Paper 2022/858

Snapshot-Oblivious RAMs: Sub-Logarithmic Efficiency for Short Transcripts

Yang Du, University of Michigan–Ann Arbor
Daniel Genkin, Georgia Institute of Technology
Paul Grubbs, University of Michigan–Ann Arbor
Abstract

Oblivious RAM (ORAM) is a powerful technique to prevent harmful data breaches. Despite tremendous progress in improving the concrete performance of ORAM, it remains too slow for use in many practical settings; recent breakthroughs in lower bounds indicate this inefficiency is inherent for ORAM and even some natural relaxations. This work introduces snapshot-oblivious RAMs, a new secure memory access primitive. Snapshot-oblivious RAMs bypass lower bounds by providing security only for transcripts whose length (call it c) is fixed and known ahead of time. Intuitively, snapshot-oblivious RAMs provide strong security for attacks of short duration, such as the snapshot attacks targeted by many encrypted databases. We give an ORAM-style definition of this new primitive, and present several constructions. The underlying design principle of our constructions is to store the history of recent operations in a data structure that can be accessed obliviously. We instantiate this paradigm with data structures that remain on the client, giving a snapshot-oblivious RAM with constant bandwidth overhead. We also show how these data structures can be stored on the server and accessed using oblivious memory primitives. Our most efficient instantiation achieves O(log c) bandwidth overhead. By extending recent ORAM lower bounds, we show this performance is asymptotically optimal. Along the way, we define a new hash queue data structure—essentially, a dictionary whose elements can be modified in a first-in-first-out fashion—which may be of independent interest.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in CRYPTO 2022
Keywords
snapshot oblivious RAM access pattern
Contact author(s)
duyung @ umich edu
genkin @ gatech edu
paulgrub @ umich edu
History
2022-07-04: revised
2022-06-29: received
See all versions
Short URL
https://ia.cr/2022/858
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/858,
      author = {Yang Du and Daniel Genkin and Paul Grubbs},
      title = {Snapshot-Oblivious {RAMs}: Sub-Logarithmic Efficiency for Short Transcripts},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/858},
      year = {2022},
      url = {https://eprint.iacr.org/2022/858}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.