License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2021.8
URN: urn:nbn:de:0030-drops-143271
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14327/
Chan, T-H. Hubert ;
Shi, Elaine ;
Lin, Wei-Kai ;
Nayak, Kartik
Perfectly Oblivious (Parallel) RAM Revisited, and Improved Constructions
Abstract
Oblivious RAM (ORAM) is a technique for compiling any RAM program to an oblivious counterpart, i.e., one whose access patterns do not leak information about the secret inputs. Similarly, Oblivious Parallel RAM (OPRAM) compiles a parallel RAM program to an oblivious counterpart. In this paper, we care about ORAM/OPRAM with perfect security, i.e., the access patterns must be identically distributed no matter what the program’s memory request sequence is. In the past, two types of perfect ORAMs/OPRAMs have been considered: constructions whose performance bounds hold in expectation (but may occasionally run more slowly); and constructions whose performance bounds hold deterministically (even though the algorithms themselves are randomized).
In this paper, we revisit the performance metrics for perfect ORAM/OPRAM, and show novel constructions that achieve asymptotical improvements for all performance metrics. Our first result is a new perfectly secure OPRAM scheme with O(log³ N/log log N) expected overhead. In comparison, prior literature has been stuck at O(log³ N) for more than a decade.
Next, we show how to construct a perfect ORAM with O(log³ N/log log N) deterministic simulation overhead. We further show how to make the scheme parallel, resulting in an perfect OPRAM with O(log⁴ N/log log N) deterministic simulation overhead. For perfect ORAMs/OPRAMs with deterministic performance bounds, our results achieve subexponential improvement over the state-of-the-art. Specifically, the best known prior scheme incurs more than √N deterministic simulation overhead (Raskin and Simkin, Asiacrypt'19); moreover, their scheme works only for the sequential setting and is not amenable to parallelization.
Finally, we additionally consider perfect ORAMs/OPRAMs whose performance bounds hold with high probability. For this new performance metric, we show new constructions whose simulation overhead is upper bounded by O(log³ /log log N) except with negligible in N probability, i.e., we prove high-probability performance bounds that match the expected bounds mentioned earlier.
BibTeX - Entry
@InProceedings{chan_et_al:LIPIcs.ITC.2021.8,
author = {Chan, T-H. Hubert and Shi, Elaine and Lin, Wei-Kai and Nayak, Kartik},
title = {{Perfectly Oblivious (Parallel) RAM Revisited, and Improved Constructions}},
booktitle = {2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
pages = {8:1--8:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-197-9},
ISSN = {1868-8969},
year = {2021},
volume = {199},
editor = {Tessaro, Stefano},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14327},
URN = {urn:nbn:de:0030-drops-143271},
doi = {10.4230/LIPIcs.ITC.2021.8},
annote = {Keywords: perfect oblivious RAM, oblivious PRAM}
}
|
Keywords: |
|
perfect oblivious RAM, oblivious PRAM |
|
Collection: |
|
2nd Conference on Information-Theoretic Cryptography (ITC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
19.07.2021 |
