Optimal Oblivious RAM with Integrity

Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM ’96), is a protocol that allows a client to perform RAM computations on a server without revealing any information about the underlying data, even via the access pattern. For a memory of size N, well-known lower bounds show that a multiplicative overhead of Ω(log N) in the number of RAM operations is necessary. 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 memory. If an adversary is allowed to tamper with the database, this construction, as well as many existing ORAM constructions, 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 also protects against tampering adversaries. This matches the efficiency of the best known ORAM constructions while additionally providing security against tampering. We achieve this by adapting the construction of Asharov et al. in a non-black-box way by using a combination of online and offline memory checking techniques, as introduced by Blum et al. (Algorithmica, 1994).

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2022

Author dc:creator

• Mathialagan, Surya

Advisors dc:contributor.advisor

• Vaikuntanathan, Vinod
• Williams, Virginia Vassilevska

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/147499

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/147499