Stronger Lower Bounds for Online ORAM.

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 oblivious 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. In this work, we revisit the lower bound of Nielsen and Larsen, which was proved under an assumption about the format of the memory access pattern of the ORAM. We give an $\Omega(\log n) $ lower bound for the bandwidth overhead of any online ORAM without any such restriction. Our results thus match the model of Boyle and Naor [ITCS'16] who proved that any super-constant lower bound for offline ORAM, i.e., an ORAM that can process its inputs simultaneously, implies super-linear lower bounds on size of sorting circuits -- which would constitute a major breakthrough in computational complexity. As our main technical contribution and to handle the lack of structure, we study the properties of access graph induced naturally by the memory access pattern of an ORAM computation. We identify a particular graph property that can be efficiently tested and that all access graphs of ORAM computation must satisfy with high probability. This property is reminiscent of the Larsen-Nielsen property but it is substantially less structured; that is, it is more generic.