Paper 2019/237

Optimal Oblivious Priority Queues

Zahra Jafargholi, Kasper Green Larsen, and Mark Simkin

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, statistically secure, and has small hidden constants. We illustrate the power of our optimal oblivious priority queue by presenting a conceptually equally simple construction of statistically secure offline ORAMs with $O(\lg n)$ bandwidth overhead.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Oblivious RAMOblivious Priority Queue
Contact author(s)
zahra @ cs au dk
larsen @ cs au dk
simkin @ cs au dk
History
2019-09-27: revised
2019-02-28: received
See all versions
Short URL
https://ia.cr/2019/237
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/237,
      author = {Zahra Jafargholi and Kasper Green Larsen and Mark Simkin},
      title = {Optimal Oblivious Priority Queues},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/237},
      year = {2019},
      url = {https://eprint.iacr.org/2019/237}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.