  We present Path ORAM, an extremely simple Oblivious RAM protocol with a small
amount of client storage. Partly due to its simplicity, Path ORAM is the most
practical ORAM scheme known to date with small client storage. We formally
prove that Path ORAM has a O(log N) bandwidth cost for blocks of size B =
Omega(log^2 N) bits. For such block sizes, Path ORAM is asymptotically better
than the best known ORAM schemes with small client storage. Due to its
practicality, Path ORAM has been adopted in the design of secure processors
since its proposal.
