Transparent SNARKs from DARK compilers. (English) Zbl 1542.94111
Canteaut, Anne (ed.) et al., Advances in cryptology – EUROCRYPT 2020. 39th annual international conference on the theory and applications of cryptographic techniques, Zagreb, Croatia, May 10–14, 2020. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 12105, 677-706 (2020).
Summary: We construct a new polynomial commitment scheme for univariate and multivariate polynomials over finite fields, with logarithmic size evaluation proofs and verification time, measured in the number of coefficients of the polynomial. The underlying technique is a Diophantine Argument of Knowledge (DARK), leveraging integer representations of polynomials and groups of unknown order. Security is shown from the strong RSA and the adaptive root assumptions. Moreover, the scheme does not require a trusted setup if instantiated with class groups. We apply this new cryptographic compiler to a restricted class of algebraic linear IOPs, which we call Polynomial IOPs, to obtain doubly-efficient public-coin interactive arguments of knowledge for any NP relation with succinct communication. With linear preprocessing, the online verifier’s work is logarithmic in the circuit complexity of the relation.
There are many existing examples of Polynomial IOPs (PIOPs) dating back to the first PCP [L. Babai, STOC 1991, 21–31 (1991; doi:10.1145/103418.103428)]. We present a generic compilation of any PIOP using our DARK polynomial commitment scheme. In particular, compiling the PIOP from PLONK [A. Gabizon, Z. J. Williamson and O. Ciobotaru, “PLONK: permutations over Lagrange-bases for oecumenical noninteractive arguments of knowledge”, Preprint, Cryptology ePrint Archive, Report 2019/953, https://eprint.iacr.org/2019/953], an improvement on Sonic [M. Maller et al., “Sonic: zero-knowledge SNARKs from linear-size universal and updatable structured reference strings”, Preprint, https://eprint.iacr.org/2019/099], yields a public-coin interactive argument with quasi-linear preprocessing, quasi-linear (online) prover time, logarithmic communication, and logarithmic (online) verification time in the circuit size. Applying Fiat-Shamir results in a SNARK, which we call Supersonic.
Supersonic is also concretely efficient with 10 KB proofs and under 100 ms verification time for circuits with 1 million gates (estimated for 120-bit security). Most importantly, this SNARK is transparent: it does not require a trusted setup. We obtain zk-SNARKs by applying a hiding variant of our polynomial commitment scheme with zero-knowledge evaluations. Supersonic is the first complete zk-SNARK system that has both a practical prover time as well as asymptotically logarithmic proof size and verification time.
For the entire collection see [Zbl 1475.94008].
There are many existing examples of Polynomial IOPs (PIOPs) dating back to the first PCP [L. Babai, STOC 1991, 21–31 (1991; doi:10.1145/103418.103428)]. We present a generic compilation of any PIOP using our DARK polynomial commitment scheme. In particular, compiling the PIOP from PLONK [A. Gabizon, Z. J. Williamson and O. Ciobotaru, “PLONK: permutations over Lagrange-bases for oecumenical noninteractive arguments of knowledge”, Preprint, Cryptology ePrint Archive, Report 2019/953, https://eprint.iacr.org/2019/953], an improvement on Sonic [M. Maller et al., “Sonic: zero-knowledge SNARKs from linear-size universal and updatable structured reference strings”, Preprint, https://eprint.iacr.org/2019/099], yields a public-coin interactive argument with quasi-linear preprocessing, quasi-linear (online) prover time, logarithmic communication, and logarithmic (online) verification time in the circuit size. Applying Fiat-Shamir results in a SNARK, which we call Supersonic.
Supersonic is also concretely efficient with 10 KB proofs and under 100 ms verification time for circuits with 1 million gates (estimated for 120-bit security). Most importantly, this SNARK is transparent: it does not require a trusted setup. We obtain zk-SNARKs by applying a hiding variant of our polynomial commitment scheme with zero-knowledge evaluations. Supersonic is the first complete zk-SNARK system that has both a practical prover time as well as asymptotically logarithmic proof size and verification time.
For the entire collection see [Zbl 1475.94008].
References:
| [1] | Zcash. https://z.cash |
| [2] | Barić, N.; Pfitzmann, B.; Fumy, W., Collision-free accumulators and fail-stop signature schemes without trees, Advances in Cryptology — EUROCRYPT ’97, 480-494 (1997), Heidelberg: Springer, Heidelberg · doi:10.1007/3-540-69053-0_33 |
| [3] | Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Fast reed-solomon interactive oracle proofs of proximity. In: Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) ICALP 2018. LIPIcs, vol. 107, pp. 14:1-14:17. Schloss Dagstuhl, July 2018 · Zbl 1499.68141 |
| [4] | Ben-Sasson, E.; Bentov, I.; Horesh, Y.; Riabzev, M.; Boldyreva, A.; Micciancio, D., Scalable zero knowledge with no trusted setup, Advances in Cryptology - CRYPTO 2019, 701-732 (2019), Cham: Springer, Cham · Zbl 1509.94063 · doi:10.1007/978-3-030-26954-8_23 |
| [5] | Ben-Sasson, E., et al.: Zerocash: decentralized anonymous payments from bitcoin. In: 2014 IEEE Symposium on Security and Privacy, pp. 459-474. IEEE Computer Society Press, May 2014 |
| [6] | Ben-Sasson, E.; Chiesa, A.; Genkin, D.; Tromer, E.; Virza, M.; Canetti, R.; Garay, JA, SNARKs for C: verifying program executions succinctly and in zero knowledge, Advances in Cryptology - CRYPTO 2013, 90-108 (2013), Heidelberg: Springer, Heidelberg · Zbl 1317.68050 · doi:10.1007/978-3-642-40084-1_6 |
| [7] | Ben-Sasson, E.; Chiesa, A.; Spooner, N.; Hirt, M.; Smith, A., Interactive oracle proofs, Theory of Cryptography, 31-60 (2016), Heidelberg: Springer, Heidelberg · Zbl 1397.94048 · doi:10.1007/978-3-662-53644-5_2 |
| [8] | Biasse, J., Jacobson Jr., M.J., Silvester, A.K.: Security estimates for quadratic field based cryptosystems. CoRR abs/1004.5512 (2010). http://arxiv.org/abs/1004.5512 |
| [9] | Bitansky, N.; Chiesa, A.; Ishai, Y.; Paneth, O.; Ostrovsky, R.; Sahai, A., Succinct non-interactive arguments via linear interactive proofs, Theory of Cryptography, 315-333 (2013), Heidelberg: Springer, Heidelberg · Zbl 1316.68056 · doi:10.1007/978-3-642-36594-2_18 |
| [10] | Boneh, D.; Bonneau, J.; Bünz, B.; Fisch, B.; Shacham, H.; Boldyreva, A., Verifiable delay functions, Advances in Cryptology - CRYPTO 2018, 757-788 (2018), Cham: Springer, Cham · Zbl 1444.94046 · doi:10.1007/978-3-319-96884-1_25 |
| [11] | Boneh, D.; Boyle, E.; Corrigan-Gibbs, H.; Gilboa, N.; Ishai, Y.; Boldyreva, A.; Micciancio, D., Zero-knowledge proofs on secret-shared data via fully linear PCPs, Advances in Cryptology - CRYPTO 2019, 67-97 (2019), Cham: Springer, Cham · Zbl 1436.94043 · doi:10.1007/978-3-030-26954-8_3 |
| [12] | Boneh, D.; Bünz, B.; Fisch, B.; Boldyreva, A.; Micciancio, D., Batching techniques for accumulators with applications to IOPs and stateless blockchains, Advances in Cryptology - CRYPTO 2019, 561-586 (2019), Cham: Springer, Cham · Zbl 1456.94051 · doi:10.1007/978-3-030-26948-7_20 |
| [13] | Bootle, J., Cerulli, A., Chaidos, P., Groth, J., Petit, C.: Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. Cryptology ePrint Archive, Report 2016/263 (2016). http://eprint.iacr.org/2016/263 · Zbl 1369.94520 |
| [14] | Bootle, J.; Cerulli, A.; Chaidos, P.; Groth, J.; Petit, C.; Fischlin, M.; Coron, JS, Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting, Advances in Cryptology - EUROCRYPT 2016, 327-357 (2016), Heidelberg: Springer, Heidelberg · Zbl 1369.94520 |
| [15] | Bosma, W.; Stevenhagen, P., On the computation of quadratic 2-class groups, J. Theor. Nombr., 8, 283-313 (1996) · Zbl 0870.11080 |
| [16] | Bowe, S.: Bellman zk-SNARKS library (2016). https://github.com/zkcrypto/bellman |
| [17] | Buchmann, J., Hamdy, S.: A survey on IQ cryptography. In: Public-Key Cryptography and Computational Number Theory, pp. 1-15 (2001) · Zbl 0983.94034 |
| [18] | Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: 2018 IEEE Symposium on Security and Privacy, pp. 315-334. IEEE Computer Society Press, May 2018 |
| [19] | Bünz, B., Fisch, B., Szepieniec, A.: Transparent SNARKs from DARK compilers. Cryptology ePrint Archive, Report 2019/1229 (2019). https://eprint.iacr.org/2019/1229 · Zbl 1542.94111 |
| [20] | Buterin, V.: ZK rollup (2016). https://ethresear.ch/t/on-chain-scaling-to-potentially-500-tx-sec-through-mass-tx-validation/3477 |
| [21] | Canetti, R., et al.: Fiat-Shamir: from practice to theory. In: Charikar, M., Cohen, E. (eds.) 51st ACM STOC, pp. 1082-1090. ACM Press, June 2019 · Zbl 1434.94060 |
| [22] | Chiesa, A., Hu, Y., Maller, M., Mishra, P., Vesely, N., Ward, N.: Marlin: preprocessing zkSNARKs with universal and updatable SRS. Cryptology ePrint Archive, Report 2019/1047 (2019). https://eprint.iacr.org/2019/1047 · Zbl 1541.94048 |
| [23] | Chiesa, A., Ojha, D., Spooner, N.: Fractal: post-quantum and transparent recursive proofs from holography (2019). https://eprint.iacr.org/2019/1076 · Zbl 1539.68118 |
| [24] | Couteau, G.; Peters, T.; Pointcheval, D.; Coron, J-S; Nielsen, JB, Removing the strong RSA assumption from arguments over the integers, Advances in Cryptology - EUROCRYPT 2017, 321-350 (2017), Cham: Springer, Cham · Zbl 1415.94420 · doi:10.1007/978-3-319-56614-6_11 |
| [25] | Damgård, I.; Fujisaki, E.; Zheng, Y., A statistically-hiding integer commitment scheme based on groups with hidden order, Advances in Cryptology — ASIACRYPT 2002, 125-142 (2002), Heidelberg: Springer, Heidelberg · Zbl 1065.94545 · doi:10.1007/3-540-36178-2_8 |
| [26] | Damgård, I.; Koprowski, M.; Knudsen, LR, Generic lower bounds for root extraction and signature schemes in general groups, Advances in Cryptology — EUROCRYPT 2002, 256-271 (2002), Heidelberg: Springer, Heidelberg · Zbl 1055.94026 · doi:10.1007/3-540-46035-7_17 |
| [27] | Eberhardt, J.: Zokrates. https://zokrates.github.io/ |
| [28] | Fiat, A.; Shamir, A.; Odlyzko, AM, How to prove yourself: practical solutions to identification and signature problems, Advances in Cryptology — CRYPTO ’86, 186-194 (1987), Heidelberg: Springer, Heidelberg · Zbl 0636.94012 · doi:10.1007/3-540-47721-7_12 |
| [29] | Fujisaki, E.; Okamoto, T.; Kaliski, BS, Statistical zero knowledge protocols to prove modular polynomial relations, Advances in Cryptology — CRYPTO ’97, 16-30 (1997), Heidelberg: Springer, Heidelberg · Zbl 0880.94007 · doi:10.1007/BFb0052225 |
| [30] | Gabizon, A., Williamson, Z.J., Ciobotaru, O.: PLONK: permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. Cryptology ePrint Archive, Report 2019/953 (2019). https://eprint.iacr.org/2019/953 |
| [31] | Gennaro, R.; Gentry, C.; Parno, B.; Raykova, M.; Johansson, T.; Nguyen, PQ, Quadratic span programs and succinct NIZKs without PCPs, Advances in Cryptology - EUROCRYPT 2013, 626-645 (2013), Heidelberg: Springer, Heidelberg · Zbl 1300.94056 · doi:10.1007/978-3-642-38348-9_37 |
| [32] | Goldreich, O.; Vadhan, S.; Wigderson, A., On interactive proofs with a laconic prover, Comput. Complex., 11, 1-2, 1-53 (2002) · Zbl 1053.68045 |
| [33] | Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 113-122. ACM Press, May 2008 · Zbl 1231.68135 |
| [34] | Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems (extended abstract). In: 17th ACM STOC, pp. 291-304. ACM Press, May 1985 · Zbl 0900.94025 |
| [35] | Groth, J.; Fischlin, M.; Coron, J-S, On the size of pairing-based non-interactive arguments, Advances in Cryptology - EUROCRYPT 2016, 305-326 (2016), Heidelberg: Springer, Heidelberg · Zbl 1369.94539 · doi:10.1007/978-3-662-49896-5_11 |
| [36] | Groth, J.; Ishai, Y.; Smart, N., Sub-linear zero-knowledge argument for correctness of a shuffle, Advances in Cryptology - EUROCRYPT 2008, 379-396 (2008), Heidelberg: Springer, Heidelberg · Zbl 1149.94319 · doi:10.1007/978-3-540-78967-3_22 |
| [37] | Hopwood, D., Bowe, S., Hornby, T., Wilcox, N.: Zcash protocol specification (2019). https://zips.z.cash/protocol/protocol.pdf |
| [38] | Ishai, Y., Kushilevitz, E., Ostrovsky, R.: Efficient arguments without short PCPs (2007) |
| [39] | Kate, A.; Zaverucha, GM; Goldberg, I.; Abe, M., Constant-size commitments to polynomials and their applications, Advances in Cryptology - ASIACRYPT 2010, 177-194 (2010), Heidelberg: Springer, Heidelberg · Zbl 1253.94054 · doi:10.1007/978-3-642-17373-8_11 |
| [40] | Labs, O.: Coda protocol (2018). https://codaprotocol.com/ |
| [41] | Lindell, Y.; Kilian, J., Parallel coin-tossing and constant-round secure two-party computation, Advances in Cryptology — CRYPTO 2001, 171-189 (2001), Heidelberg: Springer, Heidelberg · Zbl 1002.94521 · doi:10.1007/3-540-44647-8_10 |
| [42] | Lipmaa, H.; Laih, C-S, On diophantine complexity and statistical zero-knowledge arguments, Advances in Cryptology - ASIACRYPT 2003, 398-415 (2003), Heidelberg: Springer, Heidelberg · Zbl 1205.68165 · doi:10.1007/978-3-540-40061-5_26 |
| [43] | Maller, M., Bowe, S., Kohlweiss, M., Meiklejohn, S.: Sonic: zero-knowledge snarks from linear-size universal and updatable structured reference strings. Cryptology ePrint Archive, Report 2019/099 (2019). https://eprint.iacr.org/2019/099 |
| [44] | Pietrzak, K.: Simple verifiable delay functions. In: 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, San Diego, California, USA, 10-12 January 2019, pp. 60:1-60:15 (2019) · Zbl 07559103 |
| [45] | Reingold, O., Rothblum, G.N., Rothblum, R.D.: Constant-round interactive proofs for delegating computation. In: Wichs, D., Mansour, Y. (eds.) 48th ACM STOC, pp. 49-62. ACM Press, June 2016 · Zbl 1373.68274 |
| [46] | Rivest, R., Shamir, A., Wagner, D.: Time-lock puzzles and timed-release crypto. MIT Technical report (1996) |
| [47] | Setty, S., Braun, B., Vu, V., Blumberg, A.J., Parno, B., Walfish, M.: Resolving the conflict between generality and plausibility in verified computation (2013) |
| [48] | Setty, S.: Spartan: efficient and general-purpose zKSNARKs without trusted setup. Cryptology ePrint Archive, Report 2019/550 (2019). https://eprint.iacr.org/2019/550 |
| [49] | Straka, M.: Class groups for cryptographic accumulators (2019). https://www.michaelstraka.com/posts/classgroups/ |
| [50] | Vlasov, A., Panarin, K.: Transparent polynomial commitment scheme with polylogarithmic communication complexity. Cryptology ePrint Archive, Report 2019/1020 (2019). https://eprint.iacr.org/2019/1020 |
| [51] | Wahby, R.S., Tzialla, I., shelat, A., Thaler, J., Walfish, M.: Doubly-efficient zkSNARKs without trusted setup. In: 2018 IEEE Symposium on Security and Privacy, pp. 926-943. IEEE Computer Society Press, May 2018 |
| [52] | Walfish, M.; Blumberg, AJ, Verifying computations without reexecuting them: from theoretical possibility to near practicality, Commun. ACM, 58, 2, 74-84 (2015) |
| [53] | Wesolowski, B.; Ishai, Y.; Rijmen, V., Efficient verifiable delay functions, Advances in Cryptology - EUROCRYPT 2019, 379-407 (2019), Cham: Springer, Cham · Zbl 1509.94139 · doi:10.1007/978-3-030-17659-4_13 |
| [54] | Wilcox, Z.: The design of the ceremony (2016). https://z.cash/blog/the-design-of-the-ceremony.html |
| [55] | Xie, T., Zhang, J., Zhang, Y., Papamanthou, C., Song, D.: Libra: succinct zero-knowledge proofs with optimal prover computation. Cryptology ePrint Archive, Report 2019/317 (2019). https://eprint.iacr.org/2019/317 · Zbl 1509.94140 |
| [56] | Zhang, J., Xie, T., Zhang, Y., Song, D.: Transparent polynomial delegation and its applications to zero knowledge proof. Cryptology ePrint Archive, Report 2019/1482 (2019). https://eprint.iacr.org/2019/1482 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
