OptORAMa: Optimal Oblivious RAM
Journal of the ACM · 28.02.2023 · 70 (1) · 1-70
DOI: 10.1145/3566049 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 19.12.2022. Verfasst von Gilad Asharov und 5 weiteren Autor:innen. Die Arbeit wurde bisher 21-mal zitiert (Crossref) und nennt 68 Literaturangaben. Gefördert von: Simons Foundation junior fellow award, Israel Science Foundation, US-Israel Binational Science Foundation and the US National Science Foundation.
Abstract (Originalsprache)
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 Ω (log N ) amortized blowup in memory accesses 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 article, 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 ⋅ 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 ⋅ log n ) or O ( n ⋅ log log n ), respectively.
Förderung
- Simons Foundation junior fellow award
- Israel Science Foundation
- US-Israel Binational Science Foundation and the US National Science Foundation
- AFOSR Award
- NSF
- DARPA Brandeis award
- Packard Fellowship
- Sloan Fellowship
Zitieren
APA
Asharov, G., Komargodski, I., Lin, W., Nayak, K., Peserico, E., & Shi, E. (2023). OptORAMa: Optimal Oblivious RAM. Journal of the ACM, 70(1), 1-70. https://doi.org/10.1145/3566049
Vancouver
Asharov G, Komargodski I, Lin W, Nayak K, Peserico E, Shi E. OptORAMa: Optimal Oblivious RAM. Journal of the ACM. 2023;70(1):1-70. doi:10.1145/3566049
BibTeX
@article{Asharov2023,
author = {Asharov, Gilad and Komargodski, Ilan and Lin, Wei-Kai and Nayak, Kartik and Peserico, Enoch and Shi, Elaine},
title = {OptORAMa: Optimal Oblivious RAM},
journal = {Journal of the ACM},
year = {2023},
volume = {70},
number = {1},
pages = {1--70},
doi = {10.1145/3566049}
}
EUVIMED