UCONN | UNIVERSITY OF CONNECTICUT

Secure Computation Laboratory

Professor Marten van Dijk
Advertisment

Oblivious RAM

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 = Ω(log 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.

ORAM Model

Path ORAM

References

  • S. Devadas, M. van Dijk, C.W. Fletcher, L. Ren, E. Shi, and D.Wichs. "Onion ORAM: A Constant Bandwidth Blowup Oblivious RAM", TCC 2016. (Alphabetical authors, C.W. Fletcher and L. Ren shared lead author)
  • L. Ren, C. Fletcher, A. Kwon, E. Stefanov, E. Shi, M. van Dijk, and S. Devadas. "Constants Count: Practical Improvements to Oblivious RAM", Usenix Security 2015.
  • E. Stefanov, M. van Dijk, E. Shi, C.W. Fletcher, L. Ren, X. Yu, and S. Devadas.. "Path ORAM: An Extremely Simple Oblivious RAM Protocol", Proceedings of the ACM Conference on Computer and Communications Security (CCS) 2013. Best student paper award (1 out of 3; no best paper awards given).