{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:07:11Z","timestamp":1750694831352,"version":"3.40.3"},"publisher-location":"Cham","reference-count":47,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031780103"},{"type":"electronic","value":"9783031780110"}],"license":[{"start":{"date-parts":[[2024,12,2]],"date-time":"2024-12-02T00:00:00Z","timestamp":1733097600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,12,2]],"date-time":"2024-12-02T00:00:00Z","timestamp":1733097600000},"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":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-78011-0_5","type":"book-chapter","created":{"date-parts":[[2024,12,1]],"date-time":"2024-12-01T20:01:58Z","timestamp":1733083318000},"page":"125-157","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Hamming Weight Proofs of\u00a0Proximity with\u00a0One-Sided Error"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7594-3896","authenticated-orcid":false,"given":"Gal","family":"Arnon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0479-9035","authenticated-orcid":false,"given":"Shany","family":"Ben-David","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8599-2472","authenticated-orcid":false,"given":"Eylon","family":"Yogev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,12,2]]},"reference":[{"key":"5_CR1","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/978-3-031-22318-1_16","volume-title":"TCC 2022","author":"G Arnon","year":"2022","unstructured":"Arnon, G., Bhangale, A., Chiesa, A., Yogev, E.: A toolbox for barriers on interactive oracle proofs. In: Kiltz, E., Vaikuntanathan, V. (eds.) TCC 2022. LNCS, vol. 13747, pp. 447\u2013466. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-22318-1_16"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Arnon, G., Chiesa, A., Fenzi, G., Yogev, E.: STIR: ReedSolomon proximity testing with fewer queries. Cryptology ePrint Archive, Paper 2024\/390 (2024)","DOI":"10.1007\/978-3-031-68403-6_12"},{"key":"5_CR3","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/978-3-031-07085-3_3","volume-title":"EUROCRYPT 2022","author":"G Arnon","year":"2022","unstructured":"Arnon, G., Chiesa, A., Yogev, E.: A PCP theorem for interactive proofs. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022. LNCS, vol. 13276, pp. 64\u201394. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-07085-3_3"},{"key":"5_CR4","unstructured":"Arnon, G., Chiesa, A., Yogev, E.: Hardness of approximation for stochastic problems via interactive oracle proofs. In: CCC 2022 (2022)"},{"key":"5_CR5","doi-asserted-by":"crossref","unstructured":"Arnon, G., Chiesa, A., Yogev, E.: IOPs with inverse polynomial soundness error. IEEE (2023)","DOI":"10.1109\/FOCS57990.2023.00050"},{"key":"5_CR6","unstructured":"Aaronson, H., Gur, T., Rajgopal, N., Rothblum, R.: Distribution-free proofs of proximity. In: Electronic Colloquium on Computational Complexity (2023)"},{"key":"5_CR7","doi-asserted-by":"publisher","unstructured":"Ben-Sasson, E.: Computational integrity with a public random string from quasi-linear PCPs. In: Coron, J.-S., Nielsen, J.B., et al. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 551\u2013579. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56617-7_19","DOI":"10.1007\/978-3-319-56617-7_19"},{"key":"5_CR8","unstructured":"Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Fast reed\u2013solomon interactive oracle proofs of proximity. In: ICALP 2018 (2018)"},{"key":"5_CR9","unstructured":"Ben-Sasson, E., Chiesa, A., Gabizon, A., Riabzev, M., Spooner, N.: Interactive oracle proofs with constant rate and query complexity. In: ICALP 2017 (2017)"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"Bootle, J., Cerulli, A., Ghadafi, E., Groth, J., Hajiabadi, M., Jakobsen, S.K.: Linear-time zero-knowledge proofs for arithmetic circuit satisfiability. In: ASIACRYPT 2017 (2017)","DOI":"10.1007\/978-3-319-70700-6_12"},{"key":"5_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/978-3-030-64378-2_2","volume-title":"Theory of Cryptography","author":"J Bootle","year":"2020","unstructured":"Bootle, J., Chiesa, A., Groth, J.: Linear-time arguments with sublinear verification from tensor codes. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12551, pp. 19\u201346. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64378-2_2"},{"key":"5_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-662-49099-0_2","volume-title":"Theory of Cryptography","author":"E Ben-Sasson","year":"2016","unstructured":"Ben-Sasson, E., Chiesa, A., Gabizon, A., Virza, M.: Quasi-linear size zero knowledge from linear-algebraic PCPs. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 33\u201364. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49099-0_2"},{"key":"5_CR13","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/978-3-031-07085-3_10","volume-title":"EUROCRYPT 2022","author":"J Bootle","year":"2022","unstructured":"Bootle, J., Chiesa, A., Liu, S.: Zero-knowledge IOPs with linear- time prover and polylogarithmic-time verifier. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022. LNCS, vol. 13276, pp. 275\u2013304. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-07085-3_10"},{"key":"5_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-662-53644-5_2","volume-title":"Theory of Cryptography","author":"E Ben-Sasson","year":"2016","unstructured":"Ben-Sasson, E., Chiesa, A., Spooner, N.: Interactive oracle proofs. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9986, pp. 31\u201360. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53644-5_2"},{"key":"5_CR15","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.P.: Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput. (2006)","DOI":"10.1137\/S0097539705446810"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Sampling algorithms: lower bounds and applications. In: Vitter, J.S., Spirakis, P.G., Yannakakis, M. (eds.) ACM (2001)","DOI":"10.1145\/380752.380810"},{"key":"5_CR17","unstructured":"Bordage, S., Nardi, J.: Interactive oracle proofs of proximity to algebraic geometry codes. In: CCC 2022 (2022)"},{"key":"5_CR18","unstructured":"Bafna, M., Vyas, N.: Imperfect gaps in gap-ETH and PCPs. In: Shpilka, A. (eds.) LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, vol. 137 (2019)"},{"key":"5_CR19","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Vaikuntanathan, V.: A note on perfect correctness by derandomization. J. Cryptol. (2022)","DOI":"10.1007\/s00145-022-09428-0"},{"key":"5_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-030-64378-2_3","volume-title":"Theory of Cryptography","author":"A Chiesa","year":"2020","unstructured":"Chiesa, A., Yogev, E.: Barriers for succinct arguments in the random oracle model. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12551, pp. 47\u201376. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64378-2_3"},{"key":"5_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1007\/978-3-030-84242-0_25","volume-title":"Advances in Cryptology \u2013 CRYPTO 2021","author":"A Chiesa","year":"2021","unstructured":"Chiesa, A., Yogev, E.: Subquadratic SNARGs in the random oracle model. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12825, pp. 711\u2013741. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-84242-0_25"},{"key":"5_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/978-3-030-90459-3_14","volume-title":"Theory of Cryptography","author":"A Chiesa","year":"2021","unstructured":"Chiesa, A., Yogev, E.: Tight security bounds for Micali\u2019s SNARGs. In: Nissim, K., Waters, B. (eds.) TCC 2021. LNCS, vol. 13042, pp. 401\u2013434. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-90459-3_14"},{"key":"5_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/978-3-540-24676-3_21","volume-title":"Advances in Cryptology - EUROCRYPT 2004","author":"C Dwork","year":"2004","unstructured":"Dwork, C., Naor, M., Reingold, O.: Immunizing encryption schemes from decryption errors. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 342\u2013360. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24676-3_21"},{"key":"5_CR24","unstructured":"Dinur, I., Reingold, O.: Assignment testers: towards a combinatorial proof of the PCP theorem. In: FOCS 2004 (2004)"},{"key":"5_CR25","doi-asserted-by":"crossref","unstructured":"Erg\u00fcn, F., Kumar, R., Rubinfeld, R.: Fast approximate probabilistically checkable proofs. In: Information and Computation (2004)","DOI":"10.1016\/j.ic.2003.09.005"},{"key":"5_CR26","unstructured":"F\u00fcrer, M., Goldreich, O., Mansour, Y., Sipser, M., Zachos, S.: On completeness and soundness in interactive proof systems. In: Advances in Computing Research (1989)"},{"key":"5_CR27","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Gur, T., Rothblum, R.D.: Proofs of proximity for context-free languages and read-once branching programs. Inf. Comput. (2018)","DOI":"10.1016\/j.ic.2018.02.003"},{"key":"5_CR28","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM (1998)","DOI":"10.1145\/285055.285060"},{"key":"5_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/978-3-642-22670-0_24","volume-title":"Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation","author":"O Goldreich","year":"2011","unstructured":"Goldreich, O.: A sample of samplers: a computational perspective on sampling. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation. LNCS, vol. 6650, pp. 302\u2013332. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22670-0_24"},{"key":"5_CR30","unstructured":"Gur, T., Rothblum, R.D.: Non-interactive proofs of proximity. Comput. Complex. (2018)"},{"key":"5_CR31","unstructured":"Hub\u00e1cek, P., Naor, M., Yogev, E.: The journey from NP to TFNP hardness. In: Papadimitriou, vol. 67. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017)"},{"key":"5_CR32","doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: STOC 1992 (1992)","DOI":"10.1145\/129712.129782"},{"key":"5_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/978-3-662-48000-7_21","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"YT Kalai","year":"2015","unstructured":"Kalai, Y.T., Rothblum, R.D.: Arguments of proximity. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 422\u2013442. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48000-7_21"},{"key":"5_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"574","DOI":"10.1007\/978-3-030-56877-1_20","volume-title":"Advances in Cryptology \u2013 CRYPTO 2020","author":"L Katzir","year":"2020","unstructured":"Katzir, L., Shikhelman, C., Yogev, E.: Interactive proofs for social graphs. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 574\u2013601. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-56877-1_20"},{"key":"5_CR35","doi-asserted-by":"crossref","unstructured":"Lautemann, C.: BPP and the polynomial hierarchy. Inf. Process. Lett. (1983)","DOI":"10.1016\/0020-0190(83)90044-3"},{"key":"5_CR36","doi-asserted-by":"crossref","unstructured":"Micali, S.: Computationally sound proofs. SIAM J. Comput. (2000). Preliminary version appeared in FOCS 1994","DOI":"10.1137\/S0097539795284959"},{"key":"5_CR37","doi-asserted-by":"crossref","unstructured":"Mie, T.: Short PCPPs verifiable in polylogarithmic time with O(1) queries. Ann. Math. Artif. Intell. (2009)","DOI":"10.1007\/s10472-009-9169-y"},{"key":"5_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/0-387-34805-0_13","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 89 Proceedings","author":"M Naor","year":"1990","unstructured":"Naor, M.: Bit commitment using pseudo-randomness. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 128\u2013136. Springer, New York (1990). https:\/\/doi.org\/10.1007\/0-387-34805-0_13"},{"key":"5_CR39","doi-asserted-by":"crossref","unstructured":"Nisan, N., Wigderson, A.: Hardness vs randomness. J. Comput. Syst. Sci. (1994)","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"5_CR40","unstructured":"Rothblum, R.: Private communication"},{"key":"5_CR41","doi-asserted-by":"crossref","unstructured":"Ron-Zewi, N., Rothblum, R.: Local proofs approaching the witness length. In: FOCS 2020 (2020)","DOI":"10.1109\/FOCS46700.2020.00083"},{"key":"5_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-030-64378-2_5","volume-title":"Theory of Cryptography","author":"GN Rothblum","year":"2020","unstructured":"Rothblum, G.N., Rothblum, R.D.: Batch verification and proofs of proximity with polylog overhead. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12551, pp. 108\u2013138. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64378-2_5"},{"key":"5_CR43","doi-asserted-by":"crossref","unstructured":"Ron-Zewi, N., Rothblum, R.D.: Proving as fast as computing: succinct arguments with constant prover overhead. In: STOC 2022 (2022)","DOI":"10.1145\/3519935.3519956"},{"key":"5_CR44","doi-asserted-by":"crossref","unstructured":"Reingold, O., Rothblum, R., Rothblum, G.: Constant-round interactive proofs for delegating computation. In: STOC 2016 (2016)","DOI":"10.1145\/2897518.2897652"},{"key":"5_CR45","doi-asserted-by":"crossref","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. (1996)","DOI":"10.1137\/S0097539793255151"},{"key":"5_CR46","doi-asserted-by":"crossref","unstructured":"Rothblum, G.N., Vadhan, S.P., Wigderson, A.: Interactive proofs of proximity: delegating computation in sublinear time. In: STOC 2013 (2013)","DOI":"10.1145\/2488608.2488709"},{"key":"5_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1007\/978-3-030-26954-8_24","volume-title":"Advances in Cryptology \u2013 CRYPTO 2019","author":"T Xie","year":"2019","unstructured":"Xie, T., Zhang, J., Zhang, Y., Papamanthou, C., Song, D.: Libra: succinct zero-knowledge proofs with optimal prover computation. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 733\u2013764. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-26954-8_24"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-78011-0_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,1]],"date-time":"2024-12-01T20:02:23Z","timestamp":1733083343000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-78011-0_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,2]]},"ISBN":["9783031780103","9783031780110"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-78011-0_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,12,2]]},"assertion":[{"value":"2 December 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TCC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Theory of Cryptography Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Milan","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 December 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 December 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcc.iacr.org\/2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}