Paper 2018/892

OptORAMa: Optimal Oblivious RAM

Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Kartik Nayak, Enoch Peserico, and Elaine Shi

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 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in EUROCRYPT 2020
Keywords
Oblivious RAM
Contact author(s)
asharov @ cornell edu
komargodski @ cornell edu
wklin @ cs cornell edu
nkartik @ vmware com
enoch @ dei unipd it
runting @ gmail com
History
2021-02-25: last of 8 revisions
2018-09-23: received
See all versions
Short URL
https://ia.cr/2018/892
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/892,
      author = {Gilad Asharov and Ilan Komargodski and Wei-Kai Lin and Kartik Nayak and Enoch Peserico and Elaine Shi},
      title = {{OptORAMa}: Optimal Oblivious {RAM}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/892},
      year = {2018},
      url = {https://eprint.iacr.org/2018/892}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.