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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2019/274}},
      url = {https://eprint.iacr.org/2019/274}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.