Paper 2022/785

Shorter Hash-and-Sign Lattice-Based Signatures

Thomas Espitau, NTT (Japan)
Mehdi Tibouchi, NTT (Japan)
Alexandre Wallet, IRISA, Univ Rennes 1, Inria , Bretagne Atlantique Center, Rennes
Yang Yu, BNRist, Tsinghua University, Beijing, China, National Financial Cryptography Research Center, Beijing, China
Abstract

Lattice-based digital signature schemes following the hash-and-sign design paradigm of Gentry, Peikert and Vaikuntanathan (GPV) tend to offer an attractive level of efficiency, particularly when instantiated with structured compact trapdoors. In particular, NIST postquantum finalist Falcon is both quite fast for signing and verification and quite compact: NIST notes that it has the smallest bandwidth (as measured in combined size of public key and signature) of all round 2 digital signature candidates. Nevertheless, while Falcon--512, for instance, compares favorably to ECDSA--384 in terms of speed, its signatures are well over 10 times larger. For applications that store large number of signatures, or that require signatures to fit in prescribed packet sizes, this can be a critical limitation. In this paper, we explore several approaches to further improve the size of hash-and-sign lattice-based signatures, particularly instantiated over NTRU lattices like Falcon and its recent variant Mitaka. In particular, while GPV signatures are usually obtained by sampling lattice points according to some \emph{spherical} discrete Gaussian distribution, we show that it can be beneficial to sample instead according to a suitably chosen \emph{ellipsoidal} discrete Gaussian: this is because only half of the sampled Gaussian vector is actually output as the signature, while the other half is recovered during verification. Making the half that actually occurs in signatures shorter reduces signature size at essentially no security loss (in a suitable range of parameters). Similarly, we show that reducing the modulus $q$ with respect to which signatures are computed can improve signature size as well as verification key size almost ``for free''; this is particularly true for constructions like Falcon and Mitaka that do not make substantial use of NTT-based multiplication (and rely instead on transcendental FFT). Finally, we show that the Gaussian vectors in signatures can be represented in a more compact way with appropriate coding-theoretic techniques, improving signature size by an additional 7 to 14%. All in all, we manage to reduce the size of, e.g., Falcon signatures by 30--40% at the cost of only 4--6 bits of Core-SVP security.

Note: Added missing acknowledgements to fundings.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2022
Keywords
Hash-and-signlattice-based cryptographycryptanalysis
Contact author(s)
t espitau @ gmail com
mehdi tibouchi br @ hco ntt co jp
alexandre wallet @ inria fr
yu-yang @ mail tsinghua edu cn
History
2023-07-04: last of 3 revisions
2022-06-18: received
See all versions
Short URL
https://ia.cr/2022/785
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/785,
      author = {Thomas Espitau and Mehdi Tibouchi and Alexandre Wallet and Yang Yu},
      title = {Shorter Hash-and-Sign Lattice-Based Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2022/785},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/785}},
      url = {https://eprint.iacr.org/2022/785}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.