ГлавнаяАрхивСовременные парадигмы построения схем цифровой подписи на решётках

Современные парадигмы построения схем цифровой подписи на решётках | Прикладная дискретная математика. 2025. № 67. DOI: 10.17223/20710410/67/2

Ввиду возникновения угрозы нарушения стойкости криптографических алгоритмов с помощью квантового вычислителя большую популярность обрело направление постквантовой криптографии - нового раздела, включающего алгоритмы и протоколы, эффективно противостоящие атакам с помощью квантового компьютера. Теория решёток на сегодняшний день является перспективным направлением постквантовой криптографии. Одними из первых криптосистем на решетках были GGH и NTRU. В их основе лежит задача о поиске ближайшего вектора решётки, а отличие схем заключается в построении решёток. На основе криптосистем GGH и NTRU была предложена схема цифровой подписи NTRUSign, взявшая лучшее у них. Другой подход к построению подписи появился в 2008 г., в его основе лежит парадигма Hash-and-Sign, а подпись для сообщения вырабатывается с помощью лазейки. Годом позже В. Любашевским был предложен ещё один подход к построению подписи на решетках. Он заключается в использовании преобразования Фиата - Шамира, однако в силу специфики решёток алгоритм формирования подписи выдаёт корректную подпись с некоторой вероятностью, поскольку в целях безопасности используется выборка отбраковки. В данной работе представлен обзор существующих парадигм построения схем цифровых подписей на решётках, а также криптографических схем, построенных на рассматриваемых парадигмах. Проведён сравнительный анализ схем, определены преимущества и недостатки каждого из подходов, определены наилучшие условия их применения.
  • Title Современные парадигмы построения схем цифровой подписи на решётках
  • Headline Современные парадигмы построения схем цифровой подписи на решётках
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 67
  • Date:
  • DOI 10.17223/20710410/67/2
Ключевые слова
цифровая подпись на базе решёток, теория решёток, постквантовая криптография
Авторы
Ссылки
Schmieg S., Kolbl S., and Endignoux G. Google's Threat Model for Post-Quantum Cryptography. https://bughunters.google.com/blog/5108747984306176/google-s-threat-model-for-post-quantum-cryptography. 2024.
Westerbaan B. NIST's Pleasant Post-Quantum Surprise. https://blog.cloudflare.com/nist-post-quantum-surprise/. 2022.
Lyubashevsky V. CRYSTALS-Dilithium Round 3 Presentation. https://csrc.nist.gov/presentations/2021/crystals-dilithium-round-3-presentation. 2021.
Vidakovic M. and Milicevic K. Performance and applicability of post-quantum digital signature algorithms in resource-constrained environments // Algorithms. 2023. V. 16. No. 11:518.
Howe J. and Westerbaan B. Benchmarking and analysing the NIST PQC lattice-based signature schemes standards on the ARM Cortex M7 // LNCS. 2023. V. 14064. P. 442-462.
Schnorr C. P. Lattice reduction by random sampling and birthday methods // LNCS. V. 2607. P. 145-156.
Chen Y. Reduction de reseau et securite concrete du chiffrement completement homomorphe. These de doctorat. Paris, 2013. (in French).
Becker A., Ducas L., Gama N., and Laarhoven T. New directions in nearest neighbor searching with applications to lattice sieving // Proc. SODA'16. Arlington, Virginia, 2016. P. 10-24.
Laarhoven T., Mosca M., and Van De Pol J. Finding shortest lattice vectors faster using quantum search // Des. Codes Cryptography. 2015. V. 77. P.375-400.
Schnorr C.P. and Euchner M. Lattice basis reduction: Improved practical algorithms and solving subset sum problems // Math. Programming. 1994. V. 66. P. 181-199.
Alkim E., Ducas L., Poppelmann T., and Schwabe P. Post-quantum key exchange: A new hope // Proc. SEC'16. Austin, TX, USA, 2016. P.327-343.
Liu Q. and Zhandry M. Revisiting post-quantum Fiat - Shamir // LNCS. 2019. V. 11693. P. 326-355.
Devevey J., Fallahpour P., Passelegue A., and Stehle D. A detailed analysis of Fiat - Shamir with aborts // LNCS. 2023. V. 14085. P.327-357.
Don J., Fehr S., Majenz C., and Schaffner C. Security of the Fiat - Shamir transformation in the quantum random-oracle model // LNCS. 2019. V. 11693. P.356-383.
Kiltz E., Lyubashevsky V., and Schaffner C. A concrete treatment of Fiat - Shamir signatures in the quantum random-oracle model // LNCS. 2018. V. 10822. P. 552-586.
Bai S. and Galbraith S. D. An improved compression technique for signatures based on learning with errors // LNCS. 2014. V. 8366. P.28-47.
Brakerski Z., Gentry C., and Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping // Proc. ITCS'12. Cambridge, Massachusetts, 2012. P.309-325.
Devevey J., Fawzi O., PasseJegue A., and Stehle D. On rejection sampling in Lyubashevsky's signature scheme // LNCS. 2022. V. 13794. P. 34-64.
Pessl P., Bruinderink L. G., and Yarom Y. To BLISS-B or not to be: Attacking strong Swan's implementation of post-quantum signatures // Proc. CCS'17. Dallas, Texas, USA, 2017. P. 1843-1855.
Espitau T., Fouque P. A., Gerard B., and Tibouchi M. Side-channel attacks on BLISS lattice-based signatures: Exploiting branch tracing against strongswan and electromagnetic emanations in microcontrollers // Proc. CCS'17. Dallas, Texas, USA, 2017. P.1857-1874.
Groot Bruinderink L., Hulsing A., Lange T., and Yarom Y. Flush, Gauss, and reload - a cache attack on the BLISS lattice-based signature scheme // LNCS. 2016. V. 9813. P. 323-345.
Ducas L., Durmus A., Lepoint T., and Lyubashevsky V. Lattice signatures and bimodal gaussians // LNCS. 2013. V. 8042. P.40-56.
Bellare M. and Neven G. Multi-signatures in the plain public-key model and a general forking lemma // Proc. CCS'06. Alexandria, Virginia, USA, 2006. P.390-399.
Devroye L. General principles in random variate generation // Non-Uniform Random Variate Generation. N.Y.: Springer, 1986. P.27-82.
Cheon J. H., Choe H., Devevey J., et al. HAETAE: Shorter Lattice-Based Fiat - Shamir Signatures. Cryptology ePrint Archive. Paper 2023/624. https://eprint.iacr.org/2023/624.
Alagic G., Apon D., Cooper D., et al. Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process. NIST Interagency/Internal Report (NISTIR). 2022. Report 8413. https://csrc.nist.gov/pubs/ir/8413/upd1/final.
Ducas L., Kiltz E., Lepoint T., et al. CRYSTALS-Dilithium: A lattice-based digital signature scheme // lACR Trans. Cryptographic Hardware and Embedded Systems. 2018. No. 1. P. 238-268.
Lyubashevsky V. Fiat - Shamir with aborts: Applications to lattice and factoring-based signatures // LNCS. 2009. V. 5912. P.598-616.
Schnorr C. P. Efficient signature generation by smart cards // J. Cryptology. 1991. V. 4. No. 3. P. 161-174.
Abdalla M., An J. H., Bellare M., and Namprempre C. From identification to signatures via the Fiat - Shamir transform: Minimizing assumptions for security and forward-security // LNCS. 2002. V.2332. P.418-433.
Fiat A. and Shamir A. How to prove yourself: Practical solutions to identification and signature problems // LNCS. 1987. V. 263. P.186-194.
Micciancio D. and Walter M. Practical, predictable lattice basis reduction // LNCS. 2016. V.9665. P.820-849.
Klein P. N. Finding the closest lattice vector when it's unusually close // Proc. SODA'00. San Francisco, California, USA, 2000. P.937-941.
Ducas L. and Prest T. Fast Fourier orthogonalization // Proc. ISSAC'16. Waterloo, ON, Canada, 2016. P. 191-198.
Fouque P.-A., Hoffstein J., Kirchner P., et al. Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU. Specification v1.2. https://falcon-sign.info/falcon.pdf. 2020. Современные парадигмы построения схем цифровой подписи на решётках.
Peikert C. and Rosen A. Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices // LNCS. 2006. V. 3876. P. 145-166.
Alwen J. and Peikert C. Generating shorter bases for hard random lattices // Theory Comput. Syst. 2011. No. 48(3). P. 535-553.
Micciancio D. and Peikert C. Trapdoors for lattices: Simpler, tighter, faster, smaller // LNCS. 2012. V. 7237. P. 700-718.
Bellare M. and Rogaway P. Random oracles are practical: A paradigm for designing efficient protocols // Proc. CCS'93. Fairfax, Virginia, USA, 1993. P.62-73.
Diffie W. and Hellman M. E. New directions in cryptography // IEEE Trans. Inform. Theory. 1976. No. 22(6). P. 644-654.
Boneh D., Dagdelen O., Fischlin M., et al. Random oracles in a quantum world // LNCS. 2011. V.7073. P.41-69.
May A. and Silverman J. H. Dimension reduction methods for convolution modular lattices // LNCS. 2001. V.2146. P.110-125.
Stehle D. and Steinfeld R. Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices. Cryptology ePrint Archive. Paper 2013/004. https: //eprint.iacr.org/2013/004.
Howgrave-Graham N. A hybrid lattice-reduction and meet-in-the-middle attack against NTRU // LNCS. 2007. V.4622. P.150-169.
Gama N. and Nguyen P. Q. Predicting lattice reduction // LNCS. 2008. V. 4965. P. 31-51.
Lyubashevsky V. Lattice signatures without trapdoors // LNCS. 2012. V. 7237. P.738-755.
Stehle D. and Steinfeld R. Making NTRU as secure as worst-case problems over ideal lattices // LNCS. 2011. V.6632. P.27-47.
Gentry C., Peikert C., and Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions // Proc. STOC'08. Victoria, British Columbia, Canada, 2008. P. 197-206.
Hoffstein J., Howgrave-Graham N., Pipher J., et al. Performance Improvements and a Baseline Parameter Generation Algorithm for NTRUSign. Cryptology ePrint Archive. Paper 2005/274. https://eprint.iacr.org/2005/274.
Hoffstein J., Howgrave-Graham N., Pipher J., et al. NTRUSIGN: Digital signatures using the NTRU lattice // LNCS. 2003. V.2612. P. 122-140.
Ducas L. and Nguyen P. Q. Learning a zonotope and more: Cryptanalysis of NTRUSign countermeasures // LNCS. 2012. V. 7658. P.433-450.
Melchor C. A., Boyen X., Deneuville J.-C., and Gaborit P. Sealing the leak on classical NTRU signatures // LNCS. 2014. V. 8772. P. 1-21.
Nguyen P. Q. and Regev O. Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures // J. Cryptology. 2009. No. 22(2). P.139-160.
Gentry C. and Szydlo M. Cryptanalysis of the revised NTRU signature scheme // LNCS. 2002. V.2332. P.299-320.
Gentry C., Jonsson J., Stern J., and Szydlo M. Cryptanalysis of the NTRU Signature Scheme (NSS) from Eurocrypt 2001 // LNCS. 2001. V. 2248. P. 1-20.
Hoffstein J., Pipher J., and Silverman J. H. NSS: An NTRU lattice-based signature scheme // LNCS. 2001. V.2045. P.211-228.
Hoffstein J., Howgrave-Graham N., Pipher J., et al. NTRUSign: Digital signatures using the NTRU lattice // LNCS. 2003. V.2612. P. 122-140.
Hoffstein J., Pipher J., and Silverman J. H. NTRU: A ring-based public key cryptosystem // LNCS. 1998. V. 1423. P.267-288.
Langlois A. and Stehle D. Worst-case to average-case reductions for module lattices // Des. Codes Cryptography. 2015. V. 75. P. 565-599.
Goldreich O., Goldwasser S., and Halevi S. Public-key cryptosystems from lattice reduction problems // LNCS. 1997. V. 1294. P.112-131.
Lyubashevsky V., Peikert C., and Regev O. On ideal lattices and learning with errors over rings // J. ACM. 2010. V.60. P. 43:1-43:35.
Lyubashevsky V. Fiat - Shamir with aborts: Applications to lattice and factoring-based signatures // LNCS. 2009. V. 5912. P.598-616.
Lyubashevsky V. and Micciancio D. Generalized compact knapsacks are collision resistant // LNCS. 2006. V.4052. P. 144-155.
Peikert C. and Rosen A. Lattices that admit logarithmic worst-case to average-case connection factors // Proc. STOC'07. San Diego, California, USA. 2007. P.478-487.
Micciancio D. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions // Comput.Complexity. 2007. No. 16(4). P.365-411.
Regev O. On lattices, learning with errors, random linear codes, and cryptography // Proc. STOC'05. Baltimore, MD, USA. 2005. P.84-93.
Ajtai M. Generating hard instances of lattice problems // Proc. STOC'96. Philadelphia, Pennsylvania, USA, 1996. P.99-108.
Roy S.S., Vercauteren F., Mentens N., et al.Compact ring-LWE cryptoprocessor // LNCS. 2014. V.8731. P.371-391.
Dinur I., Kindler G., and Safra S. Approximating CVP to within almost-polynomial factors is NP-hard // Combinatorica. 2003. V. 23. P.205-243.
Ajtai M., Kumar R., and Sivakumar D. A sieve algorithm for the shortest lattice vector problem // Proc. STOC'01. Hersonissos, Greece, 2001. P.601-610.
Shor P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer // SIAM Rev. 1995. No. 41. P.303-332.
Современные парадигмы построения схем цифровой подписи на решётках | Прикладная дискретная математика. 2025. № 67. DOI: 10.17223/20710410/67/2
Современные парадигмы построения схем цифровой подписи на решётках | Прикладная дискретная математика. 2025. № 67. DOI: 10.17223/20710410/67/2