Yes, there is an oblivious RAM lower bound!
From MaRDI portal
Publication:1784105
DOI10.1007/978-3-319-96881-0_18zbMath1430.94077OpenAlexW2809996417MaRDI QIDQ1784105
Kasper Green Larsen, Jesper Buus Nielsen
Publication date: 26 September 2018
Full work available at URL: https://doi.org/10.1007/978-3-319-96881-0_18
Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (26)
A logarithmic lower bound for oblivious RAM (for all Parameters) ⋮ Oblivious RAM with \textit{worst-case} logarithmic overhead ⋮ Single-server private information retrieval with sublinear amortized time ⋮ The function-inversion problem: barriers and opportunities ⋮ Stronger lower bounds for online ORAM ⋮ The complexity of secure RAMs ⋮ Klee's measure problem made oblivious ⋮ Snapshot-oblivious RAMs: sub-logarithmic efficiency for short transcripts ⋮ 3-party distributed ORAM from oblivious set membership ⋮ Weighted oblivious RAM, with applications to searchable symmetric encryption ⋮ NanoGRAM: garbled RAM with \(\widetilde{O}(\log N)\) overhead ⋮ Lower bound framework for differentially private and oblivious data structures ⋮ Lower bounds for (batch) PIR with private preprocessing ⋮ Random-index oblivious RAM ⋮ Unnamed Item ⋮ \textsf{MacORAMa}: optimal oblivious RAM with integrity ⋮ Limits of breach-resistant and snapshot-oblivious RAMs ⋮ On active attack detection in messaging with immediate decryption ⋮ Oblivious RAM with worst-case logarithmic overhead ⋮ Forward secret encrypted RAM: lower bounds and applications ⋮ A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs ⋮ Is there an oblivious RAM lower bound for online reads? ⋮ Is there an oblivious RAM lower bound for online reads? ⋮ Locality-preserving oblivious RAM ⋮ Lower bounds for encrypted multi-maps and searchable encryption in the leakage cell probe model ⋮ OptORAMa: optimal oblivious RAM
This page was built for publication: Yes, there is an oblivious RAM lower bound!
