International Association
for Cryptologic Research

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.