Poster: Oblivious Data Structures

Abstract—We are among the first to systematically investigate (memory-trace) oblivious data structures. We propose a frame-work 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 overheads, 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. I