Path ORAM: An Extremely Simple Oblivious RAM Protocol

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 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.

References

1. Miklós Ajtai. 2010. Oblivious RAMs without cryptogrpahic assumptions. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC’10). ACM, 181--190.
2. Vincent Bindschaedler, Muhammad Naveed, Xiaorui Pan, XiaoFeng Wang, and Yan Huang. 2015. Practicing oblivious access on cloud storage: The gap, the fallacy, and the new way forward. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. ACM, 837--849.
3. Dan Boneh, David Mazieres, and Raluca Ada Popa. 2011. Remote Oblivious Storage: Making Oblivious RAM practical. Manuscript. Retrieved from http://dspace.mit.edu/bitstream/handle/1721.1/62006/MIT-CSAIL-TR-2011-018.pdf.
4. Elette Boyle, Kai-Min Chung, and Rafael Pass. 2015. Large-scale secure computation: Multi-party computation for (parallel) RAM programs. In Advances in Cryptology - Proceedings of the 35th Annual Cryptology Conference (CRYPTO’15), Part II. Springer, 742--762.
5. Elette Boyle, Kai-Min Chung, and Rafael Pass. 2016. Oblivious parallel RAM and applications. In Theory of Cryptography Conference. Springer, 175--204.
6. Elette Boyle and Moni Naor. 2016. Is there an oblivious RAM lower bound? In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science. ACM, 357--368.
7. Ran Canetti, Yilei Chen, Justin Holmgren, and Mariana Raykova. 2016. Adaptive succinct garbled RAM or: How to delegate your database. In Theory of Cryptography Conference. Springer, 61--90.
8. Ran Canetti and Justin Holmgren. 2016. Fully succinct garbled RAM. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS’16). ACM.
9. Ran Canetti, Justin Holmgren, Abhishek Jain, and Vinod Vaikuntanathan. 2015. Succinct garbling and indistinguishability obfuscation for RAM programs. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC’15). ACM, 429--437.
10. David Cash, Alptekin Küpçü, and Daniel Wichs. 2013. Dynamic proofs of retrievability via oblivious RAM. In Advances in Cryptology (EUROCRYPT’13). Springer, 279--295.
11. Binyi Chen, Huijia Lin, and Stefano Tessaro. 2016. Oblivious parallel ram: Improved efficiency and generic constructions. In Theory of Cryptography Conference. Springer, 205--234.
12. Benny Chor and Niv Gilboa. 1997. Computationally private information retrieval (extended abstract). In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC’97). ACM, 304--313.
13. Benny Chor, Eyal Kushilevitz, Oded Goldreich, and Madhu Sudan. 1998. Private information retrieval. Journal of the ACM (JACM) 45, 6 (1998), 965--981.
14. Kai-Min Chung, Zhenming Liu, and Rafael Pass. 2013. Statistically-secure ORAM with Õ(log2 n) Overhead. Retrieved from http://arxiv.org/abs/1307.3699.
15. Kai-Min Chung and Rafael Pass. 2013. A Simple ORAM. Retrieved from https://eprint.iacr.org/2013/243.pdf.
16. Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky. 2006. Searchable symmetric encryption: Improved definitions and efficient constructions. In Proceedings of the 13th ACM Conference on Computer and Communications Security. ACM, 79--88.
17. Ivan Damgård, Sigurd Meldgaard, and Jesper Buus Nielsen. 2011. Perfectly secure oblivious RAM without random oracles. In Proceedings of the 8th Conference on Theory of Cryptography (TCC’11). Springer-Verlag, Berlin, 144--163.
18. Jonathan Dautrich, Emil Stefanov, and Elaine Shi. 2014. Burst ORAM: Minimizing ORAM response times for bursty access patterns. In 23rd USENIX Security Symposium. USENIX Association, 749--764.
19. Srinivas Devadas, Marten van Dijk, Christopher W. Fletcher, Ling Ren, Elaine Shi, and Daniel Wichs. 2016. Onion ORAM: A constant bandwidth blowup oblivious ORAM. In Theory of Cryptography. Springer, 145--174.
20. Devdatt P. Dubhashi and Desh Ranjan. 1998. Balls and bins: A study in negative dependence. Random Structures and Algorithms 13, 2 (1998), 99--124.
21. Christopher W. Fletcher, Marten van Dijk, and Srinivas Devadas. 2012. A secure processor architecture for encrypted computation on untrusted programs. In Proceedings of the 7th ACM Workshop on Scalable Trusted Computing. ACM, 3--8.
22. Christopher W. Fletcher, Muhammad Naveed, Ling Ren, Elaine Shi, and Emil Stefanov. 2015a. Bucket ORAM: Single online roundtrip, constant bandwidth oblivious RAM. IACR Cryptology ePrint Archive (2015), 1065.
23. Christopher W. Fletcher, Ling Ren, Albert Kwon, Marten van Dijk, and Srinivas Devadas. 2015b. Freecursive oram: {Nearly} free recursion and integrity verification for position-based oblivious RAM. In Proceedings of the 20th International Conference on Architectural Support for Programming Languages and Operating Systems. ACM, 103--116.
24. Christopher W. Fletcher, Ling Ren, Albert Kwon, Marten van Dijk, Emil Stefanov, Dimitrios Serpanos, and Srinivas Devadas. 2015c. A low-latency, low-area hardware oblivious RAM controller. In 2015 IEEE 23rd Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM’15). IEEE, 215--222.
25. Sanjam Garg, Steve Lu, and Rafail Ostrovsky. 2015a. Black-box garbled RAM. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS’15). IEEE, 210--229.
26. Sanjam Garg, Steve Lu, Rafail Ostrovsky, and Alessandra Scafuro. 2015b. Garbled RAM from one-way functions. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing. ACM, 449--458.
27. Sanjam Garg, Payman Mohassel, and Charalampos Papamanthou. 2016. TWORAM: Efficient oblivious RAM in two rounds with applications to searchable encryption. In Annual Cryptology Conference. Springer, 563--592.
28. Craig Gentry, Kenny A. Goldman, Shai Halevi, Charanjit Julta, Mariana Raykova, and Daniel Wichs. 2013. Optimizing ORAM and using it efficiently for secure computation. In Privacy Enhancing Technologies. Springer, 1--18.
29. Craig Gentry, Shai Halevi, Steve Lu, Rafail Ostrovsky, Mariana Raykova, and Daniel Wichs. 2014. Garbled RAM revisited. In Advances in Cryptology - EUROCRYPT - International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 405--422.
30. Oded Goldreich. 1987. Towards a theory of software protection and simulation by oblivious RAMs. In STOC. ACM, 182--194.
31. Oded Goldreich and Rafail Ostrovsky. 1996. Software protection and simulation on oblivious RAMs. Journal of the ACM (JACM) 43 (1996), 431--473.
32. Michael T. Goodrich and Michael Mitzenmacher. 2011. Privacy-preserving access of outsourced data via oblivious RAM simulation. In Automata, Languages and Programming. Springer, 576--587.
33. Michael T. Goodrich, Michael Mitzenmacher, Olga Ohrimenko, and Roberto Tamassia. 2012. Privacy-preserving group data access via stateless oblivious RAM simulation. In SODA. SIAM, 157--167.
34. S. Dov Gordon, Jonathan Katz, Vladimir Kolesnikov, Fernando Krell, Tal Malkin, Mariana Raykova, and Yevgeniy Vahlis. 2012. Secure two-party computation in sublinear (amortized) time. In ACM Conference on Computer and Communications Security (CCS’12). ACM.
35. Mor Harchol-Balter. 2013. Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press.
36. Mohammad Saiful Islam, Mehmet Kuzu, and Murat Kantarcioglu. 2012. Access pattern disclosure on searchable encryption: Ramification, attack and mitigation. In NDSS, Vol. 20, 12.
37. Marcel Keller and Peter Scholl. 2014. Efficient, oblivious data structures for MPC. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, 506--525.
38. Eyal Kushilevitz, Steve Lu, and Rafail Ostrovsky. 2012. On the (in) security of hash-based oblivious RAM and a new balancing scheme. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 143--156.
39. Chang Liu, Austin Harris, Martin Maas, Michael Hicks, Mohit Tiwari, and Elaine Shi. 2015. GhostRider: A hardware-software system for memory trace oblivious computation. SIGPLAN Notices 50, 4 (March 2015), 87--101.
40. Jacob R. Lorch, Bryan Parno, James W. Mickens, Mariana Raykova, and Joshua Schiffman. 2013. Shroud: Ensuring private access to large-scale data in the data center. FAST (2013), 199--213.
41. Steve Lu and Rafail Ostrovsky. 2013. How to garble RAM programs. In EUROCRYPT. Springer.
42. Martin Maas, Eric Love, Emil Stefanov, Mohit Tiwari, Elaine Shi, Krste Asanovic, John Kubiatowicz, and Dawn Song. 2013. PHANTOM: Practical oblivious computation in a secure processor. In Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security (CCS’13). ACM.
43. John C. Mitchell and Joe Zimmerman. 2014. Data-oblivious data structures. In Theoretical Aspects of Computer Science (STACS’14).
44. Muhammad Naveed, Manoj Prabhakaran, and Carl A. Gunter. 2014. Dynamic searchable encryption via blind storage. In IEEE Symposium on Security and Privacy (SP’14). IEEE, 639--654.
45. Rafail Ostrovsky. 1990. Efficient computation on oblivious RAMs. In STOC. ACM, 514--523.
46. Rafail Ostrovsky and Victor Shoup. 1997. Private information storage. In STOC. ACM, 294--303.
47. Rafail Ostrovsky and William E. Skeith, III.2007. A survey of single-database private information retrieval: Techniques and applications. In Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography (PKC’07). Springer-Verlag, 393--411.
48. Benny Pinkas and Tzachy Reinman. 2010. Oblivious RAM revisited. In Advances in Cryptology (CRYPTO’10). Springer, 502--519.
49. Ling Ren, Christopher Fletcher, Albert Kwon, Emil Stefanov, Elaine Shi, Marten van Dijk, and Srinivas Devadas. 2015. Constants count: Practical improvements to oblivious RAM. In 24th USENIX Security Symposium (USENIX Security’15). USENIX Association, 415--430.
50. Ling Ren, Christopher W. Fletcher, Albert Kwon, Marten van Dijk, and Srinivas Devadas. 2017. Design and implementation of the ascend secure processor. IEEE Transactions on Dependable and Secure Computing PP, 99 (2017).
51. Ling Ren, Christopher W. Fletcher, Xiangyao Yu, Marius van Dijk, and Srinivas Devadas. 2013a. Integrity verification for path oblivious-RAM. In HPEC. IEEE, 1--6.
52. Ling Ren, Xiangyao Yu, Christopher W. Fletcher, Marten Van Dijk, and Srinivas Devadas. 2013b. Design space exploration and optimization of path oblivious RAM in secure processors. In ACM SIGARCH Computer Architecture News, Vol. 41. ACM, 571--582.
53. Cetin Sahin, Victor Zakhary, Amr El Abbadi, Huijia Rachel Lin, and Stefano Tessaro. 2016. TaoStore: Overcoming asynchronicity in oblivious data storage. In IEEE Symposium on Security and Privacy (SP’16).
54. Elaine Shi, T.-H. Hubert Chan, Emil Stefanov, and Mingfei Li. 2011. Oblivious RAM with O((log N)3) worst-case cost. In ASIACRYPT. Springer, 197--214.
55. Elaine Shi, Emil Stefanov, and Charalampos Papamanthou. 2013. Practical dynamic proofs of retrievability. In Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security. ACM, 325--336.
56. Emil Stefanov and Elaine Shi. 2012. Path O-RAM: An extremely simple oblivious RAM protocol. CoRR abs/1202.5150 (2012).
57. Emil Stefanov and Elaine Shi. 2013a. Multi-cloud oblivious storage. In ACM Conference on Computer and Communications Security (CCS’13). ACM.
58. Emil Stefanov and Elaine Shi. 2013b. ObliviStore: High performance oblivious cloud storage. In 2013 IEEE Symposium on Security and Privacy (SP’13). IEEE, 253--267.
59. Emil Stefanov, Elaine Shi, and Dawn Song. 2012. Towards practical oblivious RAM. In NDSS.
60. Xiao Wang, Hubert Chan, and Elaine Shi. 2015. Circuit ORAM: On tightness of the Goldreich-Ostrovsky lower bound. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. ACM, 850--861.
61. Xiao Shaun Wang, Kartik Nayak, Chang Liu, T. H. Chan, Elaine Shi, Emil Stefanov, and Yan Huang. 2014. Oblivious data structures. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. ACM, 215--226.
62. Peter Williams and Radu Sion. 2008. Usable PIR. In NDSS.
63. Peter Williams and Radu Sion. 2012. Single round access privacy on outsourced storage. In CCS. ACM, 293--304.
64. Peter Williams, Radu Sion, and Bogdan Carbunar. 2008. Building castles out of mud: Practical access pattern privacy and correctness on untrusted storage. In CCS. ACM, 139--148.
65. Peter Williams, Radu Sion, and Alin Tomescu. 2012. Privatefs: A parallel oblivious file system. In Proceedings of the 2012 ACM Conference on Computer and Communications Security. ACM, 977--988.

Index Terms

• Security and privacy

• Social and professional topics

  • Computing / technology policy

    • Computer crime