{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T04:28:16Z","timestamp":1778128096703,"version":"3.51.4"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,2,24]],"date-time":"2023-02-24T00:00:00Z","timestamp":1677196800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,2,24]],"date-time":"2023-02-24T00:00:00Z","timestamp":1677196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2023,4]]},"DOI":"10.1007\/s00145-023-09447-5","type":"journal-article","created":{"date-parts":[[2023,2,24]],"date-time":"2023-02-24T23:02:15Z","timestamp":1677279735000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Oblivious RAM with Worst-Case Logarithmic Overhead"],"prefix":"10.1007","volume":"36","author":[{"given":"Gilad","family":"Asharov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilan","family":"Komargodski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei-Kai","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,2,24]]},"reference":[{"key":"9447_CR1","doi-asserted-by":"crossref","unstructured":"Mikl\u00f3s Ajtai, J\u00e1nos Koml\u00f3s, and Endre Szemer\u00e9di. An $$O(n \\log n)$$ sorting network. In STOC, pages 1\u20139, 1983.","DOI":"10.1145\/800061.808726"},{"key":"9447_CR2","doi-asserted-by":"crossref","unstructured":"Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Kartik Nayak, Enoch Peserico, and Elaine Shi. OptORAMa: optimal oblivious RAM. In EUROCRYPT, pages 403\u2013432, 2020.","DOI":"10.1007\/978-3-030-45724-2_14"},{"key":"9447_CR3","first-page":"1292","volume":"2020","author":"Gilad Asharov","year":"2020","unstructured":"Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, and Elaine Shi. Optimal oblivious parallel RAM. IACR ePrint Arch., 2020:1292, 2020.","journal-title":"IACR ePrint Arch."},{"key":"9447_CR4","doi-asserted-by":"crossref","unstructured":"Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, and Elaine Shi. Oblivious RAM with worst-case logarithmic overhead. In Advances in Cryptology - CRYPTO, pages 610\u2013640, 2021.","DOI":"10.1007\/978-3-030-84259-8_21"},{"key":"9447_CR5","doi-asserted-by":"crossref","unstructured":"Vincent Bindschaedler, Muhammad Naveed, Xiaorui Pan, XiaoFeng Wang, and Yan Huang. Practicing oblivious access on cloud storage: the gap, the fallacy, and the new way forward. In CCS, pages 837\u2013849, 2015.","DOI":"10.1145\/2810103.2813649"},{"key":"9447_CR6","doi-asserted-by":"crossref","unstructured":"Elette Boyle and Moni Naor. Is there an oblivious RAM lower bound? In ITCS, pages 357\u2013368, 2016.","DOI":"10.1145\/2840728.2840761"},{"issue":"5","key":"9447_CR7","doi-asserted-by":"publisher","first-page":"28:1","DOI":"10.1145\/3402457","volume":"67","author":"Ran Canetti","year":"2020","unstructured":"Ran Canetti. Universally composable security. J. ACM, 67(5):28:1\u201328:94, 2020.","journal-title":"J. ACM"},{"key":"9447_CR8","doi-asserted-by":"crossref","unstructured":"David Cash, Paul Grubbs, Jason Perry, and Thomas Ristenpart. Leakage-abuse attacks against searchable encryption. In CCS, pages 668\u2013679, 2015.","DOI":"10.1145\/2810103.2813700"},{"key":"9447_CR9","doi-asserted-by":"crossref","unstructured":"T.-H.\u00a0Hubert Chan, Yue Guo, Wei-Kai Lin, and Elaine Shi. Oblivious hashing revisited, and applications to asymptotically efficient ORAM and OPRAM. In ASIACRYPT, pages 660\u2013690, 2017.","DOI":"10.1007\/978-3-319-70694-8_23"},{"key":"9447_CR10","doi-asserted-by":"crossref","unstructured":"T.-H.\u00a0Hubert Chan, Kartik Nayak, and Elaine Shi. Perfectly secure oblivious parallel RAM. In TCC, pages 636\u2013668, 2018.","DOI":"10.1007\/978-3-030-03810-6_23"},{"key":"9447_CR11","doi-asserted-by":"crossref","unstructured":"T.-H.\u00a0Hubert Chan and Elaine Shi. Circuit OPRAM: unifying statistically and computationally secure orams and oprams. In TCC, pages 72\u2013107, 2017.","DOI":"10.1007\/978-3-319-70503-3_3"},{"key":"9447_CR12","doi-asserted-by":"crossref","unstructured":"Kai-Min Chung, Zhenming Liu, and Rafael Pass. Statistically-secure ORAM with $$\\tilde{O}(\\log ^2n)$$ overhead. In ASIACRYPT, pages 62\u201381, 2014.","DOI":"10.1007\/978-3-662-45608-8_4"},{"key":"9447_CR13","doi-asserted-by":"crossref","unstructured":"Samuel Dittmer and Rafail Ostrovsky. Oblivious tight compaction in $$O(n)$$ time with smaller constant. In SCN, pages 253\u2013274, 2020.","DOI":"10.1007\/978-3-030-57990-6_13"},{"key":"9447_CR14","doi-asserted-by":"crossref","unstructured":"Brett\u00a0Hemenway Falk, Daniel Noble, and Rafail Ostrovsky. Alibi: A flaw in cuckoo-hashing based hierarchical ORAM schemes and a solution. In EUROCRYPT, pages 338\u2013369, 2021.","DOI":"10.1007\/978-3-030-77883-5_12"},{"key":"9447_CR15","doi-asserted-by":"crossref","unstructured":"Christopher\u00a0W Fletcher, Marten\u00a0van Dijk, and Srinivas Devadas. A secure processor architecture for encrypted computation on untrusted programs. In STC, pages 3\u20138, 2012.","DOI":"10.1145\/2382536.2382540"},{"key":"9447_CR16","doi-asserted-by":"crossref","unstructured":"Christopher\u00a0W. Fletcher, Ling Ren, Albert Kwon, Marten van Dijk, and Srinivas Devadas. Freecursive ORAM: [nearly] free recursion and integrity verification for position-based oblivious RAM. In ASPLOS, pages 103\u2013116, 2015.","DOI":"10.1145\/2775054.2694353"},{"issue":"3","key":"9447_CR17","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"Michael L Fredman","year":"1993","unstructured":"Michael\u00a0L. Fredman and Dan\u00a0E. Willard. Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci., 47(3):424\u2013436, 1993.","journal-title":"J. Comput. Syst. Sci."},{"key":"9447_CR18","doi-asserted-by":"crossref","unstructured":"Craig Gentry, Shai Halevi, Charanjit Jutla, and Mariana Raykova. Private database access with he-over-oram architecture. In CANS, pages 172\u2013191, 2015.","DOI":"10.1007\/978-3-319-28166-7_9"},{"key":"9447_CR19","doi-asserted-by":"crossref","unstructured":"Oded Goldreich. Towards a theory of software protection and simulation by oblivious rams. In STOC, pages 182\u2013194, 1987.","DOI":"10.1145\/28395.28416"},{"issue":"3","key":"9447_CR20","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1145\/233551.233553","volume":"43","author":"Oded Goldreich","year":"1996","unstructured":"Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious RAMs. J. ACM, 43(3):431\u2013473, May 1996.","journal-title":"J. ACM"},{"key":"9447_CR21","doi-asserted-by":"crossref","unstructured":"Michael\u00a0T. Goodrich and Michael Mitzenmacher. Privacy-preserving access of outsourced data via oblivious RAM simulation. In ICALP, pages 576\u2013587, 2011.","DOI":"10.1007\/978-3-642-22012-8_46"},{"key":"9447_CR22","doi-asserted-by":"crossref","unstructured":"Michael\u00a0T. Goodrich, Michael Mitzenmacher, Olga Ohrimenko, and Roberto Tamassia. Oblivious ram simulation with efficient worst-case access overhead. In CCSW, page 95-100, 2011.","DOI":"10.1145\/2046660.2046680"},{"key":"9447_CR23","doi-asserted-by":"crossref","unstructured":"Michael\u00a0T. Goodrich, Michael Mitzenmacher, Olga Ohrimenko, and Roberto Tamassia. Privacy-preserving group data access via stateless oblivious RAM simulation. In SODA, pages 157\u2013167, 2012.","DOI":"10.1137\/1.9781611973099.14"},{"key":"9447_CR24","doi-asserted-by":"crossref","unstructured":"Paul Grubbs, Richard McPherson, Muhammad Naveed, Thomas Ristenpart, and Vitaly Shmatikov. Breaking web applications built on top of encrypted data. In CCS, pages 1353\u20131364, 2016.","DOI":"10.1145\/2976749.2978351"},{"key":"9447_CR25","unstructured":"Mohammad\u00a0Saiful Islam, Mehmet Kuzu, and Murat Kantarcioglu. Access pattern disclosure on searchable encryption: Ramification, attack and mitigation. In NDSS, 2012."},{"issue":"4","key":"9447_CR26","doi-asserted-by":"publisher","first-page":"1543","DOI":"10.1137\/080728743","volume":"39","author":"Adam Kirsch","year":"2009","unstructured":"Adam Kirsch, Michael Mitzenmacher, and Udi Wieder. More robust hashing: Cuckoo hashing with a stash. SIAM J. Comput., 39(4):1543\u20131561, 2009.","journal-title":"SIAM J. Comput."},{"key":"9447_CR27","doi-asserted-by":"crossref","unstructured":"Ilan Komargodski and Wei-Kai Lin. A logarithmic lower bound for oblivious RAM (for all parameters). In Advances in Cryptology - CRYPTO, pages 579\u2013609, 2021.","DOI":"10.1007\/978-3-030-84259-8_20"},{"key":"9447_CR28","doi-asserted-by":"crossref","unstructured":"Eyal Kushilevitz, Steve Lu, and Rafail Ostrovsky. On the (in)security of hash-based oblivious RAM and a new balancing scheme. In SODA, pages 143\u2013156, 2012.","DOI":"10.1137\/1.9781611973099.13"},{"key":"9447_CR29","doi-asserted-by":"crossref","unstructured":"Kasper\u00a0Green Larsen and Jesper\u00a0Buus Nielsen. Yes, there is an oblivious RAM lower bound! In CRYPTO, pages 523\u2013542, 2018.","DOI":"10.1007\/978-3-319-96881-0_18"},{"key":"9447_CR30","doi-asserted-by":"crossref","unstructured":"Chang Liu, Xiao\u00a0Shaun Wang, Kartik Nayak, Yan Huang, and Elaine Shi. ObliVM: A programming framework for secure computation. In S &P, pages 359\u2013376, 2015.","DOI":"10.1109\/SP.2015.29"},{"key":"9447_CR31","doi-asserted-by":"crossref","unstructured":"Steve Lu and Rafail Ostrovsky. Distributed oblivious RAM for secure two-party computation. In TCC, pages 377\u2013396, 2013.","DOI":"10.1007\/978-3-642-36594-2_22"},{"key":"9447_CR32","doi-asserted-by":"crossref","unstructured":"Martin Maas, Eric Love, Emil Stefanov, Mohit Tiwari, Elaine Shi, Krste Asanovic, John Kubiatowicz, and Dawn Song. PHANTOM: practical oblivious computation in a secure processor. In CCS, pages 311\u2013324, 2013.","DOI":"10.1145\/2508859.2516692"},{"key":"9447_CR33","doi-asserted-by":"crossref","unstructured":"Rafail Ostrovsky and Victor Shoup. Private information storage. In STOC, pages 294\u2013303, 1997.","DOI":"10.1145\/258533.258606"},{"issue":"2","key":"9447_CR34","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"Rasmus Pagh","year":"2004","unstructured":"Rasmus Pagh and Flemming\u00a0Friche Rodler. Cuckoo hashing. J. Algorithms, 51(2):122\u2013144, 2004.","journal-title":"J. Algorithms"},{"key":"9447_CR35","doi-asserted-by":"crossref","unstructured":"Sarvar Patel, Giuseppe Persiano, Mariana Raykova, and Kevin Yeo. Panorama: Oblivious RAM with logarithmic overhead. In FOCS, pages 871\u2013882, 2018.","DOI":"10.1109\/FOCS.2018.00087"},{"key":"9447_CR36","doi-asserted-by":"crossref","unstructured":"Ling Ren, Xiangyao Yu, Christopher\u00a0W. Fletcher, Marten van Dijk, and Srinivas Devadas. Design space exploration and optimization of path oblivious RAM in secure processors. In ISCA, pages 571\u2013582, 2013.","DOI":"10.1145\/2508148.2485971"},{"key":"9447_CR37","doi-asserted-by":"crossref","unstructured":"Elaine Shi, T.-H.\u00a0Hubert Chan, Emil Stefanov, and Mingfei Li. Oblivious RAM with $$O((\\log N)^3)$$ worst-case cost. In ASIACRYPT, pages 197\u2013214, 2011.","DOI":"10.1007\/978-3-642-25385-0_11"},{"key":"9447_CR38","doi-asserted-by":"crossref","unstructured":"Emil Stefanov and Elaine Shi. Oblivistore: High performance oblivious cloud storage. In S &P, pages 253\u2013267, 2013.","DOI":"10.1109\/SP.2013.25"},{"key":"9447_CR39","unstructured":"Emil Stefanov, Elaine Shi, and Dawn\u00a0Xiaodong Song. Towards practical oblivious RAM. In NDSS, 2012."},{"key":"9447_CR40","doi-asserted-by":"crossref","unstructured":"Emil Stefanov, Marten van Dijk, Elaine Shi, Christopher\u00a0W. Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas. Path ORAM: an extremely simple oblivious RAM protocol. In CCS, pages 299\u2013310, 2013.","DOI":"10.1145\/2508859.2516660"},{"issue":"2","key":"9447_CR41","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1006\/jagm.2002.1211","volume":"42","author":"Mikkel Thorup","year":"2002","unstructured":"Mikkel Thorup. Randomized sorting in o(n log log n) time and linear space using addition, shift, and bit-wise boolean operations. J. Algorithms, 42(2):205\u2013230, 2002.","journal-title":"J. Algorithms"},{"key":"9447_CR42","doi-asserted-by":"crossref","unstructured":"Xiao Wang, T.-H.\u00a0Hubert Chan, and Elaine Shi. Circuit ORAM: on tightness of the goldreich-ostrovsky lower bound. In CCS, pages 850\u2013861, 2015.","DOI":"10.1145\/2810103.2813634"},{"key":"9447_CR43","unstructured":"Xiao\u00a0Shaun Wang, Yan Huang, T.-H.\u00a0Hubert Chan, Abhi Shelat, and Elaine Shi. SCORAM: oblivious RAM for secure computation. In CCS, pages 191\u2013202, 2014."},{"key":"9447_CR44","doi-asserted-by":"crossref","unstructured":"Peter Williams, Radu Sion, and Alin Tomescu. PrivateFS: A parallel oblivious file system. In CCS, pages 977\u2013988, 2012.","DOI":"10.1145\/2382196.2382299"},{"key":"9447_CR45","doi-asserted-by":"crossref","unstructured":"Samee Zahur, Xiao\u00a0Shaun Wang, Mariana Raykova, Adria Gasc\u00f3n, Jack Doerner, David Evans, and Jonathan Katz. Revisiting square-root ORAM: efficient random access in multi-party computation. In S &P, pages 218\u2013234, 2016.","DOI":"10.1109\/SP.2016.21"},{"key":"9447_CR46","unstructured":"Yupeng Zhang, Jonathan Katz, and Charalampos Papamanthou. All your queries are belong to us: The power of file-injection attacks on searchable encryption. In USENIX, pages 707\u2013720, 2016."}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09447-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-023-09447-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09447-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,15]],"date-time":"2024-10-15T04:18:07Z","timestamp":1728965887000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-023-09447-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,24]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["9447"],"URL":"https:\/\/doi.org\/10.1007\/s00145-023-09447-5","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,24]]},"assertion":[{"value":"21 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 January 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 January 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 February 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"7"}}