Cryptology ePrint Archive: Report 2019/237

Optimal Oblivious Priority Queues and Offline Oblivious RAM

Zahra Jafargholi and 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 asymptotically optimal offline ORAM. Our result provides the first matching upper bound to the 23 year old lower bound of Goldreich and Ostrovsky (JACM'96).

Category / Keywords: foundations / Oblivious RAM, Oblivious Priority Queue

Date: received 27 Feb 2019

Contact author: zahra at cs au dk,larsen@cs au dk,simkin@cs au dk

Available format(s): PDF | BibTeX Citation

Version: 20190228:190726 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]