  Many applications that benefit from data offload to cloud services operate on
private data. A now-long line of work has shown that, even when data is
offloaded in an encrypted form, an adversary can learn sensitive information by
analyzing data access patterns. Existing techniques for oblivious data
access-that protect against access pattern attacks-require a centralized and
stateful trusted proxy to orchestrate data accesses from applications to cloud
services. We show that, in failure-prone deployments, such a centralized and
stateful proxy results in violation of oblivious data access security
guarantees and/or system unavailability. We thus initiate the study of
distributed, fault-tolerant, oblivious data access.
  We present SHORTSTACK, a distributed proxy architecture for oblivious data
access in failure-prone deployments. SHORTSTACK achieves the classical
obliviousness guarantee--access patterns observed by the adversary being
independent of the input--even under a powerful passive persistent adversary
that can force failure of arbitrary (bounded-sized) subset of proxy servers at
arbitrary times. We also introduce a security model that enables studying
oblivious data access with distributed, failure-prone, servers. We provide a
formal proof that SHORTSTACK enables oblivious data access under this model,
and show empirically that SHORTSTACK performance scales near-linearly with
number of distributed proxy servers.
