MacORAMa: Optimal Oblivious RAM with Integrity

Speaker: Neekon Vafa

Date: Friday, December 09, 2022

Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: G-882, Hewlett Room

Event Type: Seminar

Room Description:

Host: Vinod Vaikuntanathan

Contact: Felicia Raton, fraton@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: cis-seminars@csail.mit.edu

Reminder Subject: TALK: MacORAMa: Optimal Oblivious RAM with Integrity

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 about the underlying data, even via the access pattern. For a database of size $N$, well-known lower bounds show that a multiplicative overhead of $\Omega(\log N)$ in the number of RAM operations 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 2021) with $O(\log N)$ worst-case overhead and $O(1)$ client storage. However, this optimal ORAM construction is only known to be secure in the semi-honest 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 allowed to tamper with the database, this construction and many others in fact become insecure. In this work, we construct an ORAM protocol with worst-case $O(\log N)$ overhead and $O(1)$ client storage that protects against tampering adversaries. By the $\Omega(\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.

Joint work with Surya Mathialagan.

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information (CIS) Seminar 2022.

Created by Megan F Farmer at Friday, November 04, 2022 at 7:52 PM.