ModFalcon: compact signatures based on module NTRU lattices

Chitchanok Chuengsatiansup; Thomas Prest; Damien Stehlé; Alexandre Wallet; Keita Xagawa

Paper 2019/1456

ModFalcon: compact signatures based on module NTRU lattices

Chitchanok Chuengsatiansup, The University of Melbourne

Thomas Prest, PQShield

Damien Stehlé, CryptoLab

Alexandre Wallet, INRIA

Keita Xagawa, Technology Innovation Institute (TII)

Abstract

Lattices lead to promising practical post-quantum digital signatures, combining asymptotic efficiency with strong theoretical security guarantees. However, tuning their parameters into practical instantiations is a delicate task. On the one hand, NIST round 2 candidates based on Lyubashevsky's design (such as Dilithium and qTesla) allow several tradeoffs between security and efficiency, but at the expense of a large bandwidth consumption. On the other hand, the hash-and-sign falcon signature is much more compact and is still very efficient, but it allows only two security levels, with large compactness and security gaps between them. We introduce a new family of signature schemes based on the Falcon design, which relies on module lattices. Our concrete instantiation enjoys the compactness and efficiency of Falcon, and allows an intermediate security level. It leads to the most compact lattice-based signature achieving a quantum security above 128 bits.

Note: Latest update: corrected security estimates that were off by 10-20 bits

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Major revision. ASIACCS
DOI: 10.1145/3320269.3384758
Keywords: public-key cryptography Lattice-Based Cryptography module lattices signature scheme public key encryption NTRU
Contact author(s): c chuengsatiansup @ unimelb edu au
thomas prest @ pqshield com
damien stehle @ cryptolab co kr
alexandre wallet @ inria fr
keita xagawa @ tii ae
History: 2024-03-05: last of 3 revisions; 2019-12-18: received; See all versions
Short URL: https://ia.cr/2019/1456
License: CC BY

BibTeX

@misc{cryptoeprint:2019/1456,
      author = {Chitchanok Chuengsatiansup and Thomas Prest and Damien Stehlé and Alexandre Wallet and Keita Xagawa},
      title = {ModFalcon: compact signatures based on module NTRU lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1456},
      year = {2019},
      doi = {10.1145/3320269.3384758},
      note = {\url{https://eprint.iacr.org/2019/1456}},
      url = {https://eprint.iacr.org/2019/1456}
}