PanORAMa: Oblivious RAM with Logarithmic Overhead
We present PanORAMa, the first Oblivious RAM construction that achieves communication overhead O(logN⋅loglogN) for database of N blocks and for any block size B=Ω(logN) while requiring client memory of only a constant number of memory blocks. Our scheme is only an O(loglogN) factor away from the Ω(logN) lower bound shown by Larsen and Nielsen [CRYPTO '18].
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(logN+poly(loglogλ)) 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(Nloglogλ+NlogNlogλ) 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.
This is a joint work with Sarvar Patel, Giuseppe Persiano and Kevin Yeo.