Optimal Oblivious RAM and Its Extensions

302 pagesOblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (STOC'87, J.~ACM'96), is a data-structure that compiles any program in the Random-Access Machine (RAM) model into a functionally equivalent RAM program whose memory accesses are provably ``unintelligible''. That is, for any ORAM-compiled program, the sequence of accesses must be either computationally indistinguishable or identically distributed; such ORAM schemes are said computationally secure or perfectly secure, respectively. The overhead of an ORAM scheme is defined as the multiplicative factor on the running time of the compiled program compared to the time of the original program. Goldreich and Ostrovsky proved that the overhead roughly depends on the memory space $N$ that is consumed by the original program, but pinning down the overhead asymptotically had been an open problem for three decades. In this dissertation, we construct the first asymptotically optimal ORAM, \emph{OptORAMa}, that is computationally secure and achieves $O(\log N)$ overhead. OptORAMa matches both lower bounds proved by Goldreich and Ostrovsky and Larsen and Nielsen (CRYPTO'18), and hence it closed the three-decade open problem. To further expand the landscape of ORAM and oblivious algorithm, we consider several directions: parallelization, perfect security, and RAM models with large cells. For parallelization, we consider obliviousness in the classic Parallel RAM (PRAM) model: proposed by Boyle, Pass, and Chung (TCC'16-A), Oblivious PRAM (OPRAM) is the counterpart of ORAM in the PRAM model. The overhead of OPRAM in terms of parallel time is still open, and it is tempting to improve OPRAM schemes using the ideas of OptORAMa. Among the building blocks of OptORAMa, \emph{oblivious tight compaction} is an inevitable one: a tight compaction algorithm takes as input an array of elements each tagged with 0 or 1 and then outputs the elements sorted according to their tags. Oblivious tight compaction has been a problem of independent interest due to the relevance in ORAM, sorting, and selection problems. In this dissertation, we construct the first optimal oblivious tight compaction in PRAM model: it runs in linear total work and logarithmic parallel time, matching the lower bound of parallel time by Cook, Dwork, and Reischuk (SICOMP'86). Our tight compaction is a first step toward optimal OPRAM. In the second direction, we improve the overhead of perfect ORAM/OPRAM (recall that a perfect O(P)RAM is an O(P)RAM such that the accesses are identically distributed). Perfect ORAM, first constructed by Damg{\aa}rd, Meldgaard, and Nielsen (TCC'11), is an essential primitive used in various protocols, including searchable encryption and even OptORAMa. % and hence it is of independent interest. Our perfect OPRAM improves the overhead to $O(\log^3 N/\log\log N)$, it is the first improvement in overhead since Damg{\aa}rd et al., and its construction demonstrates the versatility of optimal oblivious parallel tight compaction. Finally, we consider the scenario that an ORAM-compiled program runs on a memory array of \emph{cells} while the original runs on a memory array of \emph{words}, where the cell and the word sizes differ in the number of bits. We noticed that OptORAMa matches the best known lower bound (either Larsen and Nielsen or Goldreich and Ostrovsky) only when the cell size equals to the word size, and that there is a wide-open gap between the upper and lower bounds when cell size is larger. Superficially, it seemed that we could reduce the overhead of ORAMs in the setting of larger cells. However, this dissertation improves the lower bound: the overhead of ORAMs can only be reduced marginally with respect to increased cell size, significantly reduced the wide-open gap