Paper 2019/274
Path Oblivious Heap: Optimal and Practical Oblivious Priority Queue
Elaine Shi
Abstract
We propose Path Oblivious Heap, an extremely simple, practical, and optimal oblivious priority queue. Our construction also implies a practical and optimal oblivious sorting algorithm which we call Path Oblivious Sort. Not only are our algorithms asymptotically optimal, we show that their practical performance is only a small constant factor worse than insecure baselines. More specificially, assuming roughly logarithmic client private storage, Path Oblivious Heap consumes 2× to 7× more bandwidth than the ordinary insecure binary heap; and Path Oblivious Sort consumes 4.5× to 6× more bandwidth than the insecure Merge Sort. We show that these performance results improve existing works by 1-2 orders of magnitude. Finally, we evaluate our algorithm for a multi-party computation scenario and show 7× to 8× reduction in the number of symmetric encryptions relative to the state of the art.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Major revision. IEEE Symposium on Security and Privacy, 2020
- Keywords
- Oblivious algorithms
- Contact author(s)
- runting @ gmail com
- History
- 2019-11-10: last of 2 revisions
- 2019-03-12: received
- See all versions
- Short URL
- https://ia.cr/2019/274
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/274,
author = {Elaine Shi},
title = {Path Oblivious Heap: Optimal and Practical Oblivious Priority Queue},
howpublished = {Cryptology {ePrint} Archive, Paper 2019/274},
year = {2019},
url = {https://eprint.iacr.org/2019/274}
}
