HomeIssuesCurrent paradigms for construction of lattice-based digital signature schemes

Current paradigms for construction of lattice-based digital signature schemes | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 67. DOI: 10.17223/20710410/67/2

With the advent of quantum computing, research into post-quantum cryptography has gained significant attention. This is a novel branch of cryptography that utilizes algorithms and protocols designed to withstand attacks from quantum computers. Lattice theory represents a promising area within post-quantum cryptographic research. Two early examples of lattice-based cryptosystems are the GGH and NTRU schemes. These schemes are based on the challenge of finding the closest vector in a lattice and differ primarily in the type of lattice used. The NTRUSign protocol was developed by combining the strengths of both schemes. In 2008, another approach to lattice signatures was introduced by a group of authors. It is based on the hash-and-sign paradigm, in which a signature for a message is generated using a trapdoor. A year later, V. Lyubashevsky proposed another method for constructing lattice-based signatures that utilizes the Fiat - Shamir transform. However, due to the nature of the underlying lattice structure, the algorithm for signature generation produces a correct signature only with a certain probability. This is due to the use of a rejection sampling for security purposes. This paper presents an overview of existing lattice-based signature construction approaches and cryptographic schemes that are based on these approaches. A comparative analysis was conducted on these schemes, identifying the advantages and disadvantages of each method. Based on the results, optimal conditions for the application of each approach have been determined.
Download file
Counter downloads: 15
  • Title Current paradigms for construction of lattice-based digital signature schemes
  • Headline Current paradigms for construction of lattice-based digital signature schemes
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 67
  • Date:
  • DOI 10.17223/20710410/67/2
Keywords
lattice-based signature, lattice theory, post-quantum cryptography
Authors
References
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.
Current paradigms for construction of lattice-based digital signature schemes | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 67. DOI: 10.17223/20710410/67/2
Current paradigms for construction of lattice-based digital signature schemes | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 67. DOI: 10.17223/20710410/67/2
Download full-text version
Counter downloads: 206