You are looking at a specific version 20170813:192902 of this paper. See the latest version.

Paper 2017/772

Oblivious Computation with Data Locality

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

Abstract

Oblivious RAM compilers, 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 (by shuffling the data to pseudorandom positions in memory). In this work, we initiate the study of locality-friendly oblivious RAMs - Oblivious RAM compilers that preserve the locality of the accessed memory regions, while leaking only the lengths of contiguous memory regions accessed; we refer to such schemes as Range ORAMs. Our main results demonstrate the existence of a statistically-secure Range ORAM with only poly-logarithmic overhead (both in terms of the number of memory accesses, and in terms of locality). In our most optimized construction, the overhead is only a logarithmic factor greater than the best ORAM scheme (without locality). To further improve the parameters, we also consider the weaker notion of a File ORAM: whereas a Range ORAM needs to support read/write access to arbitrary regions of the memory, a File ORAM only needs to support access to pre-defined non-overlapping regions (e.g., files being stored in memory). Assuming one-way functions, we present a computationally-secure File ORAM that, up to $\log \log n$ factors matches the best ORAM schemes (i.e., we essentially get "locality for free".) As an intermediate result, we also develop a novel sorting algorithm which is also asymptotically optimal (up to $\log\log n$ factors) and enjoys good locality (can be implemented using $O(\log n)$ sequential accesses). This sorting algorithm can serve as a practical alternative to the previous sorting algorithms used in other oblivious RAM compilers and other applications, and might be of an independent interest. To the best of our knowledge, before our work, the only works combining locality and obliviousness were for the special case of symmetric searchable encryption [Cash and Tessaro (EUROCRYPT'14), Asharov et al. (STOC'16)]. Searchable encryption can be viewed as a special case of a "read-only" File ORAM which leaks whether the same files are accessed again, and whether files contain the same keyword; this leakage, however, has been shown to be harmful in many applications, and is prevented by the definition of a File ORAM.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.