{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T15:49:30Z","timestamp":1783007370556,"version":"3.54.5"},"reference-count":102,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,5,2]],"date-time":"2022-05-02T00:00:00Z","timestamp":1651449600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,2]],"date-time":"2022-05-02T00:00:00Z","timestamp":1651449600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"EPFL Lausanne"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p><jats:italic>Succinct non-interactive arguments<\/jats:italic>(SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays, researchers have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation. A common relaxation is a<jats:italic>preprocessing<\/jats:italic>SNARG, which allows the verifier to conduct an expensive offline phase that is independent of the statement to be proven later. Recent constructions of preprocessing SNARGs have achieved attractive features: they are publicly-verifiable, proofs consist of only<jats:italic>O<\/jats:italic>(1) encrypted (or encoded) field elements, and verification is via arithmetic circuits of size linear in the NP statement. Additionally, these constructions seem to have \u201cescaped the hegemony\u201d of probabilistically-checkable proofs (PCPs) as a basic building block of succinct arguments. We present a general methodology for the construction of preprocessing<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\text{ SNARG } $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mspace\/><mml:mtext>SNARG<\/mml:mtext><mml:mspace\/><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>s, as well as resulting new efficiency features. Our contribution is threefold:<jats:def-list><jats:def-item><jats:term><jats:bold>(1)<\/jats:bold><\/jats:term><jats:def><jats:p>We introduce and study a natural extension of the interactive proof model that considers<jats:italic>algebraically-bounded<\/jats:italic>provers; this new setting is analogous to the common study of algebraically-bounded \u201cadversaries\u201d in other fields, such as pseudorandomness and randomness extraction. More concretely, in this work we focus on linear (or affine) provers, and provide several constructions of (succinct two-message)<jats:italic>linear interactive proofs<\/jats:italic>(LIPs) for NP. Our constructions are based on general transformations applied to both<jats:italic>linear<\/jats:italic>PCPs (LPCPs) and traditional \u201cunstructured\u201d PCPs.<\/jats:p><\/jats:def><\/jats:def-item><jats:def-item><jats:term><jats:bold>(2)<\/jats:bold><\/jats:term><jats:def><jats:p>We give conceptually simple cryptographic transformations from LIPs to preprocessing SNARGs, whose security can be based on different forms of<jats:italic>linear targeted malleability<\/jats:italic>(implied by previous knowledge assumptions). Our transformations convert arbitrary (two-message) LIPs into designated-verifier SNARGs, and LIPs with degree-bounded verifiers into publicly-verifiable SNARGs. We also extend our methodology to obtain<jats:italic>zero-knowledge<\/jats:italic>LIPs and SNARGs. Our techniques yield SNARGs<jats:italic>of knowledge<\/jats:italic>and thus can benefit from known recursive composition and bootstrapping techniques.<\/jats:p><\/jats:def><\/jats:def-item><jats:def-item><jats:term><jats:bold>(3)<\/jats:bold><\/jats:term><jats:def><jats:p>Following this methodology, we exhibit several constructions achieving new efficiency features, such as \u201csingle-ciphertext preprocessing SNARGs.\u201d We also offer a new perspective on existing constructions of preprocessing SNARGs, revealing a direct connection of these to LPCPs and LIPs.<\/jats:p><\/jats:def><\/jats:def-item><\/jats:def-list><\/jats:p>","DOI":"10.1007\/s00145-022-09424-4","type":"journal-article","created":{"date-parts":[[2022,5,2]],"date-time":"2022-05-02T23:02:36Z","timestamp":1651532556000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Succinct Non-Interactive Arguments via Linear Interactive Proofs"],"prefix":"10.1007","volume":"35","author":[{"given":"Nir","family":"Bitansky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alessandro","family":"Chiesa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Omer","family":"Paneth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,5,2]]},"reference":[{"key":"9424_CR1","doi-asserted-by":"crossref","unstructured":"William Aiello, Sandeep\u00a0N. Bhatt, Rafail Ostrovsky, and Sivaramakrishnan Rajagopalan. Fast verification of any remote procedure call: Short witness-indistinguishable one-round proofs for NP. In Proceedings of the 27th International Colloquium on Automata, Languages and Programming, ICALP\u00a0\u201900, pages 463\u2013474, 2000.","DOI":"10.1007\/3-540-45022-X_39"},{"key":"9424_CR2","unstructured":"Masayuki Abe and Serge Fehr. Perfect NIZK with adaptive soundness. In Proceedings of the 4th Theory of Cryptography Conference, TCC\u00a0\u201907, pages 118\u2013136, 2007."},{"key":"9424_CR3","doi-asserted-by":"crossref","unstructured":"Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. From secrecy to soundness: Efficient verification via secure computation. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP\u00a0\u201910, pages 152\u2013163, 2010.","DOI":"10.1007\/978-3-642-14165-2_14"},{"key":"9424_CR4","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501\u2013555, 1998. Preliminary version in FOCS\u00a0\u201992.","DOI":"10.1145\/278298.278306"},{"key":"9424_CR5","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM, 45(1):70\u2013122, 1998. Preliminary version in FOCS\u00a0\u201992.","DOI":"10.1145\/273865.273901"},{"key":"9424_CR6","doi-asserted-by":"crossref","unstructured":"Dana Angluin and Leslie\u00a0G. Valiant. Fast probabilistic algorithms for hamiltonian circuits and matchings. In Proceedings on 9th Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201977, pages 30\u201341, 1977.","DOI":"10.1145\/800105.803393"},{"key":"9424_CR7","doi-asserted-by":"crossref","unstructured":"Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai. Zero-knowledge proofs on secret-shared data via fully linear PCPs. In Proceedings of the 39th Annual International Cryptology Conference, CRYPTO\u00a0\u201919, pages 67\u201397, 2019.","DOI":"10.1007\/978-3-030-26954-8_3"},{"key":"9424_CR8","doi-asserted-by":"crossref","unstructured":"Nir Bitansky and Alessandro Chiesa. Succinct arguments from multi-prover interactive proofs and their efficiency benefits. In Proceedings of the 32nd Annual International Cryptology Conference, CRYPTO\u00a0\u201912, pages 255\u2013272, 2012.","DOI":"10.1007\/978-3-642-32009-5_16"},{"issue":"2","key":"9424_CR9","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(88)90005-0","volume":"37","author":"Gilles Brassard","year":"1988","unstructured":"Gilles Brassard, David Chaum, and Claude Cr\u00e9peau. Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences, 37(2):156\u2013189, 1988.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"9424_CR10","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1007\/s00145-016-9241-9","volume":"30","author":"Nir Bitansky","year":"2017","unstructured":"Nir Bitansky, Ran Canetti, Alessandro Chiesa, Shafi Goldwasser, Huijia Lin, Aviad Rubinstein, and Eran Tromer. The hunting of the SNARK. Journal of Cryptology, 30(4):989\u20131066, 2017.","journal-title":"Journal of Cryptology"},{"key":"9424_CR11","doi-asserted-by":"crossref","unstructured":"Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS\u00a0\u201912, pages 326\u2013349, 2012.","DOI":"10.1145\/2090236.2090263"},{"key":"9424_CR12","doi-asserted-by":"crossref","unstructured":"Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. Recursive composition and bootstrapping for SNARKs and proof-carrying data. In Proceedings of the 45th ACM Symposium on the Theory of Computing, STOC\u00a0\u201913, pages 111\u2013120, 2013.","DOI":"10.1145\/2488608.2488623"},{"key":"9424_CR13","doi-asserted-by":"crossref","unstructured":"Jonathan Bootle, Andrea Cerulli, Essam Ghadafi, Jens Groth, Mohammad Hajiabadi, and Sune\u00a0K. Jakobsen. Linear-time zero-knowledge proofs for arithmetic circuit satisfiability. In Proceedings of the 23rd International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT\u00a0\u201917, pages 336\u2013365, 2017.","DOI":"10.1007\/978-3-319-70700-6_12"},{"key":"9424_CR14","unstructured":"Josh Benaloh. Dense probabilistic encryption. In Proceedings of the Workshop on Selected Areas of Cryptography, pages 120\u2013128, 1994."},{"issue":"111","key":"9424_CR15","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1090\/S0025-5718-1970-0276200-X","volume":"24","author":"Elwyn R Berlekamp","year":"1970","unstructured":"Elwyn\u00a0R. Berlekamp. Factoring polynomials over large finite fields. Mathematics of Computation, 24(111):713\u2013735, 1970.","journal-title":"Mathematics of Computation"},{"key":"9424_CR16","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai, Lance Fortnow, Leonid\u00a0A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201991, pages 21\u201332, 1991.","DOI":"10.1145\/103418.103428"},{"key":"9424_CR17","doi-asserted-by":"crossref","unstructured":"Manuel Blum, Paul Feldman, and Silvio Micali. Non-interactive zero-knowledge and its applications (extended abstract). In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 103\u2013112, 1988.","DOI":"10.1145\/62212.62222"},{"key":"9424_CR18","doi-asserted-by":"crossref","unstructured":"Benedikt B\u00fcnz, Ben Fisch, and Alan Szepieniec. Transparent SNARKs from DARK compilers. In Proceedings of the 39th Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT\u00a0\u201920, pages 677\u2013706, 2020.","DOI":"10.1007\/978-3-030-45721-1_24"},{"key":"9424_CR19","doi-asserted-by":"crossref","unstructured":"Boaz Barak and Oded Goldreich. Universal arguments and their applications. SIAM Journal on Computing, 38(5):1661\u20131694, 2008. Preliminary version appeared in CCC\u00a0\u201902.","DOI":"10.1137\/070709244"},{"key":"9424_CR20","doi-asserted-by":"crossref","unstructured":"Siavosh Benabbas, Rosario Gennaro, and Yevgeniy Vahlis. Verifiable delegation of computation over large datasets. In Proceedings of the 31st Annual International Cryptology Conference, CRYPTO\u00a0\u201911, pages 111\u2013131, 2011.","DOI":"10.1007\/978-3-642-22792-9_7"},{"issue":"2","key":"9424_CR21","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"Ravi B Boppana","year":"1987","unstructured":"Ravi\u00a0B. Boppana, Johan H\u00e5stad, and Stathis Zachos. Does co-NP have short interactive proofs? Information Processing Letters, 25(2):127\u2013132, 1987.","journal-title":"Information Processing Letters"},{"key":"9424_CR22","doi-asserted-by":"crossref","unstructured":"Ohad Barta, Yuval Ishai, Rafail Ostrovsky, and David\u00a0J. Wu. On succinct arguments and witness encryption from groups. In Proceedings of the 40th Annual International Cryptology Conference, CRYPTO\u00a0\u201920, pages 776\u2013806, 2020.","DOI":"10.1007\/978-3-030-56784-2_26"},{"key":"9424_CR23","doi-asserted-by":"crossref","unstructured":"Paulo S. L.\u00a0M. Barreto and Michael Naehrig. Pairing-friendly elliptic curves of prime order. In Proceedings of the 12th International Workshop in Selected Areas in Cryptography, 12th International Workshop, SAC\u00a0\u201905, pages 319\u2013331, 2005.","DOI":"10.1007\/11693383_22"},{"key":"9424_CR24","doi-asserted-by":"crossref","unstructured":"Michael Ben-Or. Probabilistic algorithms in finite fields. In Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science, FOCS\u00a0\u201981, pages 394\u2013398, 1981.","DOI":"10.1109\/SFCS.1981.37"},{"key":"9424_CR25","doi-asserted-by":"crossref","unstructured":"Mihir Bellare and Adriana Palacio. The knowledge-of-exponent assumptions and 3-round zero-knowledge protocols. In Proceedings of the 24th Annual International Cryptology Conference, CRYPTO\u00a0\u201904, pages 273\u2013289, 2004.","DOI":"10.1007\/978-3-540-28628-8_17"},{"key":"9424_CR26","doi-asserted-by":"crossref","unstructured":"Mihir Bellare and Adriana Palacio. Towards plaintext-aware public-key encryption without random oracles. In Proceedings of the 10th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT\u00a0\u201904, pages 48\u201362, 2004.","DOI":"10.1007\/978-3-540-30539-2_4"},{"key":"9424_CR27","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer. Fast reductions from RAMs to delegatable succinct constraint satisfaction problems. In Proceedings of the 4th Innovations in Theoretical Computer Science Conference, ITCS\u00a0\u201913, pages 401\u2013414, 2013.","DOI":"10.1145\/2422436.2422481"},{"key":"9424_CR28","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer. On the concrete efficiency of probabilistically-checkable proofs. In Proceedings of the 45th ACM Symposium on the Theory of Computing, STOC\u00a0\u201913, 2013.","DOI":"10.1145\/2488608.2488681"},{"key":"9424_CR29","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil Vadhan. Robust PCPs of proximity, shorter PCPs and applications to coding. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201904, pages 1\u201310, 2004.","DOI":"10.1145\/1007352.1007361"},{"key":"9424_CR30","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil Vadhan. Short PCPs verifiable in polylogarithmic time. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity, CCC\u00a0\u201905, pages 120\u2013134, 2005.","DOI":"10.1109\/CCC.2005.27"},{"key":"9424_CR31","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson, Prahladh Harsha, Oded Lachish, and Arie Matsliah. Sound 3-query PCPPs are long. ACM Transactions on Computation Theory, 1(2):7:1\u20137:49, 2009. Preliminary version appeared in ICALP\u00a0\u201908.","DOI":"10.1145\/1595391.1595394"},{"key":"9424_CR32","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson and Madhu Sudan. Short PCPs with polylog query complexity. SIAM Journal on Computing, 38(2):551\u2013607, 2008. Preliminary version appeared in STOC\u00a0\u201905.","DOI":"10.1137\/050646445"},{"key":"9424_CR33","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson, Madhu Sudan, Salil Vadhan, and Avi Wigderson. Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, STOC \u201903, pages 612\u2013621, 2003.","DOI":"10.1145\/780542.780631"},{"key":"9424_CR34","doi-asserted-by":"crossref","unstructured":"Dan Boneh, Gil Segev, and Brent Waters. Targeted malleability: Homomorphic encryption for restricted computations. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS\u00a0\u201912, pages 350\u2013366, 2012.","DOI":"10.1145\/2090236.2090264"},{"key":"9424_CR35","doi-asserted-by":"crossref","unstructured":"Andrej Bogdanov and Emanuele Viola. Pseudorandom bits for polynomials. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS\u00a0\u201907, pages 41\u201351, 2007.","DOI":"10.1109\/FOCS.2007.42"},{"key":"9424_CR36","doi-asserted-by":"crossref","unstructured":"Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS\u00a0\u201911, 2011.","DOI":"10.1109\/FOCS.2011.12"},{"key":"9424_CR37","doi-asserted-by":"crossref","unstructured":"Kai-Min Chung, Yael Kalai, and Salil Vadhan. Improved delegation of computation using fully homomorphic encryption. In Proceedings of the 30th Annual International Cryptology Conference, CRYPTO\u00a0\u201910, pages 483\u2013501, 2010.","DOI":"10.1007\/978-3-642-14623-7_26"},{"key":"9424_CR38","doi-asserted-by":"crossref","unstructured":"Graham Cormode, Michael Mitzenmacher, and Justin Thaler. Practical verified computation with streaming interactive proofs. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS\u00a0\u201912, pages 90\u2013112, 2012.","DOI":"10.1145\/2090236.2090245"},{"key":"9424_CR39","doi-asserted-by":"crossref","unstructured":"Stephen\u00a0A. Cook and Robert\u00a0A. Reckhow. Time-bounded random access machines. In Proceedings of the 4th Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201972, pages 73\u201380, 1972.","DOI":"10.1145\/800152.804898"},{"key":"9424_CR40","doi-asserted-by":"crossref","unstructured":"Ran Canetti, Ben Riva, and Guy\u00a0N. Rothblum. Two protocols for delegation of computation. In Proceedings of the 6th International Conference on Information Theoretic Security, volume 7412 of ICITS\u00a0\u201912, pages 37\u201361, 2012.","DOI":"10.1007\/978-3-642-32284-6_3"},{"issue":"1","key":"9424_CR41","doi-asserted-by":"publisher","first-page":"25","DOI":"10.14778\/2047485.2047488","volume":"5","author":"Graham Cormode","year":"2011","unstructured":"Graham Cormode, Justin Thaler, and Ke\u00a0Yi. Verifying computations with streaming interactive proofs. Proceedings of the VLDB Endowment, 5(1):25\u201336, 2011.","journal-title":"Proceedings of the VLDB Endowment"},{"issue":"154","key":"9424_CR42","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1090\/S0025-5718-1981-0606517-5","volume":"36","author":"David G Cantor","year":"1981","unstructured":"David\u00a0G. Cantor and Hans Zassenhaus. A new algorithm for factoring polynomials over finite fields. Mathematics of Computation, 36(154):587\u2013592, 1981.","journal-title":"Mathematics of Computation"},{"key":"9424_CR43","doi-asserted-by":"crossref","unstructured":"Ivan Damg\u00e5rd. Towards practical public key systems secure against chosen ciphertext attacks. In Proceedings of the 11th Annual International Cryptology Conference, CRYPTO\u00a0\u201992, pages 445\u2013456, 1992.","DOI":"10.1007\/3-540-46766-1_36"},{"key":"9424_CR44","doi-asserted-by":"crossref","unstructured":"Giovanni Di\u00a0Crescenzo and Helger Lipmaa. Succinct NP proofs from an extractability assumption. In Proceedings of the 4th Conference on Computability in Europe, CiE\u00a0\u201908, pages 175\u2013185, 2008.","DOI":"10.1007\/978-3-540-69407-6_21"},{"key":"9424_CR45","doi-asserted-by":"crossref","unstructured":"George Danezis, Cedric Fournet, Jens Groth, and Markulf Kohlweiss. Square span programs with applications to succinct NIZK arguments. In Proceedings of the 20th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT\u00a0\u201914, pages 532\u2013550, 2014.","DOI":"10.1007\/978-3-662-45611-8_28"},{"key":"9424_CR46","doi-asserted-by":"crossref","unstructured":"Ivan Damg\u00e5rd, Sebastian Faust, and Carmit Hazay. Secure two-party computation with low communication. In Proceedings of the 9th Theory of Cryptography Conference, TCC\u00a0\u201912, pages 54\u201374, 2012.","DOI":"10.1007\/978-3-642-28914-9_4"},{"key":"9424_CR47","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork, Uriel Feige, Joe Kilian, Moni Naor, and Shmuel Safra. Low communication 2-prover zero-knowledge proofs for NP. In Proceedings of the 11th Annual International Cryptology Conference, CRYPTO\u00a0\u201992, pages 215\u2013227, 1992.","DOI":"10.1007\/3-540-48071-4_15"},{"issue":"1","key":"9424_CR48","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-009-0258-4","volume":"18","author":"Zeev Dvir","year":"2009","unstructured":"Zeev Dvir, Ariel Gabizon, and Avi Wigderson. Extractors and rank extractors for polynomial sources. Computational Complexity, 18(1):1\u201358, 2009.","journal-title":"Computational Complexity"},{"issue":"3","key":"9424_CR49","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/1236457.1236459","volume":"54","author":"Irit Dinur","year":"2007","unstructured":"Irit Dinur. The PCP theorem by gap amplification. Journal of the ACM, 54(3):12, 2007.","journal-title":"Journal of the ACM"},{"key":"9424_CR50","unstructured":"Cynthia Dwork, Michael Langberg, Moni Naor, Kobbi Nissim, and Omer Reingold. Succinct NP proofs and spooky interactions, December 2004. Available at www.openu.ac.il\/home\/mikel\/papers\/spooky.ps."},{"issue":"4","key":"9424_CR51","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","volume":"31","author":"Taher El Gamal","year":"1985","unstructured":"Taher El\u00a0Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31(4):469\u2013472, 1985.","journal-title":"IEEE Transactions on Information Theory"},{"key":"9424_CR52","doi-asserted-by":"crossref","unstructured":"Dario Fiore and Rosario Gennaro. Publicly verifiable delegation of large polynomials and matrix computations, with applications. In Proceedings of the 2012 ACM Conference on Computer and Communications Security, CCS\u00a0\u201912, pages 501\u2013512, 2012.","DOI":"10.1145\/2382196.2382250"},{"key":"9424_CR53","doi-asserted-by":"crossref","unstructured":"Uriel Feige, Shafi Goldwasser, Laszlo Lov\u00e1sz, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 43(2):268\u2013292, 1996. Preliminary version in FOCS\u00a0\u201991.","DOI":"10.1145\/226643.226652"},{"key":"9424_CR54","doi-asserted-by":"crossref","unstructured":"Amos Fiat and Adi Shamir. How to prove yourself: practical solutions to identification and signature problems. In Proceedings of the 6th Annual International Cryptology Conference, CRYPTO\u00a0\u201987, pages 186\u2013194, 1987.","DOI":"10.1007\/3-540-47721-7_12"},{"key":"9424_CR55","doi-asserted-by":"crossref","unstructured":"Rosario Gennaro, Craig Gentry, and Bryan Parno. Non-interactive verifiable computing: outsourcing computation to untrusted workers. In Proceedings of the 30th Annual International Cryptology Conference, CRYPTO\u00a0\u201910, pages 465\u2013482, 2010.","DOI":"10.1007\/978-3-642-14623-7_25"},{"key":"9424_CR56","doi-asserted-by":"crossref","unstructured":"Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct NIZKs without PCPs. In Proceedings of the 32nd Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT\u00a0\u201913, pages 626\u2013645, 2013.","DOI":"10.1007\/978-3-642-38348-9_37"},{"key":"9424_CR57","doi-asserted-by":"crossref","unstructured":"Sanjam Garg, Craig Gentry, Amit Sahai, and Brent Waters. Witness encryption and its applications. In Proceedings of the 45th ACM Symposium on the Theory of Computing, STOC\u00a0\u201913, pages 467\u2013476, 2013.","DOI":"10.1145\/2488608.2488667"},{"issue":"4","key":"9424_CR58","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/S0020-0190(98)00116-1","volume":"67","author":"Oded Goldreich","year":"1998","unstructured":"Oded Goldreich and Johan H\u00e5stad. On the complexity of interactive proofs with bounded communication. Information Processing Letters, 67(4):205\u2013214, 1998.","journal-title":"Information Processing Letters"},{"key":"9424_CR59","doi-asserted-by":"crossref","unstructured":"Shafi Goldwasser, Yael\u00a0Tauman Kalai, and Guy\u00a0N. Rothblum. Delegating computation: Interactive proofs for Muggles. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201908, pages 113\u2013122, 2008.","DOI":"10.1145\/1374376.1374396"},{"key":"9424_CR60","unstructured":"Shafi Goldwasser, Huijia Lin, and Aviad Rubinstein. Delegation of computation without rejection problem from designated verifier CS-proofs. Cryptology ePrint Archive, Report 2011\/456, 2011."},{"issue":"2","key":"9424_CR61","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"Shafi Goldwasser","year":"1984","unstructured":"Shafi Goldwasser and Silvio Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270\u2013299, 1984.","journal-title":"Journal of Computer and System Sciences"},{"key":"9424_CR62","doi-asserted-by":"crossref","unstructured":"Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186\u2013208, 1989. Preliminary version appeared in STOC\u00a0\u201985.","DOI":"10.1137\/0218012"},{"key":"9424_CR63","doi-asserted-by":"crossref","unstructured":"Ariel Gabizon and Ran Raz. Deterministic extractors for affine sources over large fields. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS\u00a0\u201905, pages 407\u2013418, 2005.","DOI":"10.1109\/SFCS.2005.31"},{"key":"9424_CR64","doi-asserted-by":"crossref","unstructured":"Jens Groth. Short pairing-based non-interactive zero-knowledge arguments. In Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT\u00a0\u201910, pages 321\u2013340, 2010.","DOI":"10.1007\/978-3-642-17373-8_19"},{"key":"9424_CR65","doi-asserted-by":"crossref","unstructured":"Jens Groth. On the size of pairing-based non-interactive arguments. In Proceedings of the 35th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT \u201916, pages 305\u2013326, 2016.","DOI":"10.1007\/978-3-662-49896-5_11"},{"key":"9424_CR66","doi-asserted-by":"crossref","unstructured":"Oded Goldreich and Madhu Sudan. Locally testable codes and PCPs of almost-linear length. Journal of the ACM, 53:558\u2013655, July 2006. Preliminary version in STOC\u00a0\u201902.","DOI":"10.1145\/1162349.1162351"},{"issue":"1\/2","key":"9424_CR67","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-002-0169-0","volume":"11","author":"Oded Goldreich","year":"2002","unstructured":"Oded Goldreich, Salil Vadhan, and Avi Wigderson. On interactive proofs with a laconic prover. Computational Complexity, 11(1\/2):1\u201353, 2002.","journal-title":"Computational Complexity"},{"key":"9424_CR68","doi-asserted-by":"crossref","unstructured":"Craig Gentry and Daniel Wichs. Separating succinct non-interactive arguments from all falsifiable assumptions. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201911, pages 99\u2013108, 2011.","DOI":"10.1145\/1993636.1993651"},{"issue":"1","key":"9424_CR69","doi-asserted-by":"publisher","first-page":"119","DOI":"10.4086\/toc.2005.v001a007","volume":"1","author":"Johan H\u00e5stad","year":"2005","unstructured":"Johan H\u00e5stad and Subhash Khot. Query efficient PCPs with perfect completeness. Theory of Computing, 1(1):119\u2013148, 2005.","journal-title":"Theory of Computing"},{"key":"9424_CR70","doi-asserted-by":"crossref","unstructured":"Prahladh Harsha and Madhu Sudan. Small PCPs with low query complexity. Computational Complexity, 9(3\u20134):157\u2013201, Dec 2000. Preliminary version in STACS\u00a0\u201991.","DOI":"10.1007\/PL00001606"},{"key":"9424_CR71","doi-asserted-by":"crossref","unstructured":"Satoshi Hada and Toshiaki Tanaka. On the existence of 3-round zero-knowledge protocols. In Proceedings of the 18th Annual International Cryptology Conference, CRYPTO\u00a0\u201998, pages 408\u2013423, 1998.","DOI":"10.1007\/BFb0055744"},{"key":"9424_CR72","doi-asserted-by":"crossref","unstructured":"Yuval Ishai, Eyal Kushilevitz, and Rafail Ostrovsky. Efficient arguments without short PCPs. In Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, CCC\u00a0\u201907, pages 278\u2013291, 2007.","DOI":"10.1109\/CCC.2007.10"},{"key":"9424_CR73","unstructured":"Yuval Ishai. Zero-knowledge proofs from information-theoretic proof systems. zkproof.org blog post https:\/\/zkproof.org\/2020\/08\/12\/information-theoretic-proof-systems, 2020."},{"key":"9424_CR74","doi-asserted-by":"crossref","unstructured":"Joe Kilian. A note on efficient zero-knowledge proofs and arguments. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201992, pages 723\u2013732, 1992.","DOI":"10.1145\/129712.129782"},{"key":"9424_CR75","doi-asserted-by":"crossref","unstructured":"Yael\u00a0Tauman Kalai and Ran Raz. Succinct non-interactive zero-knowledge proofs with preprocessing for LOGSNP. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pages 355\u2013366, 2006.","DOI":"10.1109\/FOCS.2006.74"},{"key":"9424_CR76","doi-asserted-by":"crossref","unstructured":"Yael Kalai and Ran Raz. Interactive PCP. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP\u00a0\u201908, pages 536\u2013547, 2008.","DOI":"10.1007\/978-3-540-70583-3_44"},{"key":"9424_CR77","doi-asserted-by":"crossref","unstructured":"Yael\u00a0Tauman Kalai and Ran Raz. Probabilistically checkable arguments. In Proceedings of the 29th Annual International Cryptology Conference, CCC\u00a0\u201909, pages 143\u2013159, 2009.","DOI":"10.1007\/978-3-642-03356-8_9"},{"key":"9424_CR78","doi-asserted-by":"crossref","unstructured":"Helger Lipmaa. Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments. In Proceedings of the 9th Theory of Cryptography Conference, TCC\u00a0\u201912, pages 169\u2013189, 2012.","DOI":"10.1007\/978-3-642-28914-9_10"},{"key":"9424_CR79","doi-asserted-by":"crossref","unstructured":"Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT\u00a0\u201910, pages 1\u201323, 2010.","DOI":"10.1007\/978-3-642-13190-5_1"},{"key":"9424_CR80","doi-asserted-by":"crossref","unstructured":"Or\u00a0Meir. Combinatorial PCPs with short proofs. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC\u00a0\u201912, 2012.","DOI":"10.1109\/CCC.2012.14"},{"key":"9424_CR81","doi-asserted-by":"crossref","unstructured":"Ralph\u00a0C. Merkle and Martin\u00a0E. Hellman. Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory, 24(5):525\u2013530, Sep 1978.","DOI":"10.1109\/TIT.1978.1055927"},{"key":"9424_CR82","doi-asserted-by":"crossref","unstructured":"Silvio Micali. Computationally sound proofs. SIAM Journal on Computing, 30(4):1253\u20131298, 2000. Preliminary version appeared in FOCS\u00a0\u201994.","DOI":"10.1137\/S0097539795284959"},{"issue":"4","key":"9424_CR83","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1515\/JMC.2008.016","volume":"2","author":"Thilo Mie","year":"2008","unstructured":"Thilo Mie. Polylogarithmic two-round argument systems. Journal of Mathematical Cryptology, 2(4):343\u2013363, 2008.","journal-title":"Journal of Mathematical Cryptology"},{"key":"9424_CR84","doi-asserted-by":"crossref","unstructured":"Dana Moshkovitz and Ran Raz. Two-query PCP with subconstant error. Journal of the ACM, 57:1\u201329, June 2008. Preliminary version appeared in FOCS\u00a0\u201908.","DOI":"10.1145\/1754399.1754402"},{"key":"9424_CR85","doi-asserted-by":"crossref","unstructured":"Moni Naor. On cryptographic assumptions and challenges. In Proceedings of the 23rd Annual International Cryptology Conference, CRYPTO\u00a0\u201903, pages 96\u2013109, 2003.","DOI":"10.1007\/978-3-540-45146-4_6"},{"key":"9424_CR86","doi-asserted-by":"crossref","unstructured":"Joseph Naor and Moni Naor. Small-bias probability spaces: efficient constructions and applications. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201990, pages 213\u2013223, 1990.","DOI":"10.1145\/100216.100244"},{"key":"9424_CR87","doi-asserted-by":"crossref","unstructured":"Moni Naor, Merav Parter, and Eylon Yogev. The power of distributed verifiers in interactive proofs. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1096\u2013115. SIAM, 2020.","DOI":"10.1137\/1.9781611975994.67"},{"key":"9424_CR88","doi-asserted-by":"crossref","unstructured":"Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Proceedings of the 17th International Conference On Theory And Application Of Cryptographic Techniques, EUROCRYPT\u00a0\u201999, pages 223\u2013238, 1999.","DOI":"10.1007\/3-540-48910-X_16"},{"key":"9424_CR89","doi-asserted-by":"crossref","unstructured":"Christophe Petit and Jean-Jacques Quisquater. On polynomial systems arising from a Weil descent. In Proceedings of the 18th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT\u00a0\u201912, 2012.","DOI":"10.1007\/978-3-642-34961-4_28"},{"key":"9424_CR90","doi-asserted-by":"crossref","unstructured":"Alexander Polishchuk and Daniel\u00a0A. Spielman. Nearly-linear size holographic proofs. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201994, pages 194\u2013203, 1994.","DOI":"10.1145\/195058.195132"},{"key":"9424_CR91","doi-asserted-by":"crossref","unstructured":"Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201905, pages 84\u201393, 2005.","DOI":"10.1145\/1060590.1060603"},{"key":"9424_CR92","doi-asserted-by":"crossref","unstructured":"Ron Rothblum. Homomorphic encryption: From private-key to public-key. In Proceedings of the 8th Theory of Cryptography Conference, TCC\u00a0\u201911, pages 219\u2013234, 2011.","DOI":"10.1007\/978-3-642-19571-6_14"},{"key":"9424_CR93","doi-asserted-by":"crossref","unstructured":"Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201997, pages 475\u2013484, 1997.","DOI":"10.1145\/258533.258641"},{"key":"9424_CR94","doi-asserted-by":"crossref","unstructured":"Srinath Setty, Benjamin Braun, Victor Vu, Andrew\u00a0J. Blumberg, Bryan Parno, and Michael Walfish. Resolving the conflict between generality and plausibility in verified computation. In Proceedings of the 8th EuoroSys Conference, EuroSys\u00a0\u201913, pages 71\u201384, 2013.","DOI":"10.1145\/2465351.2465359"},{"key":"9424_CR95","unstructured":"Srinath Setty, Andrew\u00a0J. Blumberg, and Michael Walfish. Toward practical and unconditional verification of remote computations. In Proceedings of the 13th USENIX Conference on Hot Topics in Operating Systems, HotOS\u00a0\u201911, pages 29\u201329, 2011."},{"issue":"4","key":"9424_CR96","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"Adi Shamir","year":"1992","unstructured":"Adi Shamir. IP = PSPACE. Journal of the ACM, 39(4):869\u2013877, 1992.","journal-title":"Journal of the ACM"},{"key":"9424_CR97","unstructured":"Srinath Setty, Michael McPherson, Andrew\u00a0J. Blumberg, and Michael Walfish. Making argument systems for outsourced computation practical (sometimes). In Proceedings of the 2012 Network and Distributed System Security Symposium, NDSS\u00a0\u201912, pages ???\u2013???, 2012."},{"key":"9424_CR98","unstructured":"Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Andrew\u00a0J. Blumberg, and Michael Walfish. Taking proof-based verified computation a few steps closer to practicality. In Proceedings of the 21st USENIX Security Symposium, Security\u00a0\u201912, pages 253\u2013268, 2012."},{"key":"9424_CR99","doi-asserted-by":"crossref","unstructured":"Justin Thaler. Proofs, arguments, and zero-knowledge. http:\/\/people.cs.georgetown.edu\/jthaler\/ProofsArgsAndZK.pdf, 2021.","DOI":"10.1561\/9781638281252"},{"key":"9424_CR100","doi-asserted-by":"crossref","unstructured":"Leslie\u00a0G. Valiant. Graph-theoretic arguments in low-level complexity. In Mathematical Foundations of Computer Science, volume\u00a053 of Lecture Notes in Computer Science, pages 162\u2013176. 1977.","DOI":"10.1007\/3-540-08353-7_135"},{"key":"9424_CR101","doi-asserted-by":"crossref","unstructured":"Joachim Von Zur\u00a0Gathen and Daniel Panario. Factoring polynomials over finite fields: a survey. Journal of Symbolic Computation, 31(1-2):3\u201317, Jan 2001.","DOI":"10.1006\/jsco.1999.1002"},{"key":"9424_CR102","doi-asserted-by":"crossref","unstructured":"Hoeteck Wee. On round-efficient argument systems. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP\u00a0\u201905, pages 140\u2013152, 2005.","DOI":"10.1007\/11523468_12"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-022-09424-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-022-09424-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-022-09424-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,23]],"date-time":"2024-09-23T16:10:44Z","timestamp":1727107844000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-022-09424-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,2]]},"references-count":102,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["9424"],"URL":"https:\/\/doi.org\/10.1007\/s00145-022-09424-4","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,2]]},"assertion":[{"value":"29 October 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 May 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"15"}}