Cryptology ePrint Archive: Report 2019/274

Path Oblivious Heap

Elaine Shi

Abstract: We propose Path Oblivious Heap, an extremely simple, practical, and optimal oblivious priority queue. Path Oblivious Heap is only a small constant factor slower than the standard insecure binary heap. Our construction also implies a practical and optimal oblivious sorting algorithm.

Category / Keywords: foundations / Oblivious algorithms

Date: received 8 Mar 2019

Contact author: runting at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190312:120001 (All versions of this report)

Short URL: ia.cr/2019/274


[ Cryptology ePrint archive ]