Is There an Oblivious RAM Lower Bound?

DOI10.1145/2840728.2840761zbMath1334.94064OpenAlexW2293128137MaRDI QIDQ2800584

Moni Naor, Elette Boyle

Publication date: 15 April 2016

Published in: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2840728.2840761

zbMATH Keywords

sortingcryptographyPRAMmulti-party computationORAM

Mathematics Subject Classification ID

Searching and sorting (68P10) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (19)

A logarithmic lower bound for oblivious RAM (for all Parameters) ⋮ Oblivious RAM with \textit{worst-case} logarithmic overhead ⋮ Sorting Short Keys in Circuits of Size ${o(n \log n)}$ ⋮ 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 ⋮ Snapshot-oblivious RAMs: sub-logarithmic efficiency for short transcripts ⋮ Lower bound framework for differentially private and oblivious data structures ⋮ Random-index oblivious RAM ⋮ Limits of breach-resistant and snapshot-oblivious RAMs ⋮ Oblivious RAM with worst-case logarithmic overhead ⋮ Forward secret encrypted RAM: lower bounds and applications ⋮ 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? ⋮ 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: Is There an Oblivious RAM Lower Bound?