Paper 2017/772

Locality-Preserving Oblivious RAM

Gilad Asharov, T-H. Hubert Chan, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi

Abstract

Oblivious RAMs, introduced by Goldreich and Ostrovsky [JACM'96], compile any RAM program into one that is ``memory oblivious'', i.e., the access pattern to the memory is independent of the input. All previous ORAM schemes, however, completely break the locality of data accesses (for instance, by shuffling the data to pseudorandom positions in memory). In this work, we initiate the study of locality-preserving ORAMs --- ORAMs that preserve locality of the accessed memory regions, while leaking only the lengths of contiguous memory regions accessed. Our main results demonstrate the existence of a locality-preserving ORAM with poly-logarithmic overhead both in terms of bandwidth and locality. We also study the tradeoff between locality, bandwidth and leakage, and show that any scheme that preserves locality and does not leak the lengths of the contiguous memory regions accessed, suffers from prohibitive bandwidth. To the best of our knowledge, before our work, the only works combining locality and obliviousness were for symmetric searchable encryption [e.g., Cash and Tessaro (EUROCRYPT'14), Asharov et al. (STOC'16)]. Symmetric search encryption ensures obliviousness if each keyword is searched only once, whereas ORAM provides obliviousness to any input program. Thus, our work generalizes that line of work to the much more challenging task of preserving locality in ORAMs.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2019
Keywords
Oblivious RAMlocalityrandomized algorithms
Contact author(s)
asharov @ cornell edu
History
2019-03-03: revised
2017-08-13: received
See all versions
Short URL
https://ia.cr/2017/772
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/772,
      author = {Gilad Asharov and T-H.  Hubert Chan and Kartik Nayak and Rafael Pass and Ling Ren and Elaine Shi},
      title = {Locality-Preserving Oblivious RAM},
      howpublished = {Cryptology ePrint Archive, Paper 2017/772},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/772}},
      url = {https://eprint.iacr.org/2017/772}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.