Stronger lower bounds for online ORAM

DOI10.1007/978-3-030-36033-7_10MaRDI QIDQ2175940zbMATH OpenOpenAlexFDO

Authors Pavel Hubáček, Michal Koucký, Karel Král, Veronika Slívová

Publication date 30 April 2020

Full work available at URL https://arxiv.org/abs/1903.03385

zbMATH Keywords

bandwidth overheadlower boundoblivious RAM

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cryptography (94A60)

Abstract: Oblivious RAM (ORAM), introduced in the context of software protection by Goldreich and Ostrovsky [JACM'96], aims at obfuscating the memory access pattern induced by a RAM computation. Ideally, the memory access pattern of an ORAM should be independent of the data being processed. Since the work of Goldreich and Ostrovsky, it was believed that there is an inherent $Omega(logn)$ bandwidth overhead in any ORAM working with memory of size $n$. Larsen and Nielsen [CRYPTO'18] were the first to give a general $Omega(logn)$ lower bound for any online ORAM, i.e., an ORAM that must process its inputs in an online manner. In this work, we revisit the lower bound of Larsen and Nielsen, which was proved under the assumption that the adversarial server knows exactly which server accesses correspond to which input operation. We give an $Omega(logn)$ lower bound for the bandwidth overhead of any online ORAM even when the adversary has no access to this information. For many known constructions of ORAM this information is provided implicitly as each input operation induces an access sequence of roughly the same length. Thus, they are subject to the lower bound of Larsen and Nielsen. Our results rule out a broader class of constructions and specifically, they imply that obfuscating the boundaries between the input operations does not help in building a more efficient ORAM. As our main technical contribution and to handle the lack of structure, we study the properties of access graphs induced naturally by the memory access pattern of an ORAM computation. We identify a particular graph property that can be efficiently tested and that all access graphs of ORAM computation must satisfy with high probability. This property is reminiscent of the Larsen-Nielsen property but it is substantially less structured; that is, it is more generic.

Recommendations

• Yes, there is an oblivious RAM lower bound!
• A logarithmic lower bound for oblivious RAM (for all Parameters)
• Is there an oblivious RAM lower bound for online reads?
• Is there an oblivious RAM lower bound for online reads?
• Is there an oblivious RAM lower bound?

Cites work

• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• Is there an oblivious RAM lower bound for online reads?
• Is there an oblivious RAM lower bound?
• Logarithmic Lower Bounds in the Cell-Probe Model
• Lower bounds for differentially private RAMs
• Lower bounds for oblivious data structures
• Oblivious RAMs without cryptogarphic assumptions
• On the (in)security of hash-based oblivious RAM and a new balancing scheme
• Optimizing ORAM and Using It Efficiently for Secure Computation
• OptORAMa: optimal oblivious RAM
• Path ORAM
• Perfectly secure oblivious RAM without random oracles
• Privacy-preserving access of outsourced data via oblivious RAM simulation
• Software protection and simulation on oblivious RAMs
• Statistically-secure ORAM with \(\tilde{O}(\log^2 n)\) overhead
• Theory of Cryptography
• Yes, there is an oblivious RAM lower bound!

Cited in

(15)

• Yes, there is an oblivious RAM lower bound!
• Lower bounds for encrypted multi-maps and searchable encryption in the leakage cell probe model
• A logarithmic lower bound for oblivious RAM (for all Parameters)
• Lower bounds for differentially private RAMs
• Forward secret encrypted RAM: lower bounds and applications
• Is there an oblivious RAM lower bound?
• Tight Bounds on Online Checkpointing Algorithms
• Asymptotically tight bounds for composing ORAM with PIR
• Is there an oblivious RAM lower bound for online reads?
• Is there an oblivious RAM lower bound for online reads?
• M-ORAM Revisited: Security and Construction Updates
• Lower bound framework for differentially private and oblivious data structures
• Lower bounds for (batch) PIR with private preprocessing
• Limits of breach-resistant and snapshot-oblivious RAMs
• A logarithmic lower bound for oblivious RAM (for all parameters)

This page was built for publication: Stronger lower bounds for online ORAM

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2175940)