{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T09:50:17Z","timestamp":1774950617879,"version":"3.50.1"},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,4,12]],"date-time":"2018-04-12T00:00:00Z","timestamp":1523491200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF Graduate Research Fellowship","award":["DGE-0946797, DGE-1122374"],"award-info":[{"award-number":["DGE-0946797, DGE-1122374"]}]},{"name":"Hong Kong RGC","award":["HKU719312E"],"award-info":[{"award-number":["HKU719312E"]}]},{"name":"DoD NDSEG Fellowship","award":["CNS-1314857"],"award-info":[{"award-number":["CNS-1314857"]}]},{"name":"DARPA CRASH program","award":["N66001-10-2-4089"],"award-info":[{"award-number":["N66001-10-2-4089"]}]},{"name":"Amazon Web Services in Education program"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2018,8,31]]},"abstract":"<jats:p>\n            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\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>N<\/jats:italic>\n            ) bandwidth cost for blocks of size\n            <jats:italic>B<\/jats:italic>\n            = \u03a9 (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>N<\/jats:italic>\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.\n          <\/jats:p>","DOI":"10.1145\/3177872","type":"journal-article","created":{"date-parts":[[2018,4,13]],"date-time":"2018-04-13T12:10:20Z","timestamp":1523621420000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":162,"title":["Path ORAM"],"prefix":"10.1145","volume":"65","author":[{"given":"Emil","family":"Stefanov","sequence":"first","affiliation":[{"name":"UC Berkeley, CA, USA"}]},{"given":"Marten Van","family":"Dijk","sequence":"additional","affiliation":[{"name":"University of Connecticut, CT, USA"}]},{"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[{"name":"Cornell University, NY, USA"}]},{"given":"T.-H. Hubert","family":"Chan","sequence":"additional","affiliation":[{"name":"University of Hong Kong, Pokfulam Road, Hong Kong"}]},{"given":"Christopher","family":"Fletcher","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, IL, USA"}]},{"given":"Ling","family":"Ren","sequence":"additional","affiliation":[{"name":"MIT CSAIL, MA, USA"}]},{"given":"Xiangyao","family":"Yu","sequence":"additional","affiliation":[{"name":"MIT CSAIL, MA, USA"}]},{"given":"Srinivas","family":"Devadas","sequence":"additional","affiliation":[{"name":"MIT CSAIL, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,4,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806716"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813649"},{"key":"e_1_2_1_3_1","unstructured":"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.  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."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48000-7_36"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49099-0_7"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840761"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53644-5_3"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840765"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746621"},{"key":"e_1_2_1_10_1","volume-title":"Advances in Cryptology (EUROCRYPT\u201913)","author":"Cash David","unstructured":"David Cash , Alptekin K\u00fcp\u00e7\u00fc , and Daniel Wichs . 2013. Dynamic proofs of retrievability via oblivious RAM . In Advances in Cryptology (EUROCRYPT\u201913) . Springer , 279--295. David Cash, Alptekin K\u00fcp\u00e7\u00fc, and Daniel Wichs. 2013. Dynamic proofs of retrievability via oblivious RAM. In Advances in Cryptology (EUROCRYPT\u201913). Springer, 279--295."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49099-0_8"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258609"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293350"},{"key":"e_1_2_1_14_1","unstructured":"Kai-Min Chung Zhenming Liu and Rafael Pass. 2013. Statistically-secure ORAM with \u00d5(log2 n) Overhead. Retrieved from http:\/\/arxiv.org\/abs\/1307.3699.  Kai-Min Chung Zhenming Liu and Rafael Pass. 2013. Statistically-secure ORAM with \u00d5 (log2 n ) Overhead. Retrieved from http:\/\/arxiv.org\/abs\/1307.3699."},{"key":"e_1_2_1_15_1","unstructured":"Kai-Min Chung and Rafael Pass. 2013. A Simple ORAM. Retrieved from https:\/\/eprint.iacr.org\/2013\/243.pdf.  Kai-Min Chung and Rafael Pass. 2013. A Simple ORAM. Retrieved from https:\/\/eprint.iacr.org\/2013\/243.pdf."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1180405.1180417"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1987260.1987274"},{"key":"e_1_2_1_18_1","volume-title":"23rd USENIX Security Symposium. USENIX Association, 749--764","author":"Dautrich Jonathan","year":"2014","unstructured":"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 . 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."},{"key":"e_1_2_1_19_1","volume-title":"Theory of Cryptography","author":"Devadas Srinivas","unstructured":"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. 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."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199809)13:2%3C99::AID-RSA1%3E3.0.CO;2-M"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382536.2382540"},{"key":"e_1_2_1_22_1","volume-title":"Bucket ORAM: Single online roundtrip, constant bandwidth oblivious RAM. IACR Cryptology ePrint Archive","author":"Fletcher Christopher W.","year":"2015","unstructured":"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. 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."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2694344.2694353"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2015.58"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.22"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746593"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53015-3_20"},{"key":"e_1_2_1_28_1","volume-title":"Privacy Enhancing Technologies","author":"Gentry Craig","unstructured":"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. 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."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55220-5_23"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28416"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_2_1_32_1","volume-title":"Goodrich and Michael Mitzenmacher","author":"Michael","year":"2011","unstructured":"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. 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."},{"key":"e_1_2_1_33_1","volume-title":"Privacy-preserving group data access via stateless oblivious RAM simulation","author":"Goodrich Michael T.","unstructured":"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. 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."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382251"},{"key":"e_1_2_1_35_1","volume-title":"Performance Modeling and Design of Computer Systems: Queueing Theory in Action","author":"Harchol-Balter Mor","unstructured":"Mor Harchol-Balter . 2013. Performance Modeling and Design of Computer Systems: Queueing Theory in Action . Cambridge University Press . Mor Harchol-Balter. 2013. Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press."},{"key":"e_1_2_1_36_1","first-page":"12","article-title":"Access pattern disclosure on searchable encryption: Ramification, attack and mitigation","volume":"20","author":"Islam Mohammad Saiful","year":"2012","unstructured":"Mohammad Saiful Islam , Mehmet Kuzu , and Murat Kantarcioglu . 2012 . Access pattern disclosure on searchable encryption: Ramification, attack and mitigation . In NDSS , Vol. 20 , 12 . Mohammad Saiful Islam, Mehmet Kuzu, and Murat Kantarcioglu. 2012. Access pattern disclosure on searchable encryption: Ramification, attack and mitigation. In NDSS, Vol. 20, 12.","journal-title":"NDSS"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45608-8_27"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095129"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2775054.2694385"},{"key":"e_1_2_1_40_1","volume-title":"Shroud: Ensuring private access to large-scale data in the data center. FAST","author":"Lorch Jacob R.","year":"2013","unstructured":"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. 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."},{"key":"e_1_2_1_41_1","volume-title":"How to garble RAM programs","author":"Lu Steve","unstructured":"Steve Lu and Rafail Ostrovsky . 2013. How to garble RAM programs . In EUROCRYPT. Springer . Steve Lu and Rafail Ostrovsky. 2013. How to garble RAM programs. In EUROCRYPT. Springer."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516692"},{"key":"e_1_2_1_43_1","volume-title":"Mitchell and Joe Zimmerman","author":"John","year":"2014","unstructured":"John C. Mitchell and Joe Zimmerman . 2014 . Data-oblivious data structures. In Theoretical Aspects of Computer Science (STACS\u2019 14). John C. Mitchell and Joe Zimmerman. 2014. Data-oblivious data structures. In Theoretical Aspects of Computer Science (STACS\u201914)."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2014.47"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100289"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258606"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography (PKC\u201907)","author":"Ostrovsky Rafail","unstructured":"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\u201907) . Springer-Verlag, 393--411. 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\u201907). Springer-Verlag, 393--411."},{"key":"e_1_2_1_48_1","volume-title":"Advances in Cryptology (CRYPTO\u201910)","author":"Pinkas Benny","unstructured":"Benny Pinkas and Tzachy Reinman . 2010. Oblivious RAM revisited . In Advances in Cryptology (CRYPTO\u201910) . Springer , 502--519. Benny Pinkas and Tzachy Reinman. 2010. Oblivious RAM revisited. In Advances in Cryptology (CRYPTO\u201910). Springer, 502--519."},{"key":"e_1_2_1_49_1","volume-title":"24th USENIX Security Symposium (USENIX Security\u201915)","author":"Ren Ling","year":"2015","unstructured":"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\u201915) . USENIX Association, 415--430. 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\u201915). USENIX Association, 415--430."},{"key":"e_1_2_1_50_1","volume-title":"Design and implementation of the ascend secure processor","author":"Ren Ling","year":"2017","unstructured":"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 ). 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)."},{"key":"e_1_2_1_51_1","volume-title":"Integrity verification for path oblivious-RAM","author":"Ren Ling","unstructured":"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. 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."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508148.2485971"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2016.20"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25385-0_11"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516669"},{"key":"e_1_2_1_56_1","volume-title":"Path O-RAM: An extremely simple oblivious RAM protocol. CoRR abs\/1202.5150","author":"Stefanov Emil","year":"2012","unstructured":"Emil Stefanov and Elaine Shi . 2012. Path O-RAM: An extremely simple oblivious RAM protocol. CoRR abs\/1202.5150 ( 2012 ). Emil Stefanov and Elaine Shi. 2012. Path O-RAM: An extremely simple oblivious RAM protocol. CoRR abs\/1202.5150 (2012)."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516673"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2013.25"},{"key":"e_1_2_1_59_1","unstructured":"Emil Stefanov Elaine Shi and Dawn Song. 2012. Towards practical oblivious RAM. In NDSS.  Emil Stefanov Elaine Shi and Dawn Song. 2012. Towards practical oblivious RAM. In NDSS."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813634"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660314"},{"key":"e_1_2_1_62_1","unstructured":"Peter Williams and Radu Sion. 2008. Usable PIR. In NDSS.  Peter Williams and Radu Sion. 2008. Usable PIR. In NDSS."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382229"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455770.1455790"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382299"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3177872","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3177872","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:02:55Z","timestamp":1750215775000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3177872"}},"subtitle":["An Extremely Simple Oblivious RAM Protocol"],"short-title":[],"issued":{"date-parts":[[2018,4,12]]},"references-count":65,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,8,31]]}},"alternative-id":["10.1145\/3177872"],"URL":"https:\/\/doi.org\/10.1145\/3177872","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,12]]},"assertion":[{"value":"2014-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}