You are looking at a specific version 20190927:131000 of this paper.
See the latest version.
Paper 2019/237
Optimal Oblivious Priority Queues
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 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