Paper 2023/083

MacORAMa: Optimal Oblivious RAM with Integrity

Surya Mathialagan, Massachusetts Institute of Technology
Neekon Vafa, Massachusetts Institute of Technology
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 $\Omega(\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 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 work, we construct the first maliciously secure ORAM with worst-case $O(\log N)$ overhead and $O(1)$ client storage assuming one-way functions, which are also necessary. By the $\Omega(\log N)$ lower bound, our construction is asymptotically optimal. To attain this overhead, we develop techniques to intricately interleave online and offline memory checking for malicious security. Furthermore, we complement our positive result by showing the impossibility of a generic overhead-preserving compiler from honest-but-curious to malicious security, barring a breakthrough in memory checking.

Note: Added barrier result for an overhead-preserving compiler.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Oblivious RAMMemory Checking
Contact author(s)
smathi @ mit edu
nvafa @ mit edu
History
2023-02-25: revised
2023-01-24: received
See all versions
Short URL
https://ia.cr/2023/083
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/083,
      author = {Surya Mathialagan and Neekon Vafa},
      title = {{MacORAMa}: Optimal Oblivious {RAM} with Integrity},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/083},
      year = {2023},
      url = {https://eprint.iacr.org/2023/083}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.