Tunably-Oblivious Memory
Jonathan L. Dautrich, Chinya V. Ravishankar · 2015
We consider the challenge of providing privacy-preserving access to data outsourced to an untrusted cloud provider. Even if data blocks are encrypted, access patterns may leak valuable information. Oblivious RAM (ORAM) protocols guarantee full access pattern privacy, but even the most efficient ORAMs to date require roughly L log2 N block transfers to satisfy an L-block query, for block store capacity N.