Proofs for inner pairing products and applications. (English) Zbl 1514.94052
Tibouchi, Mehdi (ed.) et al., Advances in cryptology – ASIACRYPT 2021. 27th international conference on the theory and application of cryptology and information security, Singapore, December 6–10, 2021. Proceedings. Part III. Cham: Springer. Lect. Notes Comput. Sci. 13092, 65-97 (2021).
Summary: We present a generalized inner product argument and demonstrate its applications to pairing-based languages. We apply our generalized argument to prove that an inner pairing product is correctly evaluated with respect to committed vectors of \(n\) source group elements. With a structured reference string (SRS), we achieve a logarithmic-time verifier whose work is dominated by \(6 \log n\) target group exponentiations. Proofs are of size \(6 \log n\) target group elements, computed using \(6n\) pairings and \(4n\) exponentiations in each source group.
We apply our inner product arguments to build the first polynomial commitment scheme with succinct (logarithmic) verification, \(O(\sqrt{d})\) prover complexity for degree \(d\) polynomials (not including the cost to evaluate the polynomial), and a SRS of size \(O(\sqrt{d})\). Concretely, this means that for \(d=2^{28}\), producing an evaluation proof in our protocol is \(76\times\) faster than doing so in the KZG commitment scheme, and the CRS in our protocol is \(1000\times\) smaller: 13 MB vs 13 GB for KZG.
As a second application, we introduce an argument for aggregating \(n\) Groth16 zkSNARKs into an \(O(\log n)\) sized proof. Our protocol is significantly faster \(({>}1000\times)\) than aggregating SNARKs via recursive composition: we aggregate \({\sim}130,000\) proofs in 25 min, versus 90 proofs via recursive composition. Finally, we further apply our aggregation protocol to construct a low-memory SNARK for machine computations that does not rely on recursive composition. For a computation that requires time \(T\) and space \(S\), our SNARK produces proofs in space \(\tilde{\mathcal{O}}(S+T)\), which is significantly more space efficient than a monolithic SNARK, which requires space \(\tilde{\mathcal{O}}(S \cdot T)\).
For the entire collection see [Zbl 1510.94004].
We apply our inner product arguments to build the first polynomial commitment scheme with succinct (logarithmic) verification, \(O(\sqrt{d})\) prover complexity for degree \(d\) polynomials (not including the cost to evaluate the polynomial), and a SRS of size \(O(\sqrt{d})\). Concretely, this means that for \(d=2^{28}\), producing an evaluation proof in our protocol is \(76\times\) faster than doing so in the KZG commitment scheme, and the CRS in our protocol is \(1000\times\) smaller: 13 MB vs 13 GB for KZG.
As a second application, we introduce an argument for aggregating \(n\) Groth16 zkSNARKs into an \(O(\log n)\) sized proof. Our protocol is significantly faster \(({>}1000\times)\) than aggregating SNARKs via recursive composition: we aggregate \({\sim}130,000\) proofs in 25 min, versus 90 proofs via recursive composition. Finally, we further apply our aggregation protocol to construct a low-memory SNARK for machine computations that does not rely on recursive composition. For a computation that requires time \(T\) and space \(S\), our SNARK produces proofs in space \(\tilde{\mathcal{O}}(S+T)\), which is significantly more space efficient than a monolithic SNARK, which requires space \(\tilde{\mathcal{O}}(S \cdot T)\).
For the entire collection see [Zbl 1510.94004].
References:
| [1] | Abe, M.; Fuchsbauer, G.; Groth, J.; Haralambiev, K.; Ohkubo, M., Structure-preserving signatures and commitments to group elements, J. Cryptol., 29, 2, 363-421 (2015) · Zbl 1355.94042 · doi:10.1007/s00145-014-9196-7 |
| [2] | Attema, T., Cramer, R.: Compressed \(\Sigma \)-protocol theory and practical application to plug & play secure algorithmics. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 513-543. Springer, Cham (2020). doi:10.1007/978-3-030-56877-1_18 · Zbl 1504.94095 |
| [3] | Backes, M.; Datta, A.; Kate, A.; Dawson, E., Asynchronous computational VSS with reduced communication complexity, Topics in Cryptology - CT-RSA 2013, 259-276 (2013), Heidelberg: Springer, Heidelberg · Zbl 1312.94109 · doi:10.1007/978-3-642-36095-4_17 |
| [4] | Bünz, B.; Fisch, B.; Szepieniec, A.; Canteaut, A.; Ishai, Y., Transparent SNARKs from DARK compilers, Advances in Cryptology - EUROCRYPT 2020, 677-706 (2020), Cham: Springer, Cham · Zbl 1542.94111 · doi:10.1007/978-3-030-45721-1_24 |
| [5] | Bayer, S.; Groth, J.; Johansson, T.; Nguyen, PQ, Zero-knowledge argument for polynomial evaluation with application to blacklists, Advances in Cryptology - EUROCRYPT 2013, 646-663 (2013), Heidelberg: Springer, Heidelberg · Zbl 1300.94040 · doi:10.1007/978-3-642-38348-9_38 |
| [6] | Bowe, S., Grigg, J., Hopwood, D.: Halo: recursive proof composition without a trusted setup. eprint 2019/1021 |
| [7] | Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: Recursive composition and bootstrapping for SNARKs and proof-carrying data. In: STOC 2013 (2013) · Zbl 1293.68264 |
| [8] | Blum, M., Evans, W., Gemmell, P., Kannan, S., Naor, M.: Checking the correctness of memories. In: FOCS 1991 (1991) · Zbl 1323.68200 |
| [9] | Bonneau, J., Meckler, I., Rao, V., Shapiro, E.: Coda: decentralized cryptocurrency at scale. eprint 2020/352 |
| [10] | Bootle, J.; Cerulli, A.; Chaidos, P.; Groth, J.; Petit, C.; Fischlin, M.; Coron, J-S, 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 · doi:10.1007/978-3-662-49896-5_12 |
| [11] | Bowe, S., Chiesa, A., Green, M., Miers, I., Mishra, P., Wu, H.: ZEXE: enabling decentralized private computation. In: S&P 2020 (2020) |
| [12] | Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: S&P 2018 (2018) |
| [13] | Bünz, B., Maller, M., Mishra, P., Tyagi, N., Vesely, P.: Proofs for inner pairing products and applications. eprint 2019/1177 |
| [14] | Bünz, B., Chiesa, A., Mishra, P., Spooner, N.: Proof-carrying data from accumulation schemes. In: TCC 2020 (2020) · Zbl 1485.94132 |
| [15] | Camenisch, J.; Dubovitskaya, M.; Haralambiev, K.; Kohlweiss, M.; Iwata, T.; Cheon, JH, Composable and modular anonymous credentials: definitions and practical constructions, Advances in Cryptology - ASIACRYPT 2015, 262-288 (2015), Heidelberg: Springer, Heidelberg · Zbl 1375.94107 · doi:10.1007/978-3-662-48800-3_11 |
| [16] | Chiesa, A.; Hu, Y.; Maller, M.; Mishra, P.; Vesely, N.; Ward, N.; Canteaut, A.; Ishai, Y., Marlin: preprocessing zkSNARKs with universal and updatable SRS, Advances in Cryptology - EUROCRYPT 2020, 738-768 (2020), Cham: Springer, Cham · Zbl 1541.94048 · doi:10.1007/978-3-030-45721-1_26 |
| [17] | Chiesa, A.; Ojha, D.; Spooner, N.; Canteaut, A.; Ishai, Y., Fractal: post-quantum and transparent recursive proofs from holography, Advances in Cryptology - EUROCRYPT 2020, 769-793 (2020), Cham: Springer, Cham · Zbl 1539.68118 · doi:10.1007/978-3-030-45721-1_27 |
| [18] | Fuchsbauer, G.; Hanser, C.; Slamanig, D., Structure-preserving signatures on equivalence classes and constant-size anonymous credentials, J. Cryptol., 32, 2, 498-546 (2018) · Zbl 1434.94066 · doi:10.1007/s00145-018-9281-4 |
| [19] | Fisch, B.: Poreps: proofs of space on useful data. eprint 2018/678 |
| [20] | Fisch, B.; Ishai, Y.; Rijmen, V., Tight proofs of space and replication, Advances in Cryptology - EUROCRYPT 2019, 324-348 (2019), Cham: Springer, Cham · Zbl 1509.94086 · doi:10.1007/978-3-030-17656-3_12 |
| [21] | Fuchsbauer, G.; Kiltz, E.; Loss, J.; Shacham, H.; Boldyreva, A., The algebraic group model and its applications, Advances in Cryptology - CRYPTO 2018, 33-62 (2018), Cham: Springer, Cham · Zbl 1430.94068 · doi:10.1007/978-3-319-96881-0_2 |
| [22] | Gurkan, K., Gabizon, A., Williamson, Z.: Cheon’s attack and its effect on the security of big trusted setups. https://ethresear.ch/t/cheons-attack-and-its-effect-on-the-security-of-big-trusted-setups/6692 |
| [23] | Groth, J.; Maller, M.; Katz, J.; Shacham, H., Snarky signatures: minimal signatures of knowledge from simulation-extractable SNARKs, Advances in Cryptology - CRYPTO 2017, 581-612 (2017), Cham: Springer, Cham · Zbl 1410.94077 · doi:10.1007/978-3-319-63715-0_20 |
| [24] | Gailly, N., Maller, M., Nitulescu, A.: SnarkPack: practical SNARK aggregation. eprint 2021/529 |
| [25] | Groth, J.; Kohlweiss, M.; Maller, M.; Meiklejohn, S.; Miers, I.; Shacham, H.; Boldyreva, A., Updatable and universal common reference strings with applications to zk-SNARKs, Advances in Cryptology - CRYPTO 2018, 698-728 (2018), Cham: Springer, Cham · Zbl 1457.94137 · doi:10.1007/978-3-319-96878-0_24 |
| [26] | Groth, J.; Lee, DH; Wang, X., Efficient zero-knowledge arguments from two-tiered homomorphic commitments, Advances in Cryptology - ASIACRYPT 2011, 431-448 (2011), Heidelberg: Springer, Heidelberg · Zbl 1227.94047 · doi:10.1007/978-3-642-25385-0_23 |
| [27] | 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 |
| [28] | Groth, J.; Sahai, A.; Smart, N., Efficient non-interactive proof systems for bilinear groups, Advances in Cryptology - EUROCRYPT 2008, 415-432 (2008), Heidelberg: Springer, Heidelberg · Zbl 1149.94320 · doi:10.1007/978-3-540-78967-3_24 |
| [29] | Gabizon, A., Williamson, Z.J., Ciobotaru, O.: PLONK: permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. eprint 2019/953 |
| [30] | 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 |
| [31] | Lee, J.: Dory: efficient, transparent arguments for generalised inner products and polynomial commitments. eprint 2020/1274 |
| [32] | Lai, R.W.F., Malavolta, G., Ronge, V.: Succinct arguments for bilinear group arithmetic: practical structure-preserving cryptography. In: CCS 2019 (2019) |
| [33] | Libert, B.; Yung, M.; Micciancio, D., Concise mercurial vector commitments and independent zero-knowledge sets with short proofs, Theory of Cryptography, 499-517 (2010), Heidelberg: Springer, Heidelberg · Zbl 1274.94093 · doi:10.1007/978-3-642-11799-2_30 |
| [34] | Maller, M., Bowe, S., Kohlweiss, M., Meiklejohn, S.: Sonic: zero-knowledge snarks from linear-size universal and updatable structured reference strings. In: CCS 2019 (2019) |
| [35] | O’Leary, R.: Monero to become first billion-dollar crypto to implement ‘bulletproofs’ tech. https://www.coindesk.com/monero-to-become-first-billion-dollar-crypto-to-implement-bulletproofs-tech |
| [36] | Parno, B., Gentry, C., Howell, J., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: S&P 2013 (2013) |
| [37] | Pedersen, TP; Feigenbaum, J., Non-interactive and information-theoretic secure verifiable secret sharing, Advances in Cryptology — CRYPTO ’91, 129-140 (1992), Heidelberg: Springer, Heidelberg · Zbl 0763.94015 · doi:10.1007/3-540-46766-1_9 |
| [38] | Setty, S.; Micciancio, D.; Ristenpart, T., Spartan: efficient and general-purpose zkSNARKs without trusted setup, Advances in Cryptology - CRYPTO 2020, 704-737 (2020), Cham: Springer, Cham · Zbl 1504.94185 · doi:10.1007/978-3-030-56877-1_25 |
| [39] | Srinivasan, S., Chepurnoy, A., Papamanthou, C., Tomescu, A., Zhang, Y.: Hyperproofs: Aggregating and maintaining proofs in vector commitments. eprint 2021/599 |
| [40] | Tyagi, N., Fisch, B., Bonneau, J., Tessaro, S.: Client-auditable verifiable registries. eprint 2021/627 |
| [41] | Wahby, R.S., Tzialla, I., Shelat, A., Thaler, J., Walfish, M.: Doubly-efficient zkSNARKs without trusted setup. In: S&P 2018 (2018) |
| [42] | Whitehat, B.: Roll up: scale Ethereum with SNARKs. https://github.com/barryWhiteHat/roll_up |
| [43] | Wu, H., Zheng, W., Chiesa, A., Popa, R.A., Stoica, I.: DIZK: a distributed zero knowledge proof system. In: USENIX Security 2018 (2018) |
| [44] | Xie, T.; Zhang, J.; Zhang, Y.; Papamanthou, C.; Song, D.; Boldyreva, A.; Micciancio, D., Libra: succinct zero-knowledge proofs with optimal prover computation, Advances in Cryptology - CRYPTO 2019, 733-764 (2019), Cham: Springer, Cham · Zbl 1509.94140 · doi:10.1007/978-3-030-26954-8_24 |
| [45] | Xu, J.; Yang, A.; Zhou, J.; Wong, DS; Askoxylakis, I.; Ioannidis, S.; Katsikas, S.; Meadows, C., Lightweight delegatable proofs of storage, Computer Security - ESORICS 2016, 324-343 (2016), Cham: Springer, Cham · Zbl 1499.68063 · doi:10.1007/978-3-319-45744-4_16 |
| [46] | Zhang, J., Xie, T., Zhang, Y., Song, D.: Transparent polynomial delegation and its applications to zero knowledge proof. In: S&P 2020 (2020) |
| [47] | Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: Fast reductions from RAMs to delegatable succinct constraint satisfaction problems. In: ITCS 2013 (2013) · Zbl 1361.68088 |
| [48] | 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 |
| [49] | Ben-Sasson, E.; Chiesa, A.; Tromer, E.; Virza, M.; Garay, JA; Gennaro, R., Scalable zero knowledge via cycles of elliptic curves, Advances in Cryptology - CRYPTO 2014, 276-294 (2014), Heidelberg: Springer, Heidelberg · Zbl 1334.68077 · doi:10.1007/978-3-662-44381-1_16 |
| [50] | Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Succinct non-interactive zero knowledge for a von Neumann architecture. In: USENIX Security 2014 (2014) · Zbl 1334.68077 |
| [51] | Ben-Sasson, E., et al.: Zerocash: decentralized anonymous payments from Bitcoin. In: SP 2014 (2014) |
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.
