SHORTSTACK: Distributed, Fault-tolerant, Oblivious Data Access


Midhul Vuppalapati and 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 an 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.

OSDI '22 Open Access Sponsored by NetApp

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {280940,
author = {Midhul Vuppalapati and Kushal Babel and Anurag Khandelwal and Rachit Agarwal},
title = {{SHORTSTACK}: Distributed, Fault-tolerant, Oblivious Data Access},
booktitle = {16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22)},
year = {2022},
isbn = {978-1-939133-28-1},
address = {Carlsbad, CA},
pages = {719--734},
url = {},
publisher = {USENIX Association},
month = jul

Presentation Video