{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:54:10Z","timestamp":1764996850266,"version":"3.41.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>We consider the problem of storing a large file on a remote and unreliable server. To verify that the file has not been corrupted, a user could store a small private (randomized) \u201cfingerprint\u201d on his own computer. This is the setting for the well-studied authentication problem in cryptography, and the required fingerprint size is well understood. We study the problem of sublinear authentication: suppose the user would like to encode and store the file in a way that allows him to verify that it has not been corrupted, but without reading the entire file. If the user only wants to read<jats:italic>q<\/jats:italic>bits of the file, how large does the size<jats:italic>s<\/jats:italic>of the private fingerprint need to be? We define this problem formally, and show a tight lower bound on the relationship between<jats:italic>s<\/jats:italic>and<jats:italic>q<\/jats:italic>when the adversary is not computationally bounded, namely:<jats:italic>s<\/jats:italic>\u00d7<jats:italic>q<\/jats:italic>= \u03a9(<jats:italic>n<\/jats:italic>), where<jats:italic>n<\/jats:italic>is the file size. This is an easier case of the online memory checking problem, introduced by Blum et al. [1991], and hence the same (tight) lower bound applies also to that problem.<\/jats:p><jats:p>It was previously shown that, when the adversary is computationally bounded, under the assumption that one-way functions exist, it is possible to construct much better online memory checkers. The same is also true for sublinear authentication schemes. We show that the existence of one-way functions is also a necessary condition: even slightly breaking the<jats:italic>s<\/jats:italic>\u00d7<jats:italic>q<\/jats:italic>= \u03a9(<jats:italic>n<\/jats:italic>) lower bound in a computational setting implies the existence of one-way functions.<\/jats:p>","DOI":"10.1145\/1462153.1462155","type":"journal-article","created":{"date-parts":[[2009,2,4]],"date-time":"2009-02-04T13:01:58Z","timestamp":1233752518000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":55,"title":["The complexity of online memory checking"],"prefix":"10.1145","volume":"56","author":[{"given":"Moni","family":"Naor","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy N.","family":"Rothblum","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, Massachusetts"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,2,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509981"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Ateniese G. Burns R. Curtmola R. Herring J. Kissner L. Peterson Z. and Song D. 2007. Provable data possession at untrusted stores. Cryptology ePrint Archive Report 2007\/202. Ateniese G. Burns R. Curtmola R. Herring J. Kissner L. Peterson Z. and Song D. 2007. Provable data possession at untrusted stores. Cryptology ePrint Archive Report 2007\/202.","DOI":"10.1145\/1315245.1315318"},{"volume-title":"Proceedings of the IEEE Conference on Computational Complexity. IEEE Computer Society Press","author":"Babai L.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.03.002"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301277"},{"volume-title":"Proceedings of CRYPTO. 216--233","author":"Bellare M.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225080"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Bellare M. Impagliazzo R. and Naor M. 1997. Does parallel repetition lower the error in computationally sound protocols&quest; In Proceedings of the Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press Los Alamitos CA 374--383. Bellare M. Impagliazzo R. and Naor M. 1997. Does parallel repetition lower the error in computationally sound protocols&quest; In Proceedings of the Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press Los Alamitos CA 374--383.","DOI":"10.1109\/SFCS.1997.646126"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007361"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060631"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Blum M. Evans W. S. Gemmell P. Kannan S. and Naor M. 1994. Checking the correctness of memories. Algorithmica 12 2\/3 225--244. Blum M. Evans W. S. Gemmell P. Kannan S. and Naor M. 1994. Checking the correctness of memories. Algorithmica 12 2\/3 225--244.","DOI":"10.1007\/BF01185212"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200880"},{"key":"e_1_2_1_13_1","unstructured":"Bowers K. D. Juels A. and Oprea A. 2008. Proofs of retrievability: Theory and implementation. Cryptology ePrint Archive Report 2008\/175. Bowers K. D. Juels A. and Oprea A. 2008. Proofs of retrievability: Theory and implementation. Cryptology ePrint Archive Report 2008\/175."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293350"},{"volume-title":"Proceedings of the IEEE Symposium on Security and Privacy. IEEE Computer Society Press","author":"Clarke D. E.","key":"e_1_2_1_15_1"},{"volume-title":"Proceedings of EUROCRYPT. 122--138","author":"Crescenzo G.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Dwork C. Naor M. Rothblum G. N. and Vaikuntanathan V. 2009. How efficient can memory checking be&quest; In Proceedings of the Theory of Cryptography Conference (TCC) to appear. Dwork C. Naor M. Rothblum G. N. and Vaikuntanathan V. 2009. How efficient can memory checking be&quest; In Proceedings of the Theory of Cryptography Conference (TCC) to appear.","DOI":"10.1007\/978-3-642-00457-5_30"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-001-0006-7"},{"volume-title":"Proceedings of ISTCS. 190--198","author":"Friedl K.","key":"e_1_2_1_19_1"},{"volume-title":"Proceedings of CRYPTO. 355--367","author":"Gemmell P.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1974.tb02751.x"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28416"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Goldreich O. 2001. The Foundations of Cryptography \u2014 Volume 1. Cambridge University Press Cambridge MA. Goldreich O. 2001. The Foundations of Cryptography \u2014 Volume 1. Cambridge University Press Cambridge MA.","DOI":"10.1017\/CBO9780511546891"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6503"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1162349.1162351"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/829497.829786"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63483"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1315245.1315317"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1972.1054893"},{"key":"e_1_2_1_32_1","unstructured":"Katz J. and Koo C.-Y. 2005. On constructing universal one-way hash functions from arbitrary one-way functions. Cryptology ePrint Archive Report 2005\/328. Katz J. and Koo C.-Y. 2005. On constructing universal one-way hash functions from arbitrary one-way functions. Cryptology ePrint Archive Report 2005\/328."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335315"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129782"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050018"},{"volume-title":"Proceedings of the Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"Kushilevitz E.","key":"e_1_2_1_36_1"},{"volume-title":"Proceedings of EUROCRYPT. 104--121","author":"Kushilevitz E.","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365746"},{"volume-title":"Proceedings of TCC. 1--16","author":"Micali S.","key":"e_1_2_1_39_1"},{"volume-title":"Proceedings of CRYPTO. 41--62","author":"Naor D.","key":"e_1_2_1_40_1"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143926"},{"volume-title":"Proceedings of CRYPTO. 214--231","author":"Naor M.","key":"e_1_2_1_43_1"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73011"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.238004"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100289"},{"volume-title":"Proceedings of ISTCS. 3--17","author":"Ostrovsky R.","key":"e_1_2_1_47_1"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100269"},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Shacham H. and Waters B. 2008. Compact proofs of retrievability. Cryptology ePrint Archive Report 2008\/073. Shacham H. and Waters B. 2008. Compact proofs of retrievability. Cryptology ePrint Archive Report 2008\/073.","DOI":"10.1007\/978-3-540-89255-7_7"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90033-7"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804414"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1462153.1462155","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1462153.1462155","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:14Z","timestamp":1750253414000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1462153.1462155"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1145\/1462153.1462155"],"URL":"https:\/\/doi.org\/10.1145\/1462153.1462155","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2009,1]]},"assertion":[{"value":"2006-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-02-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}