Shortstack: Distributed, Fault-tolerant, Oblivious Data Access

Abstract

Existing oblivious-data-access systems depend on a centralized, stateful trusted proxy; in failure-prone deployments this can break privacy guarantees or make the system unavailable. Shortstack introduces a distributed, fault-tolerant proxy architecture and a security model for studying such systems. It preserves the classical obliviousness guarantee even against a passive persistent adversary that can fail an arbitrary bounded subset of proxy servers at arbitrary times. Formal analysis establishes the guarantee, and evaluation shows that performance scales nearly linearly with the number of proxy servers.

BibTeX

@inproceedings{shortstack,
  author = {Vuppalapati*, Midhul and Babel*, Kushal and Khandelwal, Anurag and Agarwal, Rachit},
  title = {{Shortstack: Distributed, Fault-tolerant, Oblivious Data Access}},
  booktitle = {USENIX OSDI},
  month = jul,
  year = {2022},
  note = {(*Equal contribution authors)}
}