Paper 2023/811

Limits of Breach-Resistant and Snapshot-Oblivious RAMs

Giuseppe Persiano, Università di Salerno, Google (United States)
Kevin Yeo, Google (United States), Columbia University

Oblivious RAMs (ORAMs) are an important cryptographic primitive that enable outsourcing data to a potentially untrusted server while hiding patterns of access to the data. ORAMs provide strong guarantees even in the face of a {\em persistent adversary} that views the transcripts of all operations and resulting memory contents. Unfortunately, the strong guarantees against persistent adversaries comes at the cost of efficiency as ORAMs are known to require $\Omega(\log n)$ overhead. In an attempt to obtain faster constructions, prior works considered security against {\em snapshot adversaries} that only have limited access to operational transcripts and memory. We consider $(s,\ell)$-snapshot adversaries that perform $s$ data breaches and views the transcripts of $\ell$ total queries. Promisingly, Du, Genkin and Grubbs [Crypto'22] presented an ORAM construction with $O(\log \ell)$ overhead protecting against $(1,\ell)$-snapshot adversaries with the transcript of $\ell$ consecutive operations from a single breach. For small values of $\ell$, this outperforms standard ORAMs. In this work, we tackle whether it is possible to further push this construction beyond a single breach. Unfortunately, we show that protecting against even slightly stronger snapshot adversaries becomes difficult. As our main result, we present a $\Omega(\log n)$ lower bound for any ORAM protecting against a $(3,1)$-snapshot adversary that performs three breaches and sees the transcript of only one query. In other words, our lower bound holds even if an adversary observes only memory contents during two breaches while managing to view the transcript of only one query in the other breach. Therefore, we surprisingly show that protecting against a snapshot adversary with three data breaches is as difficult as protecting against a persistent adversary

Available format(s)
Publication info
A minor revision of an IACR publication in CRYPTO 2023
ORAMlower boundsbreach resistantsnapshot
Contact author(s)
giuper @ gmail com
kwlyeo @ google com
2023-06-22: revised
2023-06-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Giuseppe Persiano and Kevin Yeo},
      title = {Limits of Breach-Resistant and Snapshot-Oblivious RAMs},
      howpublished = {Cryptology ePrint Archive, Paper 2023/811},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.