[Resource Topic] 2019/237: Optimal Oblivious Priority Queues

Welcome to the resource topic for 2019/237

Optimal Oblivious Priority Queues

Authors: Zahra Jafargholi, Kasper Green Larsen, Mark Simkin


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.

ePrint: https://eprint.iacr.org/2019/237

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .