Welcome to the resource topic for 2023/811
Title:
Limits of Breach-Resistant and Snapshot-Oblivious RAMs
Authors: Giuseppe Persiano, Kevin Yeo
Abstract: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
ePrint: https://eprint.iacr.org/2023/811
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .