Lower Bounds for Oblivious Data Structures
- ,
- Kasper Green Larsen,
- Jesper Buus Nielsen
- ,
- ,
- ,
- Aarhus Universitet,
- Aalborg Universitet
Publikation:
Konference artikel i Proceeding eller bog/rapport kapitel
Konferencebidrag i proceedings
Forskning
Peer-reviewOpen Access
Resume
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 ω(lg n) 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 Ω(lg n) if used in a black box manner. To circumvent the ω(lg n) 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 Θ(lg n), leaving open the question of whether even faster solutions exist. In this paper, we rule out this possibility by proving Ω(lg n) lower bounds for oblivious stacks, queues, deques, priority queues and search trees.
Publikation information
Produktionstype
Publikation:
Konference artikel i Proceeding eller bog/rapport kapitel
Konferencebidrag i proceedings
Forskning
Peer-reviewOriginalsprog
EngelskPublikationsmilepæle
- Udgivet - 06/01/2019
Publikationsstatus
Udgivet - 06/01/2019
Forlag
Society for Industrial and Applied Mathematics, USAISBN (Elektronisk)
978-1-61197-548-2Publikations IDer
- Scopus: 85066934958
Titel på værtspublikation
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete AlgorithmsMetrikker
PlumX, åbner i en ny fane
Antal citationer
27
Hentninger
19
Adgang til dokumenter
Accepteret manuskript, 196.55 KB
Relateret event
Titel
Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
Begivenhedstype
KonferenceGrad af anerkendelse
International begivenhedDato
06/01/2019 - 09/01/2019Lokation
San DiegoUSA
