Geodesic
Ways to improve the performance of zero-knowledge succinct non-interactivearguments of knowledge and~the analysis of the rusults achieved
Prikladnaâ diskretnaâ matematika, no. 2 (2023), pp. 40-58.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 parameters. 
@article{PDM_2023_2_a3,
     author = {I. V. Martynenkov},
     title = {Ways to improve the performance of zero-knowledge succinct non-interactivearguments of knowledge and~the analysis of the rusults achieved},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {40--58},
     publisher = {mathdoc},
     number = {2},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2023_2_a3/}
}
TY  - JOUR
AU  - I. V. Martynenkov
TI  - Ways to improve the performance of zero-knowledge succinct non-interactivearguments of knowledge and~the analysis of the rusults achieved
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2023
SP  - 40
EP  - 58
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2023_2_a3/
LA  - ru
ID  - PDM_2023_2_a3
ER  - 
%0 Journal Article
%A I. V. Martynenkov
%T Ways to improve the performance of zero-knowledge succinct non-interactivearguments of knowledge and~the analysis of the rusults achieved
%J Prikladnaâ diskretnaâ matematika
%D 2023
%P 40-58
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2023_2_a3/
%G ru
%F PDM_2023_2_a3
I. V. Martynenkov. Ways to improve the performance of zero-knowledge succinct non-interactivearguments of knowledge and~the analysis of the rusults achieved. Prikladnaâ diskretnaâ matematika, no. 2 (2023), pp. 40-58. http://geodesic.mathdoc.fr/item/PDM_2023_2_a3/

[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)

[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, , 2019 https://eprint.iacr.org/2019/458

[3] J. Baylina, M. Bellés, 4-bit Window Pedersen Hash On The Baby Jubjub Elliptic Curve, 2019, 8 pp. https://docs.iden3.io/publications/pdfs/Pedersen-Hash.pdf

[4] O. Regev, “New lattice based cryptographic constructions”, Proc. 35th Ann. ACM Symp. on Theory of Computing, ACM, N.Y., 2003, 407–416 | DOI | MR | Zbl

[5] O. Regev, “New lattice-based cryptographic constructions”, J. ACM, 51:6 (2004), 899–942 | DOI | MR | Zbl

[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 | MR | Zbl

[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

[9] H. Lipmaa, “Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments”, LNCS, 7194, 2012, 169–189 | MR | Zbl

[10] N. Pippenger, “On the evaluation of powers and related problems”, 17th Ann. Symp. SFCS'1976 (Houston, TX, USA, 1976), 258–263 | MR

[11] J. Bos, M. Coster, “Addition chain heuristics”, LNCS, 435, 1990, 400–407 | MR

[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 | MR | Zbl

[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, , 2019, 37 pp. https://eprint.iacr.org/2013/879.pdf

[15] R. Gennaro, C. Gentry, B. Parno, M. Raykova, “Quadratic span programs and succinct NIZKs without PCPs”, LNCS, 7881, 2013, 626–645 | MR | Zbl

[16] Costello C., Pairings for Beginners, , 2012, 146 pp. https://www.craigcostello.com.au/pairings/PairingsForBeginners.pdf

[17] J. Groth, “On the size of pairing-based non-interactive arguments”, LNCS, 9666, 2016, 305–326 | MR | Zbl

[18] G. Danezis, C. Fournet, J. Groth, M. Kohlweiss, “Square span programs with applications to succinct NIZK arguments”, LNCS, 8873, 2014, 532–550 | MR | Zbl

[19] H. Lipmaa, Almost Optimal Short Adaptive Non-Interactive Zero Knowledge, Tech. Rep. 2014/396, International Association for Cryptologic Research, 2014, 20 pp. http://eprint.iacr.org/2014/396 | Zbl

[20] R. Gennaro, C. Gentry, B. Parno, “Non-interactive verifiable computing: Outsourcing computation to untrusted workers”, LNCS, 6223, 2010, 465–482 | MR | Zbl

[21] Lee J. Dory, “Efficient, transparent arguments for generalised inner products and polynomial commitments”, LNCS, 13043, 2021, 1–34 | MR | Zbl

[22] J. Groth, R. Ostrovsky, A. Sahai, “Perfect non-interactive zero knowledge for NP”, LNCS, 4004, 2006, 339–358 | MR | Zbl

[23] J. Groth, R. Ostrovsky, A. Sahai, “Non-interactive zaps and new techniques for NIZK”, LNCS, 4117, 2006, 97–111 | MR | Zbl

[24] M. Abe, S. Fehr, “Perfect NIZK with adaptive soundness”, LNCS, 4392, 2007, 118–136 | MR | Zbl

[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 | DOI | MR | Zbl

[26] J. Groth, “Linear algebra with sub-linear zero-knowledge arguments”, LNCS, 5677, 2009, 192–208 | MR | Zbl

[27] J. Groth, “Short non-interactive zero-knowledge proofs”, LNCS, 6477, 2010, 341–358 | Zbl

[28] H. Lipmaa, “Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes”, LNCS, 8269, 2013, 41–60 | Zbl

[29] P. Fauzi, H. Lipmaa, B. Zhang, “Efficient modular NIZK arguments from shift and product”, LNCS, 8257, 2013, 92–121 | MR

[30] A. E. Kosba, D. Papadopoulos, C. Papamanthou et al, TRUESET: Nearly Practical Verifiable Set Computations, Cryptology ePrint Archive. Report 2014/160, , 2014, 30 pp. http://eprint.iacr.org/2014/160

[31] H. Lipmaa, “Efficient NIZK arguments via parallel verification of benes networks”, LNCS, 8642, 2014, 416–434 | MR | Zbl

[32] E. Ben-Sasson, A. Chiesa, E. Tromer, M. Virza, “Scalable zero knowledge via cycles of elliptic curves”, LNCS, 8617, 2014, 276–294 | MR | Zbl

[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. | MR

[36] A. Chiesa, Y. Hu, M. Maller et al, “Marlin: Preprocessing zk-SNARKs with universal and updatable SRS”, LNCS, 12105, 2020, 738–768 | MR

[37] B. Applebaum, Y. Ishai, E. Kushilevitz, “From secrecy to soundness: Efficient verification via secure computation”, LNCS, 6198, 2020, 152–163

[38] Reitwiebner C., zkSNARKs in a Nutshell, , 2017, 15 pp. https://blog.ethereum.org/2016/12/05/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 | MR | Zbl

[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 | MR | Zbl

[42] C. Papamanthou, E. Shi, R. Tamassia, K. Yi, “Streaming authenticated data structures”, LNCS, 7881, 2013, 353–370 | MR | Zbl

[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

[44] Bünz B., Fisch B., and Szepieniec A., Transparent SNARKs from DARK Compilers, Cryptology ePrint Archive. Paper 2019/1229, , 2019, 59 pp. https://eprint.iacr.org/2019/1229 | MR

[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

[46] A. Fiat, S. Shamir, “How to prove yourself: Practical solutions to identification and signature problems”, LNCS, 263, 1986, 186–194 | MR

[47] A. Aho, J. Hopcroft, J. Ulman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974, 470 pp. | MR | Zbl

[48] M. Scott, “Implementing cryptographic pairings”, Proc. 1st First Intern. Conf. on Pairing Based Cryptography, Springer Verlag, Berlin–Heidelberg, 2007, 177–196 | MR | Zbl

[49] S. D. Galbraith, K. Harrison, D. Soldera, “Implementing the Tate pairing”, LNCS, 2369, 2002, 324–337 | MR | Zbl

[50] P. S. L. M. Barreto, B. Lynn, M. Scott, “Constructing elliptic curves with prescribed embedding degrees”, LNCS, 2576, 2003, 257–267 | Zbl

[51] F. Vercauteren, “Optimal pairings”, IEEE Trans. Inform. Theory, 56:1 (2020), 455–461 | DOI | MR

[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 | MR | Zbl

[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 | MR | Zbl

[54] R. Granger, M. Scott, “Faster squaring in the cyclotomic subgroup of sixth degree extensions”, LNCS, 6056, 2010, 209–223 | MR | Zbl

[55] Fuentes-Castañeda L., Knapp E., and Rodríguez-Henríquez F., “Faster hashing to $\mathbb{Z}_2$”, LNCS, 7118, 2012, 412–430 | MR | Zbl

[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 | DOI | MR | Zbl

[57] J. A. Solinas, ID-based Digital Signature Algorithms, 2003, 32 pp. http://cacr.uwaterloo.ca/conferences/2003/ecc2003/solinas.pdf | Zbl

[58] M. Scott, “Computing the Tate pairing”, LNCS, 3376, 2005, 293–304 | MR | Zbl

[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 | DOI | MR

[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 | MR | Zbl

[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 | MR

[63] S. D. Galbraith, K. G. Paterson, N. P. Smart, “Pairings for cryptographers”, Discrete Appl. Math., 156:16 (2008), 3113–3121 | DOI | MR | Zbl

[64] N. Bitansky, R. Canetti, A. Chiesa, E. Tromer, Recursive Composition and Bootstrapping for Snarks and Proof-Carrying Data, IACR Cryptology ePrint Archive, , 2012, 61 pp. http://eprint.iacr.org/2012/095 | MR

[65] P. Valiant, “Incrementally verifiable computation or proofs of knowledge imply time/space efficiency”, LNCS, 4948, 2008, 1–18 | MR | Zbl

[66] G. D. Crescenzo, H. Lipmaa, “Succinct NP proofs from an extractability assumption”, LNCS, 5028, 2008, 175–185 | MR | Zbl

[67] T. Mei, “Polylogarithmic two-round argument systems”, J. Math. Cryptol., 2:4 (2008), 343–363 | MR

[68] A. Chiesa, D. Ojha, N. Spooner, “FRACTAL: Post-quantum and transparent recursive proofs from holography”, LNCS, 12105, 2020, 769–793 | MR

[69] A. Kattis, K. Panarin, A. Vlasov, RedShift: Transparent SNARKs from List Polynomial Commitment IOPs, Cryptology ePrint Archive. Paper 2019/1400, , 2019, 20 pp. https://eprint.iacr.org/2019/1400 | Zbl

[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 | DOI | MR

[71] S. Setty, “Spartan: Efficient and general-purpose zkSNARKs without trusted setup”, LNCS, 12172, 2020, 704–737 | MR | Zbl

[72] S. Bowe, J. Grigg, D. Hopwood, Recursive Proof Composition without a Trusted Setup, Cryptology ePrint Archive. Paper 2019/1021, , 2019, 31 pp. https://eprint.iacr.org/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, , 2020, 66 pp. https://eprint.iacr.org/2020/1536