Lower bounds for oblivious data structures

DOI10.1137/1.9781611975482.149MaRDI QIDQ5236338zbMATH OpenOpenAlexFDO

Authors Riko Jacob, Kasper Green Larsen, Jesper Buus Nielsen

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)

Abstract: An oblivious data structure is a data structure where the memory access patterns reveals no information about the operations performed on it. Such data structures were introduced by Wang et al. [ACM SIGSAC'14] and are intended for situations where one wishes to store the data structure at an untrusted server. One way to obtain an oblivious data structure is simply to run a classic data structure on an oblivious RAM (ORAM). Until very recently, this resulted in an overhead of $omega(lgn)$ for the most natural setting of parameters. Moreover, a recent lower bound for ORAMs by Larsen and Nielsen [CRYPTO'18] show that they always incur an overhead of at least $Omega(lgn)$ if used in a black box manner. To circumvent the $omega(lgn)$ overhead, researchers have instead studied classic data structure problems more directly and have obtained efficient solutions for many such problems such as stacks, queues, deques, priority queues and search trees. However, none of these data structures process operations faster than $Theta(lgn)$, leaving open the question of whether even faster solutions exist. In this paper, we rule out this possibility by proving $Omega(lgn)$ lower bounds for oblivious stacks, queues, deques, priority queues and search trees.

Recommendations

• Data-oblivious data structures
• Yes, there is an oblivious RAM lower bound!
• A logarithmic lower bound for oblivious RAM (for all Parameters)
• scientific article; zbMATH DE number 1559561
• Is there an oblivious RAM lower bound for online reads?

Cited in

(19)

• Stronger lower bounds for online ORAM
• Lower bound framework for differentially private and oblivious data structures
• Lower bounds for (batch) PIR with private preprocessing
• A logarithmic lower bound for oblivious RAM (for all parameters)
• Data Structures Lower Bounds and Popular Conjectures
• Foundations of Differentially Oblivious Algorithms
• A logarithmic lower bound for oblivious RAM (for all Parameters)
• Snapshot-oblivious RAMs: sub-logarithmic efficiency for short transcripts
• Differentially oblivious Turing machines
• A theory of composition for differential obliviousness
• Limits of breach-resistant and snapshot-oblivious RAMs
• On active attack detection in messaging with immediate decryption
• Tight Bounds on Oblivious Chaining
• Data-oblivious data structures
• Single-server private information retrieval with sublinear amortized time
• Forward secret encrypted RAM: lower bounds and applications
• scientific article; zbMATH DE number 1559561 (Why is no real title available?)
• Optimal offline ORAM with perfect security via simple oblivious priority queues
• Lower Bounds for Oblivious Transfer Reductions

This page was built for publication: Lower bounds for oblivious data structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236338)