Lower Bounds for Oblivious Data Structures

DOI10.1137/1.9781611975482.149zbMath1432.68093arXiv1810.10635OpenAlexW2949514509MaRDI QIDQ5236338

Jesper Buus Nielsen, Riko Jacob, Kasper Green Larsen

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05) Computer security (68M25)

Related Items (10)

A logarithmic lower bound for oblivious RAM (for all Parameters) ⋮ Single-server private information retrieval with sublinear amortized time ⋮ Stronger lower bounds for online ORAM ⋮ A theory of composition for differential obliviousness ⋮ 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 ⋮ Limits of breach-resistant and snapshot-oblivious RAMs ⋮ On active attack detection in messaging with immediate decryption ⋮ Forward secret encrypted RAM: lower bounds and applications

This page was built for publication: Lower Bounds for Oblivious Data Structures