Optimal Oblivious Priority Queues

Zahra Jafargholi; Kasper Green Larsen; Mark Simkin

Paper 2019/237 Original: eprint.iacr.org/2019/237 ↗

Optimal Oblivious Priority Queues

Zahra Jafargholi

Kasper Green Larsen

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.
History: 2019-09-27: last updated; 2019-02-28: published
Short URL: https://ia.cr/2019/237
License: https://creativecommons.org/licenses/by/4.0/

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