We consider ways to improve the performance of zero-knowledge succinct noninteractive 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.
Download file
Counter downloads: 8
- Title Ways to improve the performance of zero-knowledge succinct non-interactivearguments of knowledge and the analysis of the rusults achieved
- Headline Ways to improve the performance of zero-knowledge succinct non-interactivearguments of knowledge and the analysis of the rusults achieved
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 60
- Date:
- DOI 10.17223/20710410/60/4
Keywords
succinct non-interactive arguments, performance improvement, performance analysis, size of public parametersAuthors
References
Мартыненков И. В. Краткие неинтерактивные аргументы с нулевым разглашением на основе наборов полиномов // Прикладная дискретная математика. 2023. №59. С. 20-57.
Grassi L., Khovratovich D., Rechberger C., 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.
Baylina J. and Belles M. 4-bit Window Pedersen Hash On The Baby Jubjub Elliptic Curve. 2019. https://docs.iden3.io/publications/pdfs/Pedersen-Hash.pdf. 8p.
Regev O. New lattice based cryptographic constructions // Proc. 35th Ann. ACM Symp. on Theory of Computing. N.Y.: ACM, 2003. P.407-416.
Regev O. New lattice-based cryptographic constructions //j. ACM. 2004. V. 51. Iss.6. P. 899-942.
Regev O. On lattices, learning with errors, random linear codes, and cryptography // Proc. 37th Ann. ACM Symp. on Theory of Computing. N.Y.: ACM, 2005. P.84-93.
Zhang Y., Papamanthou C., and Katz J. ALITHEIA: Towards practical verifiable graph processing // Proc. CCS'14. N.Y.: ACM, 2014. P.856-867.
Groth J. Short pairing-based non-interactive zero-knowledge arguments // LNCS. 2010. V. 6477. P.321-340.
Lipmaa H. Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments // LNCS. 2012. V. 7194. P.169-189.
Pippenger N. On the evaluation of powers and related problems // 17th Ann. Symp. SFCS'1976. Houston, TX, USA, 1976. P.258-263.
Bos J. and Coster M. Addition chain heuristics // LNCS. 1990. V. 435. P.400-407.
Ben-Sasson E., Chiesa A., Genkin D., et al. SNARKs for C: Verifying program executions succinctly and in zero knowledge // LNCS. 2013. V. 8043. P. 90-108.
Parno B., Howell J., Gentry C., and Raykova M. Pinocchio: Nearly practical verifiable computation // Proc. 34th IEEE Symp. on Security and Privacy. Berkeley, CA, USA, 2013. P.238-252.
Ben-Sasson E., Chiesa A., Tromer E., and Virza M. Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture. Updated version, 2019. https://eprint.iacr.org/2013/879.pdf. 37p.
Gennaro R., Gentry C., Parno B., and Raykova M. Quadratic span programs and succinct NIZKs without PCPs // LNCS. 2013. V.7881. P.626-645.
Costello C. Pairings for Beginners. https://www.craigcostello.com.au/pairings/PairingsForBeginners.pdf. 2012. 146p.
Groth J. On the size of pairing-based non-interactive arguments // LNCS. 2016. V. 9666. P. 305-326.
Danezis G., Fournet C., Groth J., and Kohlweiss M. Square span programs with applications to succinct NIZK arguments // LNCS. 2014. V. 8873. P.532-550.
Lipmaa H. Almost Optimal Short Adaptive Non-Interactive Zero Knowledge. Tech. Rep. 2014/396.International Association for Cryptologic Research, 2014. http://eprint.iacr.org/2014/396. 20 p.
Gennaro R., Gentry C., and Parno B. Non-interactive verifiable computing: Outsourcing computation to untrusted workers // LNCS. 2010. V. 6223. P. 465-482.
Lee J. Dory: Efficient, transparent arguments for generalised inner products and polynomial commitments // LNCS. 2021. V. 13043. P. 1-34.
Groth J., Ostrovsky R., and Sahai A. Perfect non-interactive zero knowledge for NP // LNCS. 2006. V. 4004. P. 339-358.
Groth J., Ostrovsky R., and Sahai A. Non-interactive zaps and new techniques for NIZK // LNCS. 2006. V. 4117. P.97-111.
Abe M. and Fehr S. Perfect NIZK with adaptive soundness // LNCS. 2007. V. 4392. P.118-136.
Gentry G. Fully homomorphic encryption using ideal lattices // Proc. 41 Ann. ACM Symp. Theory of Computing. V. 9. N.Y.: ACM, 2009. P. 169-178.
Groth J. Linear algebra with sub-linear zero-knowledge arguments // LNCS. 2009. V. 5677. P. 192-208.
Groth J. Short non-interactive zero-knowledge proofs // LNCS. 2010. V.6477. P.341-358.
Lipmaa H. Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes // LNCS. 2013. V. 8269. P.41-60.
Fauzi P., Lipmaa H., and Zhang B. Efficient modular NIZK arguments from shift and product // LNCS. 2013. V. 8257. P.92-121.
Kosba A.E., Papadopoulos D., Papamanthou C., et al. TRUESET: Nearly Practical Verifiable Set Computations. Cryptology ePrint Archive. Report 2014/160. 2014. http://eprint.iacr.org/2014/160. 30 p.
Lipmaa H. Efficient NIZK arguments via parallel verification of benes networks // LNCS. 2014. V. 8642. P.416-434.
Ben-Sasson E., Chiesa A., Tromer E., and Virza M. Scalable zero knowledge via cycles of elliptic curves // LNCS. 2014. V. 8617. P.276-294.
Costello C., Fournet C., Howell J., et al. Geppetto: Versatile verifiable computation // Proc. IEEE Symp. SP'15. IEEE Computer Society, USA, 2015. P.253-270.
Backes M., Barbosa M., Fiore D., and Reischuk R. M. ADSNARK: Nearly practical and privacy-preserving proofs on authenticated data // IEEE Symp. on Security and Privacy, San Jose, CA, USA, 2015. P.271-286.
Groth J. and Maller M. Snarky Signatures: Minimal Signatures of Knowledge from Simulation-Extractable SNARKs. IACR Cryptology ePrint Archive. 2017. 36 p.
Chiesa A., Hu Y., Maller M., et al. Marlin: Preprocessing zk-SNARKs with universal and updatable SRS // LNCS. 2020. V. 12105. P. 738-768.
Applebaum B., Ishai Y., and Kushilevitz E. From secrecy to soundness: Efficient verification via secure computation // LNCS. 2020. V. 6198. P. 152-163.
Reitwiebner C. zkSNARKs in a Nutshell. 2017. https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/. 15 p.
Bitansky N., Canetti R., Chiesa A., and Tromer E. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again // Proc. ITCS'12. N.Y.: ACM, 2012. P.326-349.
Goldwasser S., Lin H., and Rubinstein A. Delegation of Computation without Rejection Problem from Designated Verifier CS-proofs. Cryptology ePrint Archive. Report 2011/456. 2011. 30p.
Ajtai M. Generating hard instances of lattice problems (extended abstract) // Proc. STOC'96. N.Y.: ACM, 1996. P.99-108.
Papamanthou C., Shi E., Tamassia R., and Yi K. Streaming authenticated data structures // LNCS. 2013. V. 7881. P.353-370.
Katz J., Kolesnikov V., and Wang X. Improved non-interactive zero knowledge with applications to post-quantum signatures // Proc. ACM SIGSAC Conf. CCS'18. N.Y.: ACM, 2018. P. 525-537.
Bunz B., Fisch B., and Szepieniec A. Transparent SNARKs from DARK Compilers. Cryptology ePrint Archive. Paper 2019/1229. 2019. https://eprint.iacr.org/2019/1229. 59 p.
Ames S., Hazay C., Ishai Y., and Venkitasubramaniam M. Ligero: Lightweight sublinear arguments without a trusted setup // Proc. ACM SIGSAC Conf. CCS'17. N.Y.: ACM, 2017. P.2087-2104.
Fiat A. and Shamir S. How to prove yourself: Practical solutions to identification and signature problems // LNCS. 1986. V. 263. P.186-194.
Aho A., Hopcroft J., and Ulman J. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. 470 p.
Scott M. Implementing cryptographic pairings // Proc. 1st First Intern. Conf. on Pairing-Based Cryptography. Berlin; Heidelberg: Springer Verlag, 2007. P. 177-196.
Galbraith S. D., Harrison K., and Soldera D. Implementing the Tate pairing // LNCS. 2002. V. 2369. P. 324-337.
Barreto P. S. L. M., Lynn B., and Scott M. Constructing elliptic curves with prescribed embedding degrees // LNCS. 2003. V.2576. P.257-267.
Vercauteren F. Optimal pairings // IEEE Trans. Inform. Theory. 2020. V. 56. No. 1. P.455-461.
Beuchat J. L., Gonzalez-Diaz J. E., Mitsunari S., et al. High-speed software implementation of the optimal ate pairing over Barreto - Naehrig curves // LNCS. 2010. V. 6487. P. 21-39.
Scott M., Benger N., Charlemagne M., et al. On the final exponentiation for calculating pairings on ordinary elliptic curves // LNCS. 2009. V. 5671. P. 78-88.
Granger R. and Scott M. Faster squaring in the cyclotomic subgroup of sixth degree extensions // LNCS. 2010. V.6056. P.209-223.
Fuentes-Castaneda L., Knapp E., and Rodriguez-Henriquez F. Faster hashing to G2 // LNCS. 2012. V. 7118. P.412-430.
Kim T., Kim S., and Cheon J. H. On the final exponentiation in Tate pairing computations // IEEE Trans. Inform. Theory. 2013. V. 59. No. 6. P.4033-4041.
Solinas J. A. ID-based Digital Signature Algorithms. 2003. http://cacr.uwaterloo.ca/conferences/2003/ecc2003/solinas.pdf. 32 p.
Scott M.Computing the Tate pairing // LNCS. 2005. V. 3376. P. 293-304.
Granger R. and Smart N. On Computing Products of Pairings. Cryptology ePrint Archive. Report 2006/172. 2006. 11 p.
Arene C, Lange T., Naehrig M., and Ritzenthaler C. Faster computation of the Tate pairing //j. Number Theory. 2022. V. 131. No. 5. P. 842-857.
Frey G. and Ruck H.-G. A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves // Mathematics of Computation. 1994. V. 62. No. 206. P. 865-874.
Frey G., Muller M., and Ruck H.-G. The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems // IEEE Trans. Inform. Theory. 2006. V. 45. No. 5. P. 1717-1719.
Galbraith S. D., Paterson K. G., and Smart N.P. Pairings for cryptographers // Discrete Appl. Math. 2008. V. 156. No. 16. P.3113-3121.
Bitansky N., Canetti R., Chiesa A., and Tromer E. Recursive Composition and Bootstrapping for Snarks and Proof-Carrying Data. IACR Cryptology ePrint Archive. 2012. http://eprint.iacr.org/2012/095. 61 p.
Valiant P. Incrementally verifiable computation or proofs of knowledge imply time/space efficiency // LNCS. 2008. V.4948. P. 1-18.
Crescenzo G. D. and Lipmaa H. Succinct NP proofs from an extractability assumption // LNCS. 2008. V. 5028. P.175-185.
Mei T. Polylogarithmic two-round argument systems //j. Math. Cryptol. 2008. V. 2. No. 4. P. 343-363.
Chiesa A., Ojha D., and Spooner N. FRACTAL: Post-quantum and transparent recursive proofs from holography // LNCS. 2020. V. 12105. P. 769-793.
Kattis A, Panarin K., and Vlasov A. RedShift: Transparent SNARKs from List Polynomial Commitment IOPs. Cryptology ePrint Archive. Paper 2019/1400. 2019. https://eprint. iacr.org/2019/1400. 20p.
Ben-Sasson E., Bentov I., Horesh Y., and Riabzev M. Fast Reed - Solomon interactive oracle proofs of proximity // 45th Intern. Colloquium ICALP'2018. V. 107. Prague, Czech Republic, 2018. P. 1-17.
Setty S. Spartan: Efficient and general-purpose zkSNARKs without trusted setup // LNCS. 2020. V. 12172. P. 704-737.
Bowe S., Grigg J., and Hopwood D. Recursive Proof Composition without a Trusted Setup. Cryptology ePrint Archive. Paper 2019/1021. 2019. https://eprint.iacr.org/2019/1021. 31 p.
Boneh D., Drake J., Fisch B., and Gabizon A. Halo Infinite: Recursive zk-SNARKs from any Additive Polynomial Commitment Scheme. Cryptology ePrint Archive. Paper 2020/1536. 2020. https://eprint.iacr.org/2020/1536. 66 p.
Ways to improve the performance of zero-knowledge succinct non-interactivearguments of knowledge and the analysis of the rusults achieved | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2023. № 60. DOI: 10.17223/20710410/60/4
Download full-text version
Counter downloads: 128