A Practical Oblivious Map Data Structure with Secure Deletion and History Independence

Daniel S. Roche, Adam J. Aviv, Seung Geol Choi

We present a new oblivious RAM that supports variable-sized storage blocks (vORAM), which is the first ORAM to allow varying block sizes without trivial padding. We also present a…