Cryptology ePrint Archive: Report 2014/185

Oblivious Data Structures

Xiao Wang and Kartik Nayak and Chang Liu and Elaine Shi and Emil Stefanov and Yan Huang

Abstract: We are among the first to systematically investigate (memory-trace) oblivious data structures. We propose a framework for constructing a variety of oblivious data structures, achieving asymptotic performance gains in comparison with generic Oblivious RAM (ORAM). We evaluate the performance of our oblivious data structures in terms of their bandwidth over- heads, and also when applied to a secure computation setting. Finally, we leverage our new framework to design an efficient oblivious memory allocator which is particularly useful due to the community’s recent efforts in compiling programs targeting ORAM-capable secure processors.

Category / Keywords: cryptographic protocols / oblivious RAM, ORAM, secure computation

Date: received 9 Mar 2014

Contact author: wangxiao at cs umd edu

Available format(s): PDF | BibTeX Citation

Version: 20140309:201800 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]