Рассматриваются способы повышения производительности кратких неинтерактивных аргументов с нулевым разглашением на основе полиномиальных наборов с использованием различных вычислительных методов. Проводится сравнительный анализ протоколов по размерам главных ссылочных строк и доказательств достоверности вычислений, затратам формирования доказательств и их верификации.
Скачать электронную версию публикации
Загружен, раз: 5
- Title Способы повышения производительности кратких неинтерактивных аргументов с нулевым разглашением и анализ достигнутых результатов
- Headline Способы повышения производительности кратких неинтерактивных аргументов с нулевым разглашением и анализ достигнутых результатов
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 60
- Date:
- DOI 10.17223/20710410/60/4
Ключевые слова
краткие неинтерактивные аргументы, повышение производительности, анализ производительности, размер публичных параметровАвторы
Ссылки
Мартыненков И. В. Краткие неинтерактивные аргументы с нулевым разглашением на основе наборов полиномов // Прикладная дискретная математика. 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.
Способы повышения производительности кратких неинтерактивных аргументов с нулевым разглашением и анализ достигнутых результатов | Прикладная дискретная математика. 2023. № 60. DOI: 10.17223/20710410/60/4
Скачать полнотекстовую версию
Загружен, раз: 124
- ВКонтакте
- РћРТвЂВВВВВВВВнокласснРСвЂВВВВВВВВРєРСвЂВВВВВВВВ
- Telegram