Abstract
Oblivious RAM (ORAM), introduced in the context of software protection by Goldreich and Ostrovsky [JACM'96], aims at obfuscating the memory access pattern induced by a RAM computation. Ideally, the memory access pattern of an ORAM should be independent of the data being processed.
Since the work of Goldreich and Ostrovsky, it was believed that there is an inherent Omega(log n) bandwidth overhead in any ORAM working with memory of size n. Larsen and Nielsen [CRYPTO'18] were the first to give a general Omega(log n) lower bound for any online ORAM, i.e., an ORAM that must process its inputs in an online manner.