Paper 2019/274

Path Oblivious Heap: Optimal and Practical Oblivious Priority Queue

Elaine Shi


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.

Available format(s)
Publication info
Published elsewhere. Major revision. IEEE Symposium on Security and Privacy, 2020
Oblivious algorithms
Contact author(s)
runting @ gmail com
2019-11-10: last of 2 revisions
2019-03-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Elaine Shi},
      title = {Path Oblivious Heap: Optimal and Practical Oblivious Priority Queue},
      howpublished = {Cryptology ePrint Archive, Paper 2019/274},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.