Optimal Oblivious Priority Queues

Zahra Jafargholi, Kasper Green Larsen, Mark SimkinSODA 2021 · OpenReview

Abstract

In this work, we present the first asymptotically optimal oblivious priority queue, which matches the lower bound of Jacob, Larsen, and Nielsen (SODA'19). Our construction is conceptually simple and statistically secure. We illustrate the power of our optimal oblivious priority queue by presenting a conceptually equally simple construction of statistically secure offline ORAMs with O(log n) bandwidth overhead.
BibTeX
@inproceedings{jafargholi2021optimal,
  author = {Zahra Jafargholi and Kasper Green Larsen and Mark Simkin},
  title = {{Optimal Oblivious Priority Queues}},
  booktitle = {SODA},
  year = {2021},
  url = {https://openreview.net/forum?id=iKGCOK44LNr9},
}

Loading related content...

Figure