Title: OptORAMa: Optimal Oblivious RAM
Oblivious RAM (ORAM), first introduced in the ground-breaking work of Goldreich and Ostrovsky (STOC ’87 and J. ACM ’96) is a technique for provably obfuscating programs’ access patterns, such that the access patterns leak no information about the programs’ secret inputs. To compile a general program to an oblivious counterpart, it is well-known that Ω(log N) amortized blowup is necessary, where N is the size of the logical memory. This was shown in Goldreich and Ostrovksy’s original ORAM work for statistical security and in a somewhat restricted model (the so called balls-and-bins model), and recently by Larsen and Nielsen (CRYPTO ’18) for computational security.
A long standing open question is whether there exists an optimal ORAM construction that matches the aforementioned logarithmic lower bounds (without making large memory word assumptions, and assuming a constant number of CPU registers). Recently, my coauthor and I resolve this problem and present the first secure ORAM with O(logN) amortized blowup, assuming one-way functions.
In this talk, I will present the framework of our construction, which is based on the recent beautiful work of Patel et al. (FOCS ’18) who gave a construction with O(log N · loglog N) amortized blowup, assuming one-way functions. In addition, I will also present one of our building blocks of independent interest, a linear-time deterministic oblivious algorithm for tight compaction: Given an array of n elements where some elements are marked, we permute the elements in the array so that all marked elements end up in the front of the array. Our O(n) algorithm improves the previously best known deterministic or randomized algorithms whose running time is O(n · log n) or O(n · loglog n), respectively.
This is a joint work with Gilad Asharov, Ilan Komargodski, Kartik Nayak, Enoch Peserico, and Elaine Shi.