{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:05:31Z","timestamp":1750309531405,"version":"3.41.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T00:00:00Z","timestamp":1743033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000185","name":"DARPA","doi-asserted-by":"crossref","award":["HR00112020023"],"award-info":[{"award-number":["HR00112020023"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF","award":["CNS-2154149, DGE-2141064"],"award-info":[{"award-number":["CNS-2154149, DGE-2141064"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2025,4,30]]},"abstract":"We study the complexity of memory checkers with computational security and prove the first general tight lower bound.<\/jats:p>\n \n Memory checkers, first introduced over 30 years ago by Blum, Evans, Gemmel, Kannan, and Naor (FOCS\u00a0\u201991, Algorithmica \u201994), allow a user to store and maintain a large memory on a remote and unreliable server by using small trusted local storage. The user can issue instructions to the server and after every instruction, obtain either the correct value or a failure (but not an incorrect answer) with high probability. The main complexity measure of interest is the size of the local storage and the number of queries the memory checker makes upon every logical instruction. The most efficient known construction has query complexity\n \n \\(O(\\log n\/\\log \\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and local space proportional to a computational security parameter, assuming one-way functions, where\n n<\/jats:italic>\n is the logical memory size. Dwork, Naor, Rothblum, and Vaikuntanathan (TCC \u201909) showed that for a restricted class of \u201cdeterministic and non-adaptive\u201d memory checkers, this construction is optimal, up to constant factors. However, going beyond the small class of deterministic and non-adaptive constructions has remained a major open problem.\n <\/jats:p>\n \n In this work, we fully resolve the complexity of memory checkers by showing that\n any<\/jats:italic>\n construction with local space\n p<\/jats:italic>\n and query complexity\n q<\/jats:italic>\n must satisfy\n \n \\(\\begin{equation*}\np \\ge \\frac{n}{(\\log n)^{O(q)}} \\;.\n\\end{equation*}\\)<\/jats:tex-math>\n <\/jats:disp-formula>\n This implies, as a special case, that\n \n \\(q\\ge \\Omega (\\log n\/\\log \\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n in any scheme, assuming that\n \n \\(p\\le n^{1-\\varepsilon }\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for\n \n \\(\\varepsilon \\gt 0\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . The bound applies to any scheme with computational security, completeness\n \n \\(2\/3\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , and inverse polynomial in\n n<\/jats:italic>\n soundness (all of which make our lower bound only stronger). We further extend the lower bound to schemes where the read complexity\n \n \\(q_r\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and write complexity\n \n \\(q_w\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n differ. For instance, we show the tight bound that if\n \n \\(q_r=O(1)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(p\\le n^{1-\\varepsilon }\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for\n \n \\(\\varepsilon \\gt 0\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , then\n \n \\(q_w\\ge n^{\\Omega (1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . This is the first lower bound, for any non-trivial class of constructions, showing a read-write query complexity trade-off.\n <\/jats:p>\n Our proof is via a delicate compression argument showing that a \u201ctoo good to be true\u201d memory checker can be used to compress random bits of information. We draw inspiration from tools recently developed for lower bounds for relaxed locally decodable codes. However, our proof itself significantly departs from these works, necessitated by the differences between settings.<\/jats:p>","DOI":"10.1145\/3707202","type":"journal-article","created":{"date-parts":[[2024,12,17]],"date-time":"2024-12-17T11:23:58Z","timestamp":1734434638000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Memory Checking Requires Logarithmic Overhead"],"prefix":"10.1145","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-0360-8129","authenticated-orcid":false,"given":"Elette","family":"Boyle","sequence":"first","affiliation":[{"name":"Reichman University, Herzliya, Israel and NTT Research Inc, Sunnyvale, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1647-2112","authenticated-orcid":false,"given":"Ilan","family":"Komargodski","sequence":"additional","affiliation":[{"name":"Hebrew University of Jerusalem, Jerusalem, Israel and NTT Research Inc, Sunnyvale, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0555-4200","authenticated-orcid":false,"given":"Neekon","family":"Vafa","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,3,27]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","unstructured":"Gilad Asharov Ilan Komargodski Wei-Kai Lin Kartik Nayak Enoch Peserico and Elaine Shi. 2023. OptORAMa: Optimal Oblivious RAM. J. ACM 70 1 (2023) 4:1\u20134:70. 10.1145\/3566049","DOI":"10.1145\/3566049"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","unstructured":"Gilad Asharov Ilan Komargodski Wei-Kai Lin and Elaine Shi. 2023. Oblivious RAM with worst-case logarithmic overhead. J. Cryptol. 36 2 (2023) 7. 10.1007\/S00145-023-09447-5","DOI":"10.1007\/S00145-023-09447-5"},{"key":"e_1_3_3_4_2","first-page":"598","volume-title":"Proceedings of the 2007 ACM Conference on Computer and Communications Security, CCS 2007, Alexandria, VA, USA, October 28\u201331, 2007","author":"Ateniese Giuseppe","year":"2007","unstructured":"Giuseppe Ateniese, Randal C. Burns, Reza Curtmola, Joseph Herring, Lea Kissner, Zachary N. J. Peterson, and Dawn Xiaodong Song. 2007. Provable data possession at untrusted stores. In Proceedings of the 2007 ACM Conference on Computer and Communications Security, CCS 2007, Alexandria, VA, USA, October 28\u201331, 2007, Peng Ning, Sabrina De Capitani di Vimercati, and Paul F. Syverson (Eds.). ACM, 598\u2013609. 10.1145\/1315245.1315318"},{"key":"e_1_3_3_5_2","first-page":"470","volume-title":"Advances in Cryptology - CRYPTO \u201997, 17th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17\u201321, 1997, Proceedings (Lecture Notes in Computer Science)","volume":"1294","author":"Bellare Mihir","year":"1997","unstructured":"Mihir Bellare and Phillip Rogaway. 1997. Collision-resistant hashing: Towards making UOWHFs practical. In Advances in Cryptology - CRYPTO \u201997, 17th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17\u201321, 1997, Proceedings (Lecture Notes in Computer Science), Burton S. Kaliski Jr. (Ed.), Vol. 1294. Springer, 470\u2013484. 10.1007\/BFB0052256"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","unstructured":"Manuel Blum William S. Evans Peter Gemmell Sampath Kannan and Moni Naor. 1994. Checking the correctness of memories. Algorithmica 12 2\/3 (1994) 225\u2013244. 10.1007\/BF01185212","DOI":"10.1007\/BF01185212"},{"key":"e_1_3_3_7_2","first-page":"649","volume-title":"Advances in Cryptology - CRYPTO 2021-41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16\u201320, 2021, Proceedings, Part I (Lecture Notes in Computer Science)","volume":"12825","author":"Boneh Dan","year":"2021","unstructured":"Dan Boneh, Justin Drake, Ben Fisch, and Ariel Gabizon. 2021. Halo infinite: Proof-carrying data from additive polynomial commitments. In Advances in Cryptology - CRYPTO 2021-41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16\u201320, 2021, Proceedings, Part I (Lecture Notes in Computer Science), Tal Malkin and Chris Peikert (Eds.), Vol. 12825. Springer, 649\u2013680. 10.1007\/978-3-030-84242-0_23"},{"key":"e_1_3_3_8_2","first-page":"427","volume-title":"Advances in Cryptology - EUROCRYPT 2022-41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part II (Lecture Notes in Computer Science)","volume":"13276","author":"Bootle Jonathan","year":"2022","unstructured":"Jonathan Bootle, Alessandro Chiesa, Yuncong Hu, and Michele Orr\u00f9. 2022. Gemini: Elastic SNARKs for diverse environments. In Advances in Cryptology - EUROCRYPT 2022-41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part II (Lecture Notes in Computer Science), Orr Dunkelman and Stefan Dziembowski (Eds.), Vol. 13276. Springer, 427\u2013457. 10.1007\/978-3-031-07085-3_15"},{"key":"e_1_3_3_9_2","first-page":"357","volume-title":"Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14\u201316, 2016","author":"Boyle Elette","year":"2016","unstructured":"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, Cambridge, MA, USA, January 14\u201316, 2016, Madhu Sudan (Ed.). ACM, 357\u2013368. 10.1145\/2840728.2840761"},{"key":"e_1_3_3_10_2","first-page":"65","volume-title":"Advances in Cryptology - ASIACRYPT 2021-27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6\u201310, 2021, Proceedings, Part III (Lecture Notes in Computer Science)","volume":"13092","author":"B\u00fcnz Benedikt","year":"2021","unstructured":"Benedikt B\u00fcnz, Mary Maller, Pratyush Mishra, Nirvan Tyagi, and Psi Vesely. 2021. Proofs for inner pairing products and applications. In Advances in Cryptology - ASIACRYPT 2021-27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6\u201310, 2021, Proceedings, Part III (Lecture Notes in Computer Science), Mehdi Tibouchi and Huaxiong Wang (Eds.), Vol. 13092. Springer, 65\u201397. 10.1007\/978-3-030-92078-4_3"},{"key":"e_1_3_3_11_2","first-page":"457","volume-title":"Theory of Cryptography - 18th International Conference, TCC 2020, Durham, NC, USA, November 16\u201319, 2020, Proceedings, Part I (Lecture Notes in Computer Science)","volume":"12550","author":"Cash David","year":"2020","unstructured":"David Cash, Andrew Drucker, and Alexander Hoover. 2020. A lower bound for one-round Oblivious RAM. In Theory of Cryptography - 18th International Conference, TCC 2020, Durham, NC, USA, November 16\u201319, 2020, Proceedings, Part I (Lecture Notes in Computer Science), Rafael Pass and Krzysztof Pietrzak (Eds.), Vol. 12550. Springer, 457\u2013485. 10.1007\/978-3-030-64375-1_16"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","unstructured":"David Cash Alptekin K\u00fcp\u00e7\u00fc and Daniel Wichs. 2017. Dynamic proofs of retrievability via Oblivious RAM. J. Cryptol. 30 1 (2017) 22\u201357. 10.1007\/S00145-015-9216-2","DOI":"10.1007\/S00145-015-9216-2"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2005.24"},{"key":"e_1_3_3_14_2","unstructured":"Victor Costan and Srinivas Devadas. 2016. Intel SGX explained. IACR Cryptol. ePrint Arch. (2016) 86. http:\/\/eprint.iacr.org\/2016\/086"},{"key":"e_1_3_3_15_2","first-page":"649","volume-title":"Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15\u201319, 2010. Proceedings (Lecture Notes in Computer Science)","volume":"6223","author":"De Anindya","year":"2010","unstructured":"Anindya De, Luca Trevisan, and Madhur Tulsiani. 2010. Time space tradeoffs for attacks against one-way functions and PRGs. In Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15\u201319, 2010. Proceedings (Lecture Notes in Computer Science), Tal Rabin (Ed.), Vol. 6223. Springer, 649\u2013665. 10.1007\/978-3-642-14623-7_35"},{"key":"e_1_3_3_16_2","first-page":"503","volume-title":"Theory of Cryptography, 6th Theory of Cryptography Conference, TCC 2009, San Francisco, CA, USA, March 15\u201317, 2009. Proceedings (Lecture Notes in Computer Science)","volume":"5444","author":"Dwork Cynthia","year":"2009","unstructured":"Cynthia Dwork, Moni Naor, Guy N. Rothblum, and Vinod Vaikuntanathan. 2009. How efficient can memory checking be?. In Theory of Cryptography, 6th Theory of Cryptography Conference, TCC 2009, San Francisco, CA, USA, March 15\u201317, 2009. Proceedings (Lecture Notes in Computer Science), Omer Reingold (Ed.), Vol. 5444. Springer, 503\u2013520. 10.1007\/978-3-642-00457-5_30"},{"key":"e_1_3_3_17_2","first-page":"74:1\u201374:20","volume-title":"51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) (Leibniz International Proceedings in Informatics (LIPIcs))","volume":"297","author":"Goldberg Guy","year":"2024","unstructured":"Guy Goldberg. 2024. Linear relaxed locally decodable and correctable codes do not need adaptivity and two-sided error. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) (Leibniz International Proceedings in Informatics (LIPIcs)), Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson (Eds.), Vol. 297. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 74:1\u201374:20. 10.4230\/LIPIcs.ICALP.2024.74"},{"key":"e_1_3_3_18_2","first-page":"182","volume-title":"Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, NY, USA","author":"Goldreich Oded","year":"1987","unstructured":"Oded Goldreich. 1987. Towards a theory of software protection and simulation by Oblivious RAMs. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, NY, USA, Alfred V. Aho (Ed.). ACM, 182\u2013194. 10.1145\/28395.28416"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891"},{"key":"e_1_3_3_20_2","unstructured":"Oded Goldreich. 2023. On the lower bound on the length of relaxed locally decodable codes. Electron. Colloquium Comput. Complex. TR23-064 (2023). ECCC:TR23-064https:\/\/eccc.weizmann.ac.il\/report\/2023\/064"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","unstructured":"Oded Goldreich Shafi Goldwasser and Silvio Micali. 1986. How to construct random functions. J. ACM 33 4 (1986) 792\u2013807. 10.1145\/6490.6503","DOI":"10.1145\/6490.6503"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","unstructured":"Oded Goldreich and Rafail Ostrovsky. 1996. Software protection and simulation on Oblivious RAMs. J. ACM 43 3 (1996) 431\u2013473. 10.1145\/233551.233553","DOI":"10.1145\/233551.233553"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/11693383_7"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","unstructured":"Johan H\u00e5stad Russell Impagliazzo Leonid A. Levin and Michael Luby. 1999. A Pseudorandom generator from any one-way function. SIAM J. Comput. 28 4 (1999) 1364\u20131396. 10.1137\/S0097539793244708","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","unstructured":"Johan H\u00e5stad Benjamin Rossman Rocco A. Servedio and Li-Yang Tan. 2017. An average-case depth hierarchy theorem for Boolean circuits. J. ACM 64 5 Article 35 (Aug.2017) 27 pages. 10.1145\/3095799","DOI":"10.1145\/3095799"},{"key":"e_1_3_3_26_2","first-page":"584","volume-title":"Proceedings of the 2007 ACM Conference on Computer and Communications Security, CCS 2007, Alexandria, VA, USA, October 28\u201331, 2007","author":"Juels Ari","year":"2007","unstructured":"Ari Juels and Burton S. Kaliski Jr.2007. PORs: Proofs of retrievability for large files. In Proceedings of the 2007 ACM Conference on Computer and Communications Security, CCS 2007, Alexandria, VA, USA, October 28\u201331, 2007, Peng Ning, Sabrina De Capitani di Vimercati, and Paul F. Syverson (Eds.). ACM, 584\u2013597. 10.1145\/1315245.1315317"},{"key":"e_1_3_3_27_2","unstructured":"Jonathan Katz and Chiu-Yuen Koo. 2005. On constructing universal one-way hash functions from arbitrary one-way functions. IACR Cryptol. ePrint Arch. (2005) 328. http:\/\/eprint.iacr.org\/2005\/328"},{"key":"e_1_3_3_28_2","first-page":"579","volume-title":"Advances in Cryptology - CRYPTO 2021-41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16\u201320, 2021, Proceedings, Part IV (Lecture Notes in Computer Science)","volume":"12828","author":"Komargodski Ilan","year":"2021","unstructured":"Ilan Komargodski and Wei-Kai Lin. 2021. A logarithmic lower bound for Oblivious RAM (for all parameters). In Advances in Cryptology - CRYPTO 2021-41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16\u201320, 2021, Proceedings, Part IV (Lecture Notes in Computer Science), Tal Malkin and Chris Peikert (Eds.), Vol. 12828. Springer, 579\u2013609. 10.1007\/978-3-030-84259-8_20"},{"key":"e_1_3_3_29_2","first-page":"523","volume-title":"Advances in Cryptology - CRYPTO 2018-38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19\u201323, 2018, Proceedings, Part II (Lecture Notes in Computer Science)","volume":"10992","author":"Larsen Kasper Green","year":"2018","unstructured":"Kasper Green Larsen and Jesper Buus Nielsen. 2018. Yes, there is an Oblivious RAM lower bound!. In Advances in Cryptology - CRYPTO 2018-38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19\u201323, 2018, Proceedings, Part II (Lecture Notes in Computer Science), Hovav Shacham and Alexandra Boldyreva (Eds.), Vol. 10992. Springer, 523\u2013542. 10.1007\/978-3-319-96881-0_18"},{"key":"e_1_3_3_30_2","unstructured":"Kasper Green Larsen Rasmus Pagh Giuseppe Persiano Toniann Pitassi Kevin Yeo and Or Zamir. 2024. Optimal non-adaptive cell probe dictionaries and hashing. arxiv:cs.DS\/2308.16042https:\/\/arxiv.org\/abs\/2308.16042"},{"key":"e_1_3_3_31_2","first-page":"199","volume-title":"Proceedings of the 11th USENIX Conference on File and Storage Technologies, FAST 2013, San Jose, CA, USA, February 12\u201315, 2013","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. In Proceedings of the 11th USENIX Conference on File and Storage Technologies, FAST 2013, San Jose, CA, USA, February 12\u201315, 2013, Keith A. Smith and Yuanyuan Zhou (Eds.). USENIX, 199\u2013214. https:\/\/www.usenix.org\/conference\/fast13\/technical-sessions\/presentation\/lorch"},{"key":"e_1_3_3_32_2","first-page":"436","volume-title":"Theory of Cryptography - 21st International Conference, TCC 2023, Taipei, Taiwan, November 29 - December 2, 2023, Proceedings, Part II (Lecture Notes in Computer Science)","volume":"14370","author":"Mathialagan Surya","year":"2023","unstructured":"Surya Mathialagan. 2023. Memory checking for parallel RAMs. In Theory of Cryptography - 21st International Conference, TCC 2023, Taipei, Taiwan, November 29 - December 2, 2023, Proceedings, Part II (Lecture Notes in Computer Science), Guy N. Rothblum and Hoeteck Wee (Eds.), Vol. 14370. Springer, 436\u2013464. 10.1007\/978-3-031-48618-0_15"},{"key":"e_1_3_3_33_2","first-page":"95","volume-title":"Advances in Cryptology - CRYPTO 2023-43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20\u201324, 2023, Proceedings, Part IV (Lecture Notes in Computer Science)","volume":"14084","author":"Mathialagan Surya","year":"2023","unstructured":"Surya Mathialagan and Neekon Vafa. 2023. MacORAMa: Optimal Oblivious RAM with integrity. In Advances in Cryptology - CRYPTO 2023-43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20\u201324, 2023, Proceedings, Part IV (Lecture Notes in Computer Science), Helena Handschuh and Anna Lysyanskaya (Eds.), Vol. 14084. Springer, 95\u2013127. 10.1007\/978-3-031-38551-3_4"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","unstructured":"Moni Naor and Guy N. Rothblum. 2009. The complexity of online memory checking. J. ACM 56 1 (2009) 2:1\u20132:46. 10.1145\/1462153.1462155","DOI":"10.1145\/1462153.1462155"},{"key":"e_1_3_3_35_2","first-page":"33","volume-title":"Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14\u201317, 1989, Seattle, WA, USA","author":"Naor Moni","year":"1989","unstructured":"Moni Naor and Moti Yung. 1989. Universal one-way hash functions and their cryptographic applications. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14\u201317, 1989, Seattle, WA, USA, David S. Johnson (Ed.). ACM, 33\u201343. 10.1145\/73007.73011"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","unstructured":"Noam Nisan and Avi Wigderson. 1993. Rounds in communication complexity revisited. SIAM J. Comput. 22 1 (1993) 211\u2013219. 10.1137\/0222016","DOI":"10.1137\/0222016"},{"key":"e_1_3_3_37_2","volume-title":"Proceedings of the 16th USENIX Security Symposium, Boston, MA, USA, August 6\u201310, 2007","author":"Oprea Alina","year":"2007","unstructured":"Alina Oprea and Michael K. Reiter. 2007. Integrity checking in cryptographic file systems with constant trusted storage. In Proceedings of the 16th USENIX Security Symposium, Boston, MA, USA, August 6\u201310, 2007, Niels Provos (Ed.). USENIX Association. https:\/\/www.usenix.org\/conference\/16th-usenix-security-symposium\/integrity-checking-cryptographic-file-systems-constant"},{"key":"e_1_3_3_38_2","first-page":"514","volume-title":"Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13\u201317, 1990, Baltimore, MD, USA","author":"Ostrovsky Rafail","year":"1990","unstructured":"Rafail Ostrovsky. 1990. Efficient computation on Oblivious RAMs. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13\u201317, 1990, Baltimore, MD, USA, Harriet Ortiz (Ed.). ACM, 514\u2013523. 10.1145\/100216.100289"},{"key":"e_1_3_3_39_2","first-page":"2075","volume-title":"29th USENIX Security Symposium, USENIX Security 2020, August 12\u201314, 2020","author":"Ozdemir Alex","year":"2020","unstructured":"Alex Ozdemir, Riad S. Wahby, Barry Whitehat, and Dan Boneh. 2020. Scaling verifiable computation using efficient set accumulators. In 29th USENIX Security Symposium, USENIX Security 2020, August 12\u201314, 2020, Srdjan Capkun and Franziska Roesner (Eds.). USENIX Association, 2075\u20132092. https:\/\/www.usenix.org\/conference\/usenixsecurity20\/presentation\/ozdemir"},{"key":"e_1_3_3_40_2","unstructured":"Charalampos Papamanthou and Roberto Tamassia. 2011. Optimal and parallel online memory checking. Cryptology ePrint Archive (2011)."},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00087"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","unstructured":"Mihai Patrascu and Erik D. Demaine. 2006. Logarithmic lower bounds in the cell-probe model. SIAM J. Comput. 35 4 (2006) 932\u2013963. 10.1137\/S0097539705447256 arXiv:10.1137\/S0097539705447256","DOI":"10.1137\/S0097539705447256"},{"key":"e_1_3_3_43_2","first-page":"1","volume-title":"IEEE High Performance Extreme Computing Conference, HPEC 2013, Waltham, MA, USA, September 10\u201312, 2013","author":"Ren Ling","year":"2013","unstructured":"Ling Ren, Christopher W. Fletcher, Xiangyao Yu, Marten van Dijk, and Srinivas Devadas. 2013. Integrity verification for path Oblivious-RAM. In IEEE High Performance Extreme Computing Conference, HPEC 2013, Waltham, MA, USA, September 10\u201312, 2013. IEEE, 1\u20136. 10.1109\/HPEC.2013.6670339"},{"key":"e_1_3_3_44_2","first-page":"387","volume-title":"Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13\u201317, 1990, Baltimore, MD, USA","author":"Rompel John","year":"1990","unstructured":"John Rompel. 1990. One-way functions are necessary and sufficient for secure signatures. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13\u201317, 1990, Baltimore, MD, USA, Harriet Ortiz (Ed.). ACM, 387\u2013394. 10.1145\/100216.100269"},{"key":"e_1_3_3_45_2","first-page":"704","volume-title":"Advances in Cryptology - CRYPTO 2020-40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17\u201321, 2020, Proceedings, Part III (Lecture Notes in Computer Science)","volume":"12172","author":"Setty Srinath T. V.","year":"2020","unstructured":"Srinath T. V. Setty. 2020. Spartan: Efficient and general-purpose zkSNARKs without trusted setup. In Advances in Cryptology - CRYPTO 2020-40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17\u201321, 2020, Proceedings, Part III (Lecture Notes in Computer Science), Daniele Micciancio and Thomas Ristenpart (Eds.), Vol. 12172. Springer, 704\u2013737. 10.1007\/978-3-030-56877-1_25"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","unstructured":"Hovav Shacham and Brent Waters. 2013. Compact proofs of retrievability. J. Cryptol. 26 3 (2013) 442\u2013483. 10.1007\/S00145-012-9129-2","DOI":"10.1007\/S00145-012-9129-2"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","unstructured":"Emil Stefanov Marten van Dijk Elaine Shi T.-H. Hubert Chan Christopher W. Fletcher Ling Ren Xiangyao Yu and Srinivas Devadas. 2018. Path ORAM: An extremely simple Oblivious RAM protocol. J. ACM 65 4 (2018) 18:1\u201318:26. 10.1145\/3177872","DOI":"10.1145\/3177872"},{"key":"e_1_3_3_48_2","first-page":"926","volume-title":"2018 IEEE Symposium on Security and Privacy, SP 2018, Proceedings, 21\u201323 May 2018, San Francisco, CA, USA","author":"Wahby Riad S.","year":"2018","unstructured":"Riad S. Wahby, Ioanna Tzialla, Abhi Shelat, Justin Thaler, and Michael Walfish. 2018. Doubly-efficient zkSNARKs without trusted setup. In 2018 IEEE Symposium on Security and Privacy, SP 2018, Proceedings, 21\u201323 May 2018, San Francisco, CA, USA. IEEE Computer Society, 926\u2013943. 10.1109\/SP.2018.00060"},{"key":"e_1_3_3_49_2","first-page":"1820","volume-title":"Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, CCS 2023, Copenhagen, Denmark, November 26\u201330, 2023","author":"Wang Weijie","year":"2023","unstructured":"Weijie Wang, Yujie Lu, Charalampos Papamanthou, and Fan Zhang. 2023. The locality of memory checking. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, CCS 2023, Copenhagen, Denmark, November 26\u201330, 2023, Weizhi Meng, Christian Damsgaard Jensen, Cas Cremers, and Engin Kirda (Eds.). ACM, 1820\u20131834. 10.1145\/3576915.3623195"},{"key":"e_1_3_3_50_2","first-page":"733","volume-title":"Advances in Cryptology - CRYPTO 2019-39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18\u201322, 2019, Proceedings, Part III (Lecture Notes in Computer Science)","volume":"11694","author":"Xie Tiancheng","year":"2019","unstructured":"Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang, Charalampos Papamanthou, and Dawn Song. 2019. Libra: Succinct zero-knowledge proofs with optimal prover computation. In Advances in Cryptology - CRYPTO 2019-39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18\u201322, 2019, Proceedings, Part III (Lecture Notes in Computer Science), Alexandra Boldyreva and Daniele Micciancio (Eds.), Vol. 11694. Springer, 733\u2013764. 10.1007\/978-3-030-26954-8_24"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP40000.2020.00052"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3707202","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3707202","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:14Z","timestamp":1750295894000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3707202"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,27]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4,30]]}},"alternative-id":["10.1145\/3707202"],"URL":"https:\/\/doi.org\/10.1145\/3707202","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2025,3,27]]},"assertion":[{"value":"2024-03-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-13","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}