Path Oblivious Heap - Optimal and Practical Oblivious Priority Queue

Explore an innovative approach to oblivious priority queues and sorting algorithms in this 16-minute IEEE conference talk. Discover the Path Oblivious Heap, a simple yet optimal solution that offers practical performance with only a small constant factor increase in bandwidth compared to insecure baselines. Learn how this construction leads to Path Oblivious Sort, an efficient oblivious sorting algorithm. Examine the performance improvements over existing works, with 2-7 times more bandwidth usage than insecure binary heaps for the Path Oblivious Heap, and 4.5-6 times more for Path Oblivious Sort compared to insecure Merge Sort. Gain insights into the algorithm's application in multi-party computation scenarios, where it achieves a 7-8 times reduction in symmetric encryptions compared to the state of the art.

Path Oblivious Heap: Optimal and Practical Oblivious Priority Queue