Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Oblivious algorithms

Original Publication (with major differences): IEEE Symposium on Security and Privacy, 2020

Date: received 8 Mar 2019, last revised 10 Nov 2019

Contact author: runting at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20191110:160608 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]