{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T14:40:46Z","timestamp":1773931246744,"version":"3.50.1"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,12,19]],"date-time":"2022-12-19T00:00:00Z","timestamp":1671408000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Simons Foundation junior fellow award"},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["2439\/20"],"award-info":[{"award-number":["2439\/20"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1774\/20"],"award-info":[{"award-number":["1774\/20"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"US-Israel Binational Science Foundation and the US National Science Foundation","award":["2020643"],"award-info":[{"award-number":["2020643"]}]},{"name":"AFOSR Award","award":["FA9550-18-1-0267"],"award-info":[{"award-number":["FA9550-18-1-0267"]}]},{"name":"NSF","award":["CNS-1601879"],"award-info":[{"award-number":["CNS-1601879"]}]},{"name":"DARPA Brandeis award"},{"name":"Packard Fellowship"},{"name":"Sloan Fellowship"},{"name":"Google Faculty Research Awards"},{"name":"VMware Research Award"},{"name":"Baidu Research Award"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2023,2,28]]},"abstract":"<jats:p>\n            Oblivious RAM (ORAM), first introduced in the ground-breaking work of Goldreich and Ostrovsky (STOC\u00a0\u201987 and J. ACM \u201996) is a technique for provably obfuscating programs\u2019 access patterns, such that the access patterns leak no information about the programs\u2019 secret inputs. To compile a general program to an oblivious counterpart, it is well-known that \u03a9 (log\n            <jats:italic>N<\/jats:italic>\n            ) amortized blowup in memory accesses is necessary, where\n            <jats:italic>N<\/jats:italic>\n            is the size of the logical memory. This was shown in Goldreich and Ostrovksy\u2019s original ORAM work for statistical security and in a somewhat restricted model (the so-called\n            <jats:italic>balls-and-bins<\/jats:italic>\n            model), and recently by Larsen and Nielsen (CRYPTO\u00a0\u201918) for computational security.\n          <\/jats:p>\n          <jats:p>\n            A long-standing open question is whether there exists an\n            <jats:italic>optimal<\/jats:italic>\n            ORAM construction that matches the aforementioned logarithmic lower bounds (without making large memory word assumptions, and assuming a constant number of CPU registers). In this article, we resolve this problem and present the first secure ORAM with\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>N<\/jats:italic>\n            ) amortized blowup, assuming one-way functions. Our result is inspired by and non-trivially improves on the recent beautiful work of Patel et\u00a0al. (FOCS \u201918) who gave a construction with\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>N<\/jats:italic>\n            \u22c5 log log\n            <jats:italic>N<\/jats:italic>\n            ) amortized blowup, assuming one-way functions.\n          <\/jats:p>\n          <jats:p>\n            One of our building blocks of independent interest is a linear-time deterministic oblivious algorithm for tight compaction: Given an array of\n            <jats:italic>n<\/jats:italic>\n            elements where some elements are marked, we permute the elements in the array so that all marked elements end up in the front of the array. Our\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) algorithm improves the previously best-known deterministic or randomized algorithms whose running time is\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            \u22c5 log\n            <jats:italic>n<\/jats:italic>\n            ) or\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            \u22c5 log log\n            <jats:italic>n<\/jats:italic>\n            ), respectively.\n          <\/jats:p>","DOI":"10.1145\/3566049","type":"journal-article","created":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T12:20:53Z","timestamp":1665058853000},"page":"1-70","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["OptORAMa: Optimal Oblivious RAM"],"prefix":"10.1145","volume":"70","author":[{"given":"Gilad","family":"Asharov","sequence":"first","affiliation":[{"name":"Bar-Ilan University, Ramat-Gan, Israel"}]},{"given":"Ilan","family":"Komargodski","sequence":"additional","affiliation":[{"name":"Hebrew University and NTT Research, Jerusalem, Israel"}]},{"given":"Wei-Kai","family":"Lin","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY"}]},{"given":"Kartik","family":"Nayak","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC"}]},{"given":"Enoch","family":"Peserico","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi di Padova, Padova (PD), Italy"}]},{"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY"}]}],"member":"320","published-online":{"date-parts":[[2022,12,19]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808726"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225173"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_3_3_5_2","volume-title":"Proceedings of the ACM STOC","author":"Arora Sanjeev","year":"1990","unstructured":"Sanjeev Arora, Frank Thomson Leighton, and Bruce M. Maggs. 1990. On-line algorithms for path selection in a nonblocking network (extended abstract). In Proceedings of the ACM STOC."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1468075.1468121"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813649"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840761"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_21"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s001459910006"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959888"},{"key":"e_1_3_3_12_2","volume-title":"Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security","author":"Chan Hubert","year":"2017","unstructured":"Hubert Chan, Kai-Min Chung, and Elaine Shi. 2017. On the depth of oblivious parallel ORAM. In Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security."},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70694-8_23"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.143"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-03810-6_23"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70503-3_3"},{"key":"e_1_3_3_17_2","volume-title":"Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security","author":"Chung Kai-Min","year":"2014","unstructured":"Kai-Min Chung, Zhenming Liu, and Rafael Pass. 2014. Statistically-secure ORAM with \\(\\tilde{O}(\\log ^2n)\\) overhead. In Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security."},{"key":"e_1_3_3_18_2","unstructured":"Jean claude Paul and Wilhelm Simon. 1980. Decision trees and random access machines. Logic and Algorithmic 30 (1980) 331\u2013340."},{"key":"e_1_3_3_19_2","first-page":"428","volume-title":"Introduction to Algorithms (3rd ed.)","author":"Cormen T. H.","year":"2009","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press, 428\u2013436."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19571-6_10"},{"key":"e_1_3_3_21_2","article-title":"Alibi: A Flaw in Cuckoo-Hashing based Hierarchical ORAM Schemes and a Solution","author":"Falk Brett Hemenway","year":"2020","unstructured":"Brett Hemenway Falk, Daniel Noble, and Rafail Ostrovsky. 2020. Alibi: A Flaw in Cuckoo-Hashing based Hierarchical ORAM Schemes and a Solution. Cryptology ePrint Archive, Report 2020\/997. (2020). Retrieved from https:\/\/eprint.iacr.org\/2020\/997.","journal-title":"Cryptology ePrint Archive, Report 2020\/997"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0077-8"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316337"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12155"},{"key":"e_1_3_3_25_2","volume-title":"Statistical Tables for Biological, Agricultural and Medical Research","author":"Fisher R. A.","year":"1975","unstructured":"R. A. Fisher and F. Yates. 1975. Statistical Tables for Biological, Agricultural and Medical Research. Oliver and Boyd. Retrieved October 1, 2020 from https:\/\/books.google.com\/books?id=KWBLPgAACAAJ."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2382536.2382540"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2694344.2694353"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90040-4"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-28166-7_9"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28416"},{"key":"e_1_3_3_31_2","volume-title":"The Foundations of Cryptography - Volume 2, Basic Applications","author":"Goldreich Oded","year":"2004","unstructured":"Oded Goldreich. 2004. The Foundations of Cryptography - Volume 2, Basic Applications. Cambridge University Press."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591830"},{"key":"e_1_3_3_34_2","doi-asserted-by":"crossref","first-page":"576","DOI":"10.1007\/978-3-642-22012-8_46","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Goodrich Michael T.","year":"2011","unstructured":"Michael T. Goodrich and Michael Mitzenmacher. 2011. Privacy-preserving access of outsourced data via oblivious RAM simulation. In International Colloquium on Automata, Languages, and Programming. 576\u2013587."},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2046660.2046680"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095130"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90097-H"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579322"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.5555\/1957995.1958011"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.13"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96881-0_18"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/s002240000068"},{"key":"e_1_3_3_44_2","unstructured":"Zongpeng Li and Baochun Li. 2004. Network coding: The case of multiple unicast sessions. Allerton Conference on Communications 16 8 (2004)"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.148"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2015.29"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_22"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516692"},{"issue":"4","key":"e_1_3_3_49_2","first-page":"71","article-title":"Explicit constructions of concentrators","volume":"9","author":"Margulis Grigorii Aleksandrovich","year":"1973","unstructured":"Grigorii Aleksandrovich Margulis. 1973. Explicit constructions of concentrators. Problemy Peredachi Informatsii 9, 4 (1973), 71\u201380.","journal-title":"Problemy Peredachi Informatsii"},{"key":"e_1_3_3_50_2","first-page":"554","volume-title":"Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science STACS","author":"Mitchell John C.","year":"2014","unstructured":"John C. Mitchell and Joe Zimmerman. 2014. Data-oblivious data structures. In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science STACS. 554\u2013565."},{"key":"e_1_3_3_51_2","first-page":"128","volume-title":"Proceedings of the Conference on the Theory and Application of Cryptology","author":"Naor Moni","year":"1989","unstructured":"Moni Naor. 1989. Bit commitment using pseudo-randomness. In Proceedings of the Conference on the Theory and Application of Cryptology. 128\u2013136."},{"key":"e_1_3_3_52_2","first-page":"294","volume-title":"Proceedings of the 29th Annual ACM Symposium on Theory of Computing","author":"Ostrovsky Rafail","year":"1997","unstructured":"Rafail Ostrovsky and Victor Shoup. 1997. Private information storage. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing. 294\u2013303."},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00087"},{"key":"e_1_3_3_55_2","volume-title":"Proceedings of the 7th International Teletraffic Conference","author":"Pinsker Mark S.","year":"1973","unstructured":"Mark S. Pinsker. 1973. On the complexity of a concentrator. In Proceedings of the 7th International Teletraffic Conference."},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1137\/0206022"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0005"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/2485922.2485971"},{"key":"e_1_3_3_59_2","first-page":"197","volume-title":"Proceedings of the International Conference on The Theory and Application of Cryptology and Information Security","author":"Shi Elaine","year":"2011","unstructured":"Elaine Shi, T.-H. Hubert Chan, Emil Stefanov, and Mingfei Li. 2011. Oblivious RAM with \\(O((\\log N)^3)\\) worst-case cost. In Proceedings of the International Conference on The Theory and Application of Cryptology and Information Security. 197\u2013214."},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2013.25"},{"key":"e_1_3_3_61_2","volume-title":"Proceedings of the 19th Annual Network and Distributed System Security Symposium","author":"Stefanov Emil","year":"2012","unstructured":"Emil Stefanov, Elaine Shi, and Dawn Xiaodong Song. 2012. Towards practical oblivious RAM. In Proceedings of the 19th Annual Network and Distributed System Security Symposium."},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516660"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80041-4"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813634"},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660365"},{"key":"e_1_3_3_66_2","unstructured":"Wikipedia. Bitonic sorter. (n. d.). Retrieved September 22 2019 from https:\/\/en.wikipedia.org\/w\/index.php?title=Bitonic_sorter."},{"key":"e_1_3_3_67_2","unstructured":"Wikipedia. Sorting network. (n. d.). Retrieved February 14 2020 from https:\/\/en.wikipedia.org\/wiki\/Sorting_network."},{"key":"e_1_3_3_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382299"},{"key":"e_1_3_3_69_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2016.21"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3566049","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3566049","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3566049","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:32Z","timestamp":1750183712000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3566049"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,19]]},"references-count":68,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2,28]]}},"alternative-id":["10.1145\/3566049"],"URL":"https:\/\/doi.org\/10.1145\/3566049","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,19]]},"assertion":[{"value":"2020-03-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-06","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-12-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}