Aarhus University Seal

Optimal oblivious priority queues

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

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.

Original languageEnglish
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2021
EditorsDaniel Marx
Number of pages18
PublisherAssociation for Computing Machinery
Publication year2021
ISBN (Electronic)9781611976465
Publication statusPublished - 2021
Event32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 - Alexandria, Virtual, United States
Duration: 10 Jan 202113 Jan 2021


Conference32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
LandUnited States
ByAlexandria, Virtual
SponsorACM Special Interest Group on Algorithms and Computation Theory (SIGACT), SIAM Activity Group on Discrete Mathematics
SeriesProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Bibliographical note

Publisher Copyright:
© 2021 by SIAM

See relations at Aarhus University Citationformats

ID: 229267164