A logarithmic lower bound for oblivious RAM (for all Parameters)
From MaRDI portal
Publication:2139649
DOI10.1007/978-3-030-84259-8_20zbMath1489.94102OpenAlexW3192610252MaRDI QIDQ2139649
Publication date: 18 May 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-84259-8_20
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cryptography (94A60) Data encryption (aspects in computer science) (68P25) Classical models of computation (Turing machines, etc.) (68Q04)
Related Items (9)
Single-server private information retrieval with sublinear amortized time ⋮ The complexity of secure RAMs ⋮ Snapshot-oblivious RAMs: sub-logarithmic efficiency for short transcripts ⋮ Lower bound framework for differentially private and oblivious data structures ⋮ Lower bounds for (batch) PIR with private preprocessing ⋮ \textsf{MacORAMa}: optimal oblivious RAM with integrity ⋮ Limits of breach-resistant and snapshot-oblivious RAMs ⋮ Oblivious RAM with worst-case logarithmic overhead ⋮ Doubly efficient private information retrieval and fully homomorphic RAM computation from ring LWE
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Dynamic proofs of retrievability via oblivious RAM
- Yes, there is an oblivious RAM lower bound!
- 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
- OptORAMa: optimal oblivious RAM
- Stronger lower bounds for online ORAM
- Lower bounds for differentially private RAMs
- Oblivious hashing revisited, and applications to asymptotically efficient ORAM and OPRAM
- Private Database Access with HE-over-ORAM Architecture
- Onion ORAM: A Constant Bandwidth Blowup Oblivious RAM
- Oblivious Parallel RAM and Applications
- Is There an Oblivious RAM Lower Bound?
- Optimizing ORAM and Using It Efficiently for Secure Computation
- Perfectly Secure Oblivious RAM without Random Oracles
- Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation
- Oblivious RAM with O((logN)3) Worst-Case Cost
- Large-Scale Secure Computation: Multi-party Computation for (Parallel) RAM Programs
- Should Tables Be Sorted?
- Software protection and simulation on oblivious RAMs
- Path ORAM
- Distributed Oblivious RAM for Secure Two-Party Computation
- Permuting Information in Idealized Two-Level Storage
- Lower Bounds for Oblivious Near-Neighbor Search
- Lower bounds for external memory integer sorting via network coding
- Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds
- Can We Overcome the n log n Barrier for Oblivious Sorting?
- Lower Bounds for Oblivious Data Structures
- The cell probe complexity of dynamic range counting
- Garbled RAM Revisited
- Logarithmic Lower Bounds in the Cell-Probe Model
- Asymptotically Tight Bounds for Composing ORAM with PIR
- Is there an oblivious RAM lower bound for online reads?
This page was built for publication: A logarithmic lower bound for oblivious RAM (for all Parameters)
