Friday, September 17, 2021 - 1:00pm to 2:30pm

Location:

email dlehto@mit.edu for Zoom Link

Speaker:

Ilan Komargodski

Seminar group:

An Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM 1996), is a (probabilistic) RAM that hides its access pattern, i.e., for every input the observed locations accessed are similarly distributed. In recent years there has been great progress both in terms of upper bounds as well as in terms of lower bounds, essentially pinning down the smallest overhead possible in various settings of parameters.

In this talk I will describe a recent work related to proving lower bounds for ORAM. Specifically, we will show that any ORAM must make logarithmically many physical accesses per each logical query, amortized. The lower bound will hold for any reasonable choice of word sizes and block sizes. An application of this result is an unconditional separation between online and offline ORAM.