Current paradigms for construction of lattice-based digital signature schemes

A. G. Leevik ; E. S. Malygina ; E. M. Melnichuk ; D. A. Nabokov

Prikladnaâ diskretnaâ matematika, no. 1 (2025), pp. 36-69.

Résumé

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.

Détail

Keywords: post-quantum cryptography, lattice theory, lattice-based signature.

Bibliographie

[1] Shor P. W., “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM Rev., 1995, no. 41, 303–332 | MR

[2] Ajtai M., Kumar R., and Sivakumar D., “A sieve algorithm for the shortest lattice vector problem”, Proc. STOC'01 (Hersonissos, Greece), 2001, 601–610 | DOI | MR

[3] Dinur I., Kindler G., and Safra S., “Approximating CVP to within almost-polynomial factors is NP-hard”, Combinatorica, 23 (2003), 205–243 | DOI | MR

[4] Roy S. S., Vercauteren F., Mentens N., et al., “Compact ring-LWE cryptoprocessor”, LNCS, 8731, 2014, 371–391

[5] Ajtai M., “Generating hard instances of lattice problems”, Proc. STOC'96 (Philadelphia, Pennsylvania, USA), 1996, 99–108 | MR

[6] Regev O., “On lattices, learning with errors, random linear codes, and cryptography”, Proc. STOC'05 (Baltimore, MD, USA), 2005, 84–93 | DOI | MR

[7] Micciancio D., “Generalized compact knapsacks, cyclic lattices, and efficient one-way functions”, Comput. Complexity, 2007, no. 16(4), 365–411 | DOI | MR

[8] Peikert C. and Rosen A., “Lattices that admit logarithmic worst-case to average-case connection factors”, Proc. STOC'07 (San Diego, California, USA), 2007, 478–487 | DOI | MR

[9] Lyubashevsky V. and Micciancio D., “Generalized compact knapsacks are collision resistant”, LNCS, 4052, 2006, 144–155 | MR

[10] Lyubashevsky V., “Fiat — Shamir with aborts: Applications to lattice and factoring-based signatures”, LNCS, 5912, 2009, 598–616 | MR

[11] Lyubashevsky V., Peikert C., and Regev O., “On ideal lattices and learning with errors over rings”, J. ACM, 60 (2010), 43:1–43:35 | MR

[12] Langlois A. and Stehlé D., “Worst-case to average-case reductions for module lattices”, Des. Codes Cryptography, 75 (2015), 565–599 | DOI | MR

[13] Goldreich O., Goldwasser S., and Halevi S., “Public-key cryptosystems from lattice reduction problems”, LNCS, 1294, 1997, 112–131 | MR

[14] Hoffstein J., Pipher J., and Silverman J. H., “NTRU: A ring-based public key cryptosystem”, LNCS, 1423, 1998, 267–288 | MR

[15] Hoffstein J., Howgrave-Graham N., Pipher J., et al., “NTRUSign: Digital signatures using the NTRU lattice”, LNCS, 2612, 2003, 122–140 | MR

[16] Hoffstein J., Pipher J., and Silverman J. H., “NSS: An NTRU lattice-based signature scheme”, LNCS, 2045, 2001, 211–228 | MR

[17] Gentry C., Jonsson J., Stern J., and Szydlo M., “Cryptanalysis of the NTRU Signature Scheme (NSS) from Eurocrypt 2001”, LNCS, 2248, 2001, 1–20 | MR

[18] Gentry C. and Szydlo M., “Cryptanalysis of the revised NTRU signature scheme”, LNCS, 2332, 2002, 299–320 | MR

[19] Nguyen P. Q. and Regev O., “Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures”, J. Cryptology, 22:2 (2009), 139–160 | DOI | MR

[20] Ducas L. and Nguyen P. Q., “Learning a zonotope and more: Cryptanalysis of NTRUSign countermeasures”, LNCS, 7658, 2012, 433–450

[21] Melchor C. A., Boyen X., Deneuville J.-C., and Gaborit P., “Sealing the leak on classical NTRU signatures”, LNCS, 8772, 2014, 1–21 | MR

[22] Hoffstein J., Howgrave-Graham N., Pipher J., et al., “NTRUSIGN: Digital signatures using the NTRU lattice”, LNCS, 2612, 2003, 122–140 | MR

[23] 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

[24] Gentry C., Peikert C., and Vaikuntanathan V., “Trapdoors for hard lattices and new cryptographic constructions”, Proc. STOC'08 (Victoria, British Columbia, Canada), 2008, 197–206 | MR

[25] Stehlé D. and Steinfeld R., “Making NTRU as secure as worst-case problems over ideal lattices”, LNCS, 6632, 2011, 27–47 | MR

[26] Lyubashevsky V., “Lattice signatures without trapdoors”, LNCS, 7237, 2012, 738–755 | MR

[27] Gama N. and Nguyen P. Q., “Predicting lattice reduction”, LNCS, 4965, 2008, 31–51 | MR

[28] Howgrave-Graham N., “A hybrid lattice-reduction and meet-in-the-middle attack against NTRU”, LNCS, 4622, 2007, 150–169 | MR

[29] May A. and Silverman J. H., “Dimension reduction methods for convolution modular lattices”, LNCS, 2146, 2001, 110–125 | MR

[30] Stehlé 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 | MR

[31] Boneh D., Dagdelen Ö., Fischlin M., et al., “Random oracles in a quantum world”, LNCS, 7073, 2011, 41–69 | MR

[32] Diffie W. and Hellman M. E., “New directions in cryptography”, IEEE Trans. Inform. Theory, 22:6 (1976), 644–654 | DOI | MR

[33] Bellare M. and Rogaway P., “Random oracles are practical: A paradigm for designing efficient protocols”, Proc. CCS'93 (Fairfax, Virginia, USA), 1993, 62–73

[34] Micciancio D. and Peikert C., “Trapdoors for lattices: Simpler, tighter, faster, smaller”, LNCS, 7237, 2012, 700–718 | MR

[35] Alwen J. and Peikert C., “Generating shorter bases for hard random lattices”, Theory Comput. Syst., 48:3 (2011), 535–553 | DOI | MR

[36] Peikert C. and Rosen A., “Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices”, LNCS, 3876, 2006, 145–166 | MR

[37] Fouque P.-A., Hoffstein J., Kirchner P., et al., Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU, Specification v1.2, , 2020 https://falcon-sign.info/falcon.pdf

[38] Ducas L. and Prest T., “Fast Fourier orthogonalization”, Proc. ISSAC'16 (Waterloo, ON, Canada), 2016, 191–198 | MR

[39] Klein P. N., “Finding the closest lattice vector when it's unusually close”, Proc. SODA'00, California, USA, San Francisco, 2000, 937–941 | MR

[40] Micciancio D. and Walter M., “Practical, predictable lattice basis reduction”, LNCS, 9665, 2016, 820–849 | MR

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

[42] 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, 2332, 2002, 418–433 | MR

[43] Schnorr C. P., “Efficient signature generation by smart cards”, J. Cryptology, 4:3 (1991), 161–174 | DOI | MR

[44] Lyubashevsky V., “Fiat — Shamir with aborts: Applications to lattice and factoring-based signatures”, LNCS, 5912, 2009, 598–616 | MR

[45] Ducas L., Kiltz E., Lepoint T., et al., “CRYSTALS-Dilithium: A lattice-based digital signature scheme”, IACR Trans. Cryptographic Hardware and Embedded Systems, 2018, no. 1, 238–268 | DOI

[46] 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), Report 8413, 2022 https://csrc.nist.gov/pubs/ir/8413/upd1/final

[47] Cheon J. H., Choe H., Devevey J., et al., HAETAE: Shorter Lattice-Based Fiat — Shamir Signatures, Cryptology ePrint Archive. Paper 2023/624, , 2023 https://eprint.iacr.org/2023/624

[48] Devroye L., “General principles in random variate generation”, Non-Uniform Random Variate Generation, Springer, N.Y., 1986, 27–82 | DOI | MR

[49] 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, 390–399 | DOI

[50] Ducas L., Durmus A., Lepoint T., and Lyubashevsky V., “Lattice signatures and bimodal gaussians”, LNCS, 8042, 2013, 40–56 | MR

[51] Groot Bruinderink L., Hülsing A., Lange T., and Yarom Y., “Flush, Gauss, and reload — a cache attack on the BLISS lattice-based signature scheme”, LNCS, 9813, 2016, 323–345

[52] Espitau T., Fouque P. A., Gérard 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, 1857–1874

[53] Pessl P., Bruinderink L. G., and Yarom Y., “To BLISS-B or not to be: Attacking strongSwan's implementation of post-quantum signatures”, Proc. CCS'17 (Dallas, Texas, USA), 2017, 1843–1855

[54] Devevey J., Fawzi O., Passelègue A., and Stehlé D., “On rejection sampling in Lyubashevsky's signature scheme”, LNCS, 13794, 2022, 34–64 | MR

[55] Brakerski Z., Gentry C., and Vaikuntanathan V., “(Leveled) fully homomorphic encryption without bootstrapping”, Proc. ITCS'12 (Cambridge, Massachusetts), 2012, 309–325 | MR

[56] Bai S. and Galbraith S. D., “An improved compression technique for signatures based on learning with errors”, LNCS, 8366, 2014, 28–47 | MR

[57] Kiltz E., Lyubashevsky V., and Schaffner C., “A concrete treatment of Fiat — Shamir signatures in the quantum random-oracle model”, LNCS, 10822, 2018, 552–586 | MR

[58] Don J., Fehr S., Majenz C., and Schaffner C., “Security of the Fiat — Shamir transformation in the quantum random-oracle model”, LNCS, 11693, 2019, 356–383 | MR

[59] Liu Q. and Zhandry M., “Revisiting post-quantum Fiat — Shamir”, LNCS, 11693, 2019, 326–355

[60] Devevey J., Fallahpour P., Passelègue A., and Stehlé D., “A detailed analysis of Fiat — Shamir with aborts”, LNCS, 14085, 2023, 327–357 | MR

[61] Schnorr C. P. and Euchner M., “Lattice basis reduction: Improved practical algorithms and solving subset sum problems”, Math. Programming, 66 (1994), 181–199 | DOI | MR

[62] Alkim E., Ducas L., Pöppelmann T., and Schwabe P., “Post-quantum key exchange: A new hope”, Proc. SEC'16 (Austin, TX, USA), 2016, 327–343

[63] Becker A., Ducas L., Gama N., and Laarhoven T., “New directions in nearest neighbor searching with applications to lattice sieving” (Arlington, Virginia), Proc. SODA'16, 2016, 10–24 | MR

[64] Laarhoven T., Mosca M., and Van De Pol J., “Finding shortest lattice vectors faster using quantum search”, Des. Codes Cryptography, 77 (2015), 375–400 | DOI | MR

[65] Schnorr C. P., “Lattice reduction by random sampling and birthday methods”, LNCS, 2607, 145–156 | MR

[66] Chen Y., Réduction de réseau et sécurité concrete du chiffrement completement homomorphe, Thés. se de doctorat, Paris, 2013 (in French)

[67] Howe J. and Westerbaan B., “Benchmarking and analysing the NIST PQC lattice-based signature schemes standards on the ARM Cortex M7”, LNCS, 14064, 2023, 442–462 | MR

[68] Vidaković M. and Miličević K., “Performance and applicability of post-quantum digital signature algorithms in resource-constrained environments”, Algorithms, 16:11 (2023), 518 | DOI

[69] Lyubashevsky V., CRYSTALS-Dilithium Round 3 Presentation, , 2021 https://csrc.nist.gov/presentations/2021/crystals-dilithium-round-3-presentation

[70] Westerbaan B., NIST's Pleasant Post-Quantum Surprise, , 2022 https://blog.cloudflare.com/nist-post-quantum-surprise/

[71] Schmieg S., Kolbl S., and Endignoux G., Google's Threat Model for Post-Quantum Cryptography, , 2024 https://bughunters.google.com/blog/5108747984306176/google-s-threat-model-for-post-quantum-cryptography