Faster Sounder Succinct Arguments and s
Pages 474 - 503
Abstract
Succinct arguments allow a prover to convince a verifier that a given statement is true, using an extremely short proof. A major bottleneck that has been the focus of a large body of work is in reducing the overhead incurred by the prover in order to prove correctness of the computation. By overhead we refer to the cost of proving correctness, divided by the cost of the original computation.
In this work, for a large class of Boolean circuits , we construct succinct arguments for the language , with soundness error, and with prover overhead . This result relies on the existence of (sub-exponentially secure) linear-size computable collision-resistant hash functions. The class of Boolean circuits that we can handle includes circuits with a repeated sub-structure, which arise in natural applications such as batch computation/verification, hashing and related block chain applications.
The succinct argument is obtained by constructing interactive oracle proofs for the same class of languages, with prover overhead, and soundness error . Prior to our work, the best s for Boolean circuits either had prover overhead of based on efficient s due to Ben Sasson et al. (STOC, 2013) or due to Rothblum and Ron-Zewi (STOC, 2022).
References
[1]
Applebaum, B., Haramaty, N., Ishai, Y., Kushilevitz, E., Vaikuntanathan, V.: Low-complexity cryptographic hash functions. In: Papadimitriou, C.H. (ed.) ITCS 2017. LIPIcs, vol. 67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 7:1–7:31 (2017)
[2]
Bitansky N and Chiesa A Safavi-Naini R and Canetti R Succinct arguments from multi-prover interactive proofs and their efficiency benefits Advances in Cryptology – CRYPTO 2012 2012 Heidelberg Springer 255-272
[3]
Bootle J, Cerulli A, Ghadafi E, Groth J, Hajiabadi M, and Jakobsen SK Takagi T and Peyrin T Linear-time zero-knowledge proofs for arithmetic circuit satisfiability Advances in Cryptology – ASIACRYPT 2017 2017 Cham Springer 336-365
[4]
Ben-Sasson E, Chiesa A, Goldberg L, Gur T, Riabzev M, and Spooner N Hofheinz D and Rosen A Linear-size constant-query IOPs for delegating computation Theory of Cryptography 2019 Cham Springer 494-521
[5]
Bootle J, Chiesa A, and Groth J Pass R and Pietrzak K Linear-time arguments with sublinear verification from tensor codes Theory of Cryptography 2020 Cham Springer 19-46
[6]
Bootle, J., Chiesa, A., Liu, S.: Zero-knowledge succinct arguments with a linear-time prover. ePrint 2020, 1527 (2020)
[7]
Ben-Sasson E, Chiesa A, Riabzev M, Spooner N, Virza M, and Ward NP Ishai Y and Rijmen V Aurora: transparent succinct arguments for R1CS Advances in Cryptology – EUROCRYPT 2019 2019 Cham Springer 103-128
[8]
Ben-Sasson E, Chiesa A, and Spooner N Hirt M and Smith A Interactive oracle proofs Theory of Cryptography 2016 Heidelberg Springer 31-60
[9]
Ben-Or M et al. Goldwasser S et al. Everything provable is provable in zero-knowledge Advances in Cryptology — CRYPTO’ 88 1990 New York Springer 37-56
[10]
Block AR, Holmgren J, Rosen A, Rothblum RD, and Soni P Pass R and Pietrzak K Public-coin zero-knowledge arguments with (almost) minimal time and space overheads Theory of Cryptography 2020 Cham Springer 168-197
[11]
Block AR, Holmgren J, Rosen A, Rothblum RD, and Soni P Malkin T and Peikert C Time- and space-efficient arguments from groups of unknown order Advances in Cryptology – CRYPTO 2021 2021 Cham Springer 123-152
[12]
Baum C, Malozemoff AJ, Rosen MB, and Scholl P Malkin T and Peikert C : zero-knowledge proofs for Boolean and arithmetic circuits with nested disjunctions Advances in Cryptology – CRYPTO 2021 2021 Cham Springer 92-122
[13]
Damgård I, Ishai Y, and Krøigaard M Gilbert H Perfectly secure multiparty computation and the computational overhead of cryptography Advances in Cryptology – EUROCRYPT 2010 2010 Heidelberg Springer 445-465
[14]
Dittmer, S., Ishai, Y., Ostrovsky, R.: Line-point zero knowledge and its applications. In: 2nd Conference on Information-Theoretic Cryptography, ITC 2021, 23–26 July 2021, Virtual Conference. LIPIcs, vol. 199. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 5:1–5:24 (2021)
[15]
Dinur I, Sudan M, and Wigderson A Díaz J, Jansen K, Rolim JDP, and Zwick U Robust local testability of tensor products of LDPC codes Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 2006 Heidelberg Springer 304-315
[16]
Ephraim N, Freitag C, Komargodski I, and Pass R Canteaut A and Ishai Y SPARKs: succinct parallelizable arguments of knowledge Advances in Cryptology – EUROCRYPT 2020 2020 Cham Springer 707-737
[17]
Franzese, N., Katz, J., Lu, S., Ostrovsky, R., Wang, X., Weng, C.: Constant-overhead zero-knowledge for RAM programs. ePrint 979 (2021)
[18]
Golovnev, A., Lee, J., Setty, S., Thaler, J., Wahby, R.S.: Brakedown: linear-time and post-quantum snarks for R1CS, Cryptology ePrint Archive, Report 2021/1043 (2021). https://ia.cr/2021/1043
[19]
Goldwasser S, Micali S, and Rackoff C The knowledge complexity of interactive proof systems SIAM J. Comput. 1989 18 1 186-208
[20]
Gur, T., Ramnarayan, G., Rothblum, R.D.: Relaxed locally correctable codes. In: ITCS 2018, pp. 27:1–27:11 (2018)
[21]
Holmgren, J., Rothblum, R.: Delegating computations with (almost) minimal time and space overhead. In: Thorup, M. (ed.) FOCS 2018. IEEE Computer Society, pp. 124–135 (2018)
[22]
Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. In: Dwork, C. (ed.) STOC 2008. ACM, pp. 433–442 (2008)
[23]
Ishai Y, Kushilevitz E, Ostrovsky R, and Sahai A Zero-knowledge proofs from secure multiparty computation SIAM J. Comput. 2009 39 3 1121-1152
[24]
Ishai, Y.: Zero-knowledge proofs from information-theoretic proof systems (2020). https://zkproof.org/2020/08/12/information-theoretic-proof-systems
[25]
Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: STOC 1992, pp. 723–732 (1992)
[26]
Lee, J., Setty, S., Thaler, J., Wahby, R.: Linear-time zero-knowledge snarks for R1CS. Cryptology ePrint Archive, Report 2021/030 (2021). https://eprint.iacr.org/2021/030
[27]
Micali S Computationally sound proofs SIAM J. Comput. 2000 30 4 1253-1298
[28]
Ron-Zewi, N., Rothblum, R.D.: Proving as fast as computing: succinct arguments with constant prover overhead. ePrint 1673 (2021)
[29]
Reingold, O., Rothblum, G.N., Rothblum, R.D.: Constant-round interactive proofs for delegating computation. SIAM J. Comput. 50(3) (2021)
[30]
Shoup, V.: New algorithms for finding irreducible polynomials over finite fields. In: FOCS 1988, pp. 283–290 (1988)
[31]
Daniel A Spielman, Linear-time encodable and decodable error-correcting codes IEEE Trans. Inf. Theory 1996 42 6 1723-1731
[32]
Sudan, M.: Algorithmic introduction to coding theory (lecture notes) (2001)
[33]
Thaler, J.: Proofs, arguments, and zero-knowledge (2021). https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.html
[34]
Viderman M A combination of testability and decodability by tensor products Random Struct. Algorithms 2015 46 3 572-598
[35]
Weng, C., Yang, K., Katz, J., Wang, X.: Wolverine: fast, scalable, and communication-efficient zero-knowledge proofs for Boolean and arithmetic circuits. In: SP 2021, pp. 1074–1091. IEEE (2021)
[36]
Xie T, Zhang J, Zhang Y, Papamanthou C, and Song D Boldyreva A and Micciancio D Libra: succinct zero-knowledge proofs with optimal prover computation Advances in Cryptology – CRYPTO 2019 2019 Cham Springer 733-764
[37]
Yang, K., Sarkar, P., Weng, C., Wang, X.: QuickSilver: efficient and affordable zero-knowledge proofs for circuits and polynomials over any field. ePrint 76 (2021)
[38]
Zhang, J., Wang, W., Zhang, Y., Zhang, Y.: Doubly efficient interactive proofs for general arithmetic circuits with linear prover time. ePrint 2020, 1247 (2020)
Index Terms
- Faster Sounder Succinct Arguments and s
Index terms have been assigned to the content through auto-classification.
Recommendations
Succinct Non-Interactive Arguments via Linear Interactive Proofs
AbstractSuccinct non-interactive arguments (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 ...
Interactive Oracle Arguments in the QROM and Applications to Succinct Verification of Quantum Computation
Topics in Cryptology – CT-RSA 2024AbstractThis work is motivated by the following question: can an untrusted quantum server convince a classical verifier of the answer to an efficient quantum computation using only polylogarithmic communication? We show how to achieve this in the quantum ...
Lattice-Based Succinct Arguments for NP with Polylogarithmic-Time Verification
Advances in Cryptology – CRYPTO 2023AbstractSuccinct arguments that rely on the Merkle-tree paradigm introduced by Kilian (STOC 92) suffer from larger proof sizes in practice due to the use of generic cryptographic primitives. In contrast, succinct arguments with the smallest proof sizes in ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Aug 2022
821 pages
© International Association for Cryptologic Research 2022.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 15 August 2022
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025