Paper 2021/1280

Snoopy: Surpassing the Scalability Bottleneck of Oblivious Storage

Emma Dauterman, Vivian Fang, Ioannis Demertzis, Natacha Crooks, and Raluca Ada Popa

Abstract

Existing oblivious storage systems provide strong security by hiding access patterns, but do not scale to sustain high throughput as they rely on a central point of coordination. To overcome this scalability bottleneck, we present Snoopy, an object store that is both oblivious and scalable such that adding more machines increases system throughput. Snoopy contributes techniques tailored to the high-throughput regime to securely distribute and efficiently parallelize every system component without prohibitive coordination costs. These techniques enable Snoopy to scale similarly to a plaintext storage system. Snoopy achieves 13.7x higher throughput than Obladi, a state-of-the-art oblivious storage system. Specifically, Obladi reaches a throughput of 6.7K requests/s for two million 160-byte objects and cannot scale beyond a proxy and server machine. For the same data size, Snoopy uses 18 machines to scale to 92K requests/s with average latency under 500ms.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.SOSP 21
DOI
10.1145/3477132.3483562
Keywords
Oblivious RAM
Contact author(s)
edauterman @ berkeley edu
v fang @ berkeley edu
History
2021-11-12: last of 3 revisions
2021-09-24: received
See all versions
Short URL
https://ia.cr/2021/1280
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1280,
      author = {Emma Dauterman and Vivian Fang and Ioannis Demertzis and Natacha Crooks and Raluca Ada Popa},
      title = {Snoopy: Surpassing the Scalability Bottleneck of Oblivious Storage},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1280},
      year = {2021},
      doi = {10.1145/3477132.3483562},
      note = {\url{https://eprint.iacr.org/2021/1280}},
      url = {https://eprint.iacr.org/2021/1280}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.