Oblivious Data Structures

We are among the first to systematically investigate (memory-trace) oblivious data struc-tures. We propose a framework for constructing a variety of oblivious data structures, achiev-ing 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.