International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

OptORAMa: Optimal Oblivious RAM

Authors:
Gilad Asharov , Bar-Ilan University
Ilan Komargodski , NTT Research
Wei-Kai Lin , Cornell University
Kartik Nayak , Duke University
Enoch Peserico , Università degli Studi di Padova
Elaine Shi , Cornell University
Download:
DOI: 10.1007/978-3-030-45724-2_14 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2020
Abstract: Oblivious RAM (ORAM), first introduced in the ground-breaking work of Goldreich and Ostrovsky (STOC '87 and J. ACM '96) is a technique for provably obfuscating programs' access patterns, such that the access patterns leak no information about the programs' secret inputs. To compile a general program to an oblivious counterpart, it is well-known that $\Omega(\log N)$ amortized blowup is necessary, where $N$ is the size of the logical memory. This was shown in Goldreich and Ostrovksy's original ORAM work for statistical security and in a somewhat restricted model (the so called \emph{balls-and-bins} model), and recently by Larsen and Nielsen (CRYPTO '18) for computational security. A long standing open question is whether there exists an optimal ORAM construction that matches the aforementioned logarithmic lower bounds (without making large memory word assumptions, and assuming a constant number of CPU registers). In this paper, we resolve this problem and present the first secure ORAM with $O(\log N)$ amortized blowup, assuming one-way functions. Our result is inspired by and non-trivially improves on the recent beautiful work of Patel et al. (FOCS '18) who gave a construction with $O(\log N\cdot \log\log N)$ amortized blowup, assuming one-way functions. One of our building blocks of independent interest is a linear-time deterministic oblivious algorithm for tight compaction: Given an array of $n$ elements where some elements are marked, we permute the elements in the array so that all marked elements end up in the front of the array. Our $O(n)$ algorithm improves the previously best known deterministic or randomized algorithms whose running time is $O(n \cdot\log n)$ or $O(n \cdot\log \log n)$, respectively.
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30214,
  title={OptORAMa: Optimal Oblivious RAM},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  keywords={oblivious RAM;tight compaction;randomized algorithms},
  volume={12105},
  doi={10.1007/978-3-030-45724-2_14},
  author={Gilad Asharov and Ilan Komargodski and Wei-Kai Lin and Kartik Nayak and Enoch Peserico and Elaine Shi},
  year=2020
}