A logarithmic lower bound for oblivious RAM (for all Parameters)
From MaRDI portal
Publication:2139649
DOI10.1007/978-3-030-84259-8_20zbMATH Open1489.94102OpenAlexW3192610252MaRDI QIDQ2139649FDOQ2139649
Authors: Ilan Komargodski, Wei-Kai Lin 
Publication date: 18 May 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-84259-8_20
Recommendations
Data encryption (aspects in computer science) (68P25) Cryptography (94A60) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Classical models of computation (Turing machines, etc.) (68Q04)
Cites Work
- Should Tables Be Sorted?
- The cell probe complexity of dynamic range counting
- Title not available (Why is that?)
- Software protection and simulation on oblivious RAMs
- Privacy-preserving access of outsourced data via oblivious RAM simulation
- Oblivious RAM with \(O((\log N)^{3})\) worst-case cost
- Path ORAM
- Dynamic proofs of retrievability via oblivious RAM
- Logarithmic Lower Bounds in the Cell-Probe Model
- Can we overcome the \(n\log n\) barrier for oblivious sorting?
- Oblivious hashing revisited, and applications to asymptotically efficient ORAM and OPRAM
- Oblivious parallel RAM and applications
- Optimizing ORAM and Using It Efficiently for Secure Computation
- Perfectly secure oblivious RAM without random oracles
- Large-Scale Secure Computation: Multi-party Computation for (Parallel) RAM Programs
- Garbled RAM revisited
- On the (in)security of hash-based oblivious RAM and a new balancing scheme
- Cache-oblivious and data-oblivious sorting and applications
- Distributed Oblivious RAM for Secure Two-Party Computation
- Asymptotically tight bounds for composing ORAM with PIR
- OptORAMa: optimal oblivious RAM
- Yes, there is an oblivious RAM lower bound!
- Permuting Information in Idealized Two-Level Storage
- Private database access with HE-over-ORAM architecture
- Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds
- A lower bound for one-round oblivious RAM
- Lower bounds for multi-server oblivious RAMs
- Lower bounds for encrypted multi-maps and searchable encryption in the leakage cell probe model
- Stronger lower bounds for online ORAM
- Lower bounds for differentially private RAMs
- Is there an oblivious RAM lower bound?
- Lower bounds for external memory integer sorting via network coding
- Onion ORAM: a constant bandwidth blowup oblivious RAM
- Lower Bounds for Oblivious Near-Neighbor Search
- Lower bounds for oblivious data structures
- Is there an oblivious RAM lower bound for online reads?
Cited In (17)
- Lower bounds for differentially private RAMs
- Lower bound framework for differentially private and oblivious data structures
- Lower bounds for (batch) PIR with private preprocessing
- Is there an oblivious RAM lower bound for online reads?
- Is there an oblivious RAM lower bound?
- Lower bounds for oblivious data structures
- Oblivious RAM with \textit{worst-case} logarithmic overhead
- Is there an oblivious RAM lower bound for online reads?
- Snapshot-oblivious RAMs: sub-logarithmic efficiency for short transcripts
- Yes, there is an oblivious RAM lower bound!
- \textsf{MacORAMa}: optimal oblivious RAM with integrity
- Limits of breach-resistant and snapshot-oblivious RAMs
- Single-server private information retrieval with sublinear amortized time
- Doubly efficient private information retrieval and fully homomorphic RAM computation from ring LWE
- The complexity of secure RAMs
- Oblivious RAM with worst-case logarithmic overhead
- Stronger lower bounds for online ORAM
Uses Software
This page was built for publication: A logarithmic lower bound for oblivious RAM (for all Parameters)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2139649)
