Ways to improve the performance of zero-knowledge succinct non-interactive arguments of knowledge and the analysis of the results achieved. (Ways to improve the performance of zero-knowledge succinct non-interactive arguments of knowledge and the analysis of the rusults achieved.) (Russian. English summary) Zbl 07746256
Summary: We consider ways to improve the performance of zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) based on polynomial sets, such as quadratic arithmetic programs (QAP), square arithmetic programs (SAP), quadratic span programs (QSP), square span programs (SSP), quadratic polynomial programs (QPP), etc. To improve the performance of zk-SNARK, batch data processing methods, various modifications of exponentiation problems, bilinear pairings based on elliptic curves, etc. are used. A comparative analysis of the complexity of the common reference strings formation, the construction and verification of the calculations reliability proofs, as well as the sizes of common reference strings and proofs has been carried out.
Keywords:
succinct non-interactive arguments; performance improvement; performance analysis; size of public parametersReferences:
| [1] | Martynenkov I. V., “Zero-knowledge succinct non-interactive arguments of knowledge based on sets of polynomials”, Prikladnaya Diskretnaya Matematika, 2023, no. 59, 20-57 (in Russian) · Zbl 07724168 |
| [2] | L. Grassi, D. Khovratovich, C. Rechberger et al, Poseidon: A New Hash Function for Zero Knowledge Proof Systems, Cryptology ePrint Archive. Paper 2019/458, |
| [3] | J. Baylina, M. Bellés, 4-bit Window Pedersen Hash On The Baby Jubjub Elliptic Curve, 2019, 8 pp. |
| [4] | O. Regev, “New lattice based cryptographic constructions”, Proc. 35th Ann. ACM Symp. on Theory of Computing, ACM, N.Y., 2003, 407-416 · Zbl 1192.94105 · doi:10.1145/780542.780603 |
| [5] | O. Regev, “New lattice-based cryptographic constructions”, J. ACM, 51:6 (2004), 899-942 · Zbl 1125.94026 · doi:10.1145/1039488.1039490 |
| [6] | O. Regev, “On lattices, learning with errors, random linear codes, and cryptography”, Proc. 37th Ann. ACM Symp. on Theory of Computing, ACM, N.Y., 2005, 84-93 · Zbl 1192.94106 |
| [7] | Y. Zhang, C. Papamanthou, J. Katz, “ALITHEIA: Towards practical verifiable graph processing”, Proc. CCS’14, ACM, N.Y., 2014, 856-867 |
| [8] | J. Groth, “Short pairing-based non-interactive zero-knowledge arguments”, LNCS, 6477, 2010, 321-340 · Zbl 1253.94049 |
| [9] | H. Lipmaa, “Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments”, LNCS, 7194, 2012, 169-189 · Zbl 1303.94090 |
| [10] | N. Pippenger, “On the evaluation of powers and related problems”, 17th Ann. Symp. SFCS’1976 (Houston, TX, USA, 1976), 258-263 |
| [11] | J. Bos, M. Coster, “Addition chain heuristics”, LNCS, 435, 1990, 400-407 |
| [12] | E. Ben-Sasson, A. Chiesa, D. Genkin et al, “SNARKs for C: Verifying program executions succinctly and in zero knowledge”, LNCS, 8043, 2013, 90-108 · Zbl 1317.68050 |
| [13] | B. Parno, J. Howell, C. Gentry, M. Raykova, “Pinocchio: Nearly practical verifiable computation”, Proc. 34th IEEE Symp. on Security and Privacy (Berkeley, CA, USA), 2013, 238-252 |
| [14] | E. Ben-Sasson, A. Chiesa, E. Tromer, M. Virza, Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture, Updated version, · Zbl 1334.68077 |
| [15] | R. Gennaro, C. Gentry, B. Parno, M. Raykova, “Quadratic span programs and succinct NIZKs without PCPs”, LNCS, 7881, 2013, 626-645 · Zbl 1300.94056 |
| [16] | Costello C., Pairings for Beginners, |
| [17] | J. Groth, “On the size of pairing-based non-interactive arguments”, LNCS, 9666, 2016, 305-326 · Zbl 1369.94539 |
| [18] | G. Danezis, C. Fournet, J. Groth, M. Kohlweiss, “Square span programs with applications to succinct NIZK arguments”, LNCS, 8873, 2014, 532-550 · Zbl 1306.94042 |
| [19] | H. Lipmaa, Almost Optimal Short Adaptive Non-Interactive Zero Knowledge, Tech. Rep. 2014/396, International Association for Cryptologic Research, 2014, 20 pp. · Zbl 1378.94054 |
| [20] | R. Gennaro, C. Gentry, B. Parno, “Non-interactive verifiable computing: Outsourcing computation to untrusted workers”, LNCS, 6223, 2010, 465-482 · Zbl 1284.68065 |
| [21] | Lee J. Dory, “Efficient, transparent arguments for generalised inner products and polynomial commitments”, LNCS, 13043, 2021, 1-34 · Zbl 1511.94126 |
| [22] | J. Groth, R. Ostrovsky, A. Sahai, “Perfect non-interactive zero knowledge for NP”, LNCS, 4004, 2006, 339-358 · Zbl 1129.94025 |
| [23] | J. Groth, R. Ostrovsky, A. Sahai, “Non-interactive zaps and new techniques for NIZK”, LNCS, 4117, 2006, 97-111 · Zbl 1129.94024 |
| [24] | M. Abe, S. Fehr, “Perfect NIZK with adaptive soundness”, LNCS, 4392, 2007, 118-136 · Zbl 1129.94008 |
| [25] | G. Gentry, “Fully homomorphic encryption using ideal lattices”, Proc. 41 Ann. ACM Symp. Theory of Computing, v. 9, ACM, N.Y., 2009, 169-178 · Zbl 1304.94059 · doi:10.1145/1536414.1536440 |
| [26] | J. Groth, “Linear algebra with sub-linear zero-knowledge arguments”, LNCS, 5677, 2009, 192-208 · Zbl 1252.94068 |
| [27] | J. Groth, “Short non-interactive zero-knowledge proofs”, LNCS, 6477, 2010, 341-358 · Zbl 1253.94050 |
| [28] | H. Lipmaa, “Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes”, LNCS, 8269, 2013, 41-60 · Zbl 1300.94080 |
| [29] | P. Fauzi, H. Lipmaa, B. Zhang, “Efficient modular NIZK arguments from shift and product”, LNCS, 8257, 2013, 92-121 |
| [30] | A. E. Kosba, D. Papadopoulos, C. Papamanthou et al, TRUESET: Nearly Practical Verifiable Set Computations, Cryptology ePrint Archive. Report 2014/160, |
| [31] | H. Lipmaa, “Efficient NIZK arguments via parallel verification of benes networks”, LNCS, 8642, 2014, 416-434 · Zbl 1378.94054 |
| [32] | E. Ben-Sasson, A. Chiesa, E. Tromer, M. Virza, “Scalable zero knowledge via cycles of elliptic curves”, LNCS, 8617, 2014, 276-294 · Zbl 1334.68077 |
| [33] | C. Costello, C. Fournet, J. Howell et al, “Geppetto: Versatile verifiable computation”, Proc. IEEE Symp. SP’15, IEEE Computer Society, USA, 2015, 253-270 |
| [34] | M. Backes, M. Barbosa, D. Fiore, R. M. Reischuk, “ADSNARK: Nearly practical and privacy-preserving proofs on authenticated data”, IEEE Symp. on Security and Privacy (San Jose, CA, USA, 2015), 271-286 |
| [35] | J. Groth, M. Maller, Snarky Signatures: Minimal Signatures of Knowledge from Simulation-Extractable SNARKs, IACR Cryptology ePrint Archive, 2017, 36 pp. |
| [36] | A. Chiesa, Y. Hu, M. Maller et al, “Marlin: Preprocessing zk-SNARKs with universal and updatable SRS”, LNCS, 12105, 2020, 738-768 · Zbl 1541.94048 |
| [37] | B. Applebaum, Y. Ishai, E. Kushilevitz, “From secrecy to soundness: Efficient verification via secure computation”, LNCS, 6198, 2020, 152-163 · Zbl 1287.68041 |
| [38] | Reitwiebner C., zkSNARKs in a Nutshell, |
| [39] | N. Bitansky, R. Canetti, A. Chiesa, E. Tromer, “From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again”, Proc. ITCS’12, ACM, N.Y., 2012, 326-349 · Zbl 1347.68129 |
| [40] | S. Goldwasser, H. Lin, A. Rubinstein, Delegation of Computation without Rejection Problem from Designated Verifier CS-proofs, Cryptology ePrint Archive. Report 2011/456, 2011, 30 pp. |
| [41] | M. Ajtai, “Generating hard instances of lattice problems (extended abstract)”, Proc. STOC’96, ACM, N.Y., 1996, 99-108 · Zbl 0921.11071 |
| [42] | C. Papamanthou, E. Shi, R. Tamassia, K. Yi, “Streaming authenticated data structures”, LNCS, 7881, 2013, 353-370 · Zbl 1306.94106 |
| [43] | J. Katz, V. Kolesnikov, X. Wang, “Improved non-interactive zero knowledge with applications to post-quantum signatures”, Proc. ACM SIGSAC Conf. CCS’18, ACM, N.Y., 2018, 525-537 · doi:10.1145/3243734.3243805 |
| [44] | Bünz B., Fisch B., and Szepieniec A., Transparent SNARKs from DARK Compilers, Cryptology ePrint Archive. Paper 2019/1229, · Zbl 07436935 |
| [45] | S. Ames, C. Hazay, Y. Ishai, M. Venkitasubramaniam, “Ligero: Lightweight sublinear arguments without a trusted setup”, Proc. ACM SIGSAC Conf. CCS’17, ACM, N.Y., 2017, 2087-2104 · doi:10.1145/3133956.3134104 |
| [46] | A. Fiat, S. Shamir, “How to prove yourself: Practical solutions to identification and signature problems”, LNCS, 263, 1986, 186-194 · Zbl 0636.94012 |
| [47] | A. Aho, J. Hopcroft, J. Ulman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974, 470 pp. · Zbl 0326.68005 |
| [48] | M. Scott, “Implementing cryptographic pairings”, Proc. 1st First Intern. Conf. on Pairing Based Cryptography, Springer Verlag, Berlin-Heidelberg, 2007, 177-196 · Zbl 1148.94432 |
| [49] | S. D. Galbraith, K. Harrison, D. Soldera, “Implementing the Tate pairing”, LNCS, 2369, 2002, 324-337 · Zbl 1058.11072 |
| [50] | P. S. L. M. Barreto, B. Lynn, M. Scott, “Constructing elliptic curves with prescribed embedding degrees”, LNCS, 2576, 2003, 257-267 · Zbl 1022.94008 |
| [51] | F. Vercauteren, “Optimal pairings”, IEEE Trans. Inform. Theory, 56:1 (2020), 455-461 · Zbl 1366.94540 · doi:10.1109/TIT.2009.2034881 |
| [52] | J. L. Beuchat, J. E. González-Díaz, S. Mitsunari et al, “High-speed software implementation of the optimal ate pairing over Barreto Naehrig curves”, LNCS, 6487, 2010, 21-39 · Zbl 1287.94054 |
| [53] | M. Scott, N. Benger, M. Charlemagne et al, “On the final exponentiation for calculating pairings on ordinary elliptic curves”, LNCS, 5671, 2009, 78-88 · Zbl 1248.94093 |
| [54] | R. Granger, M. Scott, “Faster squaring in the cyclotomic subgroup of sixth degree extensions”, LNCS, 6056, 2010, 209-223 · Zbl 1279.94079 |
| [55] | Fuentes-Castañeda L., Knapp E., and Rodríguez-Henríquez F., “Faster hashing to \(\mathbb{Z}_2\)”, LNCS, 7118, 2012, 412-430 · Zbl 1292.94063 |
| [56] | T. Kim, S. Kim, J. H. Cheon, “On the final exponentiation in Tate pairing computations”, IEEE Trans. Inform. Theory, 59:6 (2013), 4033-4041 · Zbl 1364.94548 · doi:10.1109/TIT.2013.2240763 |
| [57] | J. A. Solinas, ID-based Digital Signature Algorithms, 2003, 32 pp. · Zbl 1016.94025 |
| [58] | M. Scott, “Computing the Tate pairing”, LNCS, 3376, 2005, 293-304 · Zbl 1079.94572 |
| [59] | R. Granger, N. Smart, On Computing Products of Pairings, Cryptology ePrint Archive. Report 2006/172, 2006, 11 pp. |
| [60] | Arène C., Lange T., Naehrig M., and Ritzenthaler C., “Faster computation of the Tate pairing”, J. Number Theory, 131:5 (2022), 842-857 · Zbl 1222.14069 · doi:10.1016/j.jnt.2010.05.013 |
| [61] | Frey G. and Rück H. G., “A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves”, Mathematics of Computation, 62:206 (1994), 865-874 · Zbl 0813.14045 |
| [62] | H. G. and Rück, “The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems”, IEEE Trans. Inform. Theory, 45:5 (2006), 1717-1719 · Zbl 0957.94025 |
| [63] | S. D. Galbraith, K. G. Paterson, N. P. Smart, “Pairings for cryptographers”, Discrete Appl. Math., 156:16 (2008), 3113-3121 · Zbl 1156.94347 · doi:10.1016/j.dam.2007.12.010 |
| [64] | N. Bitansky, R. Canetti, A. Chiesa, E. Tromer, Recursive Composition and Bootstrapping for Snarks and Proof-Carrying Data, IACR Cryptology ePrint Archive, · Zbl 1293.68264 |
| [65] | P. Valiant, “Incrementally verifiable computation or proofs of knowledge imply time/space efficiency”, LNCS, 4948, 2008, 1-18 · Zbl 1162.68448 |
| [66] | G. D. Crescenzo, H. Lipmaa, “Succinct NP proofs from an extractability assumption”, LNCS, 5028, 2008, 175-185 · Zbl 1142.68370 |
| [67] | T. Mei, “Polylogarithmic two-round argument systems”, J. Math. Cryptol., 2:4 (2008), 343-363 · Zbl 1158.94003 |
| [68] | A. Chiesa, D. Ojha, N. Spooner, “FRACTAL: Post-quantum and transparent recursive proofs from holography”, LNCS, 12105, 2020, 769-793 · Zbl 1539.68118 |
| [69] | A. Kattis, K. Panarin, A. Vlasov, RedShift: Transparent SNARKs from List Polynomial Commitment IOPs, Cryptology ePrint Archive. Paper 2019/1400, · Zbl 1428.74009 |
| [70] | E. Ben-Sasson, I. Bentov, Y. Horesh, M. Riabzev, “Fast Reed Solomon interactive oracle proofs of proximity” (Prague, Czech Republic, 2018), 45th Intern. Colloquium ICALP’2018, LIPIcs, 107, 1-17 · Zbl 1499.68141 · doi:10.4230/LIPIcs.ICALP.2018.14 |
| [71] | S. Setty, “Spartan: Efficient and general-purpose zkSNARKs without trusted setup”, LNCS, 12172, 2020, 704-737 · Zbl 1504.94185 |
| [72] | S. Bowe, J. Grigg, D. Hopwood, Recursive Proof Composition without a Trusted Setup, Cryptology ePrint Archive. Paper 2019/1021, |
| [73] | D. Boneh, J. Drake, B. Fisch, A. Gabizon, Halo Infinite: Recursive zk-SNARKs from any Additive Polynomial Commitment Scheme, Cryptology ePrint Archive. Paper 2020/1536, |
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.
