BARC/EADS Talk by Kasper Green Larsen

Title

Yes, There is an Oblivious RAM Lower Bound!

Abstract

An Oblivious RAM (ORAM) introduced by Goldreich and Ostrovsky [JACM'96] is a (possibly randomized) RAM, for which the memory access pattern reveals no information about the operations performed. The main performance metric of an ORAM is the bandwidth overhead, i.e., the multiplicative factor extra memory blocks that must be accessed to hide the operation sequence. In their seminal paper introducing the ORAM, Goldreich and Ostrovsky proved an amortized Omega(log n) bandwidth overhead lower bound for ORAMs with memory size n. Their lower bound is very strong in the sense that it applies to the ``offline'' setting in which the ORAM knows the entire sequence of operations ahead of time.

However, as pointed out by Boyle and Naor [ITCS'16] in the paper "Is there an oblivious RAM lower bound?",  there are two caveats with the lower bound of Goldreich and Ostrovsky:  (1) it only applies to ``balls in bins'' algorithms, i.e., algorithms where the ORAM may only shuffle blocks around and not apply any sophisticated encoding of the data, and (2), it only applies to statistically secure constructions. Boyle and Naor showed that removing the ``balls in bins'' assumption would result in super linear lower bounds for sorting circuits, a long standing open problem in circuit complexity. As a way to circumventing this barrier, they also proposed a notion of an ``online'' ORAM, which is an ORAM that remains secure even if the operations arrive in an online manner. They argued that most known ORAM constructions work in the online setting as well.

Our contribution is an Omega(log n) lower bound on the bandwidth overhead of any online ORAM, even if we require only computational security and allow arbitrary representations of data, thus greatly strengthening the lower bound of Goldreich and Ostrovsky in the online setting.  Our lower bound applies to ORAMs with memory size n and any word size w >= log n. The bound therefore asymptotically matches the known upper bounds when w = Omega(log^2 n).

Joint work with Jesper Buus Nielsen.

Bio

Kasper Green Larsen is an assistant professor at the Department of Computer Science at Aarhus University.

His research span in many areas of theoretical computer science, but in particular, he enjoys working on data structures, range searching, lower bounds, dimensionality reduction, and streaming algorithms.

Kasper received his Ph. D. from Aarhus University in 2013 and since 2017 he has been a member of the Young Academy under the Royal Danish Academy of Sciences and Letters.