Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / Oblivious RAM, locality, randomized algorithms

Date: received 11 Aug 2017, last revised 12 Aug 2017

Contact author: asharov at cornell edu

Available format(s): PDF | BibTeX Citation

Version: 20170813:192902 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]