2026-07-20T05:27:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14327 2024-03-06T10:53:47Z ddc:004 open_access

Perfectly Oblivious (Parallel) RAM Revisited, and Improved Constructions Chan, T-H. Hubert Shi, Elaine Lin, Wei-Kai Nayak, Kartik perfect oblivious RAM oblivious PRAM 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik T-H. Hubert Chan and Elaine Shi and Wei-Kai Lin and Kartik Nayak 2021 Is Part Of LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2021.8 urn:nbn:de:0030-drops-143271 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.8 eng https://creativecommons.org/licenses/by/4.0/legalcode