Cryptology ePrint Archive: Report 2013/280

Path ORAM: An Extremely Simple Oblivious RAM Protocol

Emil Stefanov and Marten van Dijk and Elaine Shi and Christopher Fletcher and Ling Ren and Xiangyao Yu and Srinivas Devadas

Abstract: 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. We formally prove that Path ORAM requires O(log^2 N / k) bandwidth overhead for block size B = k * log N. For block sizes bigger than O(log^2 N) bits, Path ORAM is asymptotically better than the best known ORAM scheme with small client storage. Due to its practicality, Path ORAM has been adopted in the design of secure processors since its proposal.

Category / Keywords: cryptographic protocols / oblivious ram, oram, privacy, storage, access patterns

Date: received 14 May 2013, last revised 14 May 2013

Contact author: emil at cs berkeley edu

Available formats: PDF | BibTeX Citation

Version: 20130516:132830 (All versions of this report)

Discussion forum: Show discussion | Start new discussion