PanORAMa: Oblivious RAM with Logarithmic Overhead

By Sarvar Patel, Giuseppe Persiano, Mariana Raykova, Kevin Yeo. 2018

97 citations recorded by the source corpus.

We present PanORAMa, the first Oblivious RAM construction that achieves communication overhead O(log N log log N) for database of N blocks and for any block size B = Ω(log N) while requiring client memory of only a constant number of memory blocks. Our scheme can be instantiated in the "balls and bins" model in which Goldreich and Ostrovsky [JACM 96] showed an Ω(log N) lower bound for ORAM communication. Our construction follows the hierarchical approach to ORAM design and relies on two main building blocks of independent interest: a new oblivious hash table construction with improved amortized O(log N + poly(log log λ)) communication overhead for security parameter λ and N = poly(λ), assuming its input is randomly shuffled; and a complementary new oblivious random multi-array shuffle construction, which shuffles N blocks of data with communication O(N log log λ + N log N/log λ) when the input has a certain level of entropy. We combine these two primitives to improve the shuffle time in our hierarchical ORAM construction by avoiding heavy oblivious shuffles and leveraging entropy remaining in the merged levels from previous shuffles. As a result, the amortized shuffle cost is asymptotically the same as the lookup complexity in our construction.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Private Stateful Information Retrieval (2018, methodology): “The secret key enables ORAM to use sublinear computation and bandwidth (the current, best ORAM construction usesO(logn · log logn) bandwidth and computation [44]).”
Communication-Computation Trade-offs in PIR (2019, methodology): “Unlike PSI and ORAM, we don’t need to provide privacy for the server’s database in PIR.”