Paper 2022/662

SHORTSTACK : Distributed, Fault-tolerant, Oblivious Data Access

Midhul Vuppalapati, Cornell University
Kushal Babel, Cornell University
Anurag Khandelwal, Yale University
Rachit Agarwal, Cornell University

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 in 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.

Available format(s)
Publication info
Oblivious Data Access Access pattern attack Distributed Systems Fault Tolerance Scalability Security Model ORAM
Contact author(s)
mvv25 @ cornell edu
kb742 @ cornell edu
anurag khandelwal @ yale edu
ragarwal @ cs cornell edu
2022-06-08: revised
2022-05-27: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-ShareAlike


      author = {Midhul Vuppalapati and Kushal Babel and Anurag Khandelwal and Rachit Agarwal},
      title = {{SHORTSTACK} : Distributed, Fault-tolerant, Oblivious Data Access},
      howpublished = {Cryptology ePrint Archive, Paper 2022/662},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.