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)
- 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
-
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} }