Neekon Vafa
February 8, 2023 at 11:00 AM on Zoom / Soda Hall
MacORAMa: Optimal Oblivious RAM with Integrity
Abstract: Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM ‘96), is a primitive that allows a client to perform RAM computations on an external database without revealing any information through the access pattern. For a database of size N, well-known lower bounds show that a multiplicative overhead of log(N) in the number of RAM queries is necessary assuming O(1) client storage. A long sequence of works culminated in the asymptotically optimal construction of Asharov, Komargodski, Lin, and Shi (CRYPTO ‘21) with O(log N) worst-case overhead and O(1) client storage. However, this optimal ORAM construction is known to be secure only in the honest-but-curious setting, where an adversary is allowed to observe the access patterns but not modify the contents of the database. In the malicious setting, where an adversary is additionally allowed to tamper with the database, this construction and many others in fact become insecure. In this talk, I will present MacORAMa, the first maliciously secure ORAM protocol with worst-case O(log N) overhead and O(1) client storage assuming one-way functions, which are also necessary. By the log(N) ORAM lower bound, our construction is asymptotically optimal. We can also interpret our construction as an online memory checker that matches the bandwidth of the best known online memory checkers while additionally hiding the access pattern. To achieve this, we intricately interleave the ORAM construction of Asharov et al. with online and offline memory checking techniques. Based on joint work with Surya Mathialagan.
Bio: Neekon Vafa is a third-year PhD student at MIT, currently visiting the Simons Institute for the Meta-Complexity program. At MIT, he is advised by Vinod Vaikuntanathan. Neekon was awarded an NSF Graduate Research Fellowship, and his research interests include cryptography, complexity theory, and connections between them. Prior to MIT, he was a software engineer at Google. Personal website: https://neekonvafa.com