Paper 2023/446

Phoenix: Hash-and-Sign with Aborts from Lattice Gadgets

Corentin Jeudy, Orange Labs, Applied Crypto Group, Univ Rennes, CNRS, IRISA
Adeline Roux-Langlois, Normandie Univ, UNICAEN, ENSICAEN, CNRS, GREYC
Olivier Sanders, Orange Labs, Applied Crypto Group
Abstract

Preimage sampling is a fundamental tool in lattice-based cryptography, and its performance directly impacts that of the cryptographic mechanisms relying on it. In 2012, Micciancio and Peikert proposed a new way of generating trapdoors (and an associated preimage sampling procedure) with very interesting features. Unfortunately, in some applications such as digital signatures, the performance may not be as competitive as other approaches like Fiat-Shamir with Aborts. In an effort to improve preimage sampling for Micciancio-Peikert (MP) trapdoors, Lyubashevsky and Wichs (LW) introduced a new sampler which leverages rejection sampling but suffers from strong parameter requirements that hampered performance. As a consequence it seemed to be restricted to theoretical applications and has not been, to our knowledge, considered for real-world applications. Our first contribution is to revisit the LW sampler by proposing an improved analysis which yields much more compact parameters. This leads to gains on the preimage size of about 60% over the LW sampler, and up to 25% compared to the original MP sampling technique. It thus sheds a new light on the LW sampler, opening promising perspectives for the efficiency of advanced lattice-based constructions relying on such mechanisms. To provide further improvements, we show that it perfectly combines with the approximate trapdoors approach by Chen, Genise and Mukherjee, but with a smaller preimage error. Building upon those results, we introduce a hash-and-sign signature scheme called Phoenix. The scheme is based on the M-LWE and M-SIS assumptions and features attractive public key and signature sizes which are even smaller than those of the most recent gadget-based construction Eagle of Yu, Jia and Wang (Crypto’23). Moreover, Phoenix is designed to be implementation-friendly, avoiding in particular complex Gaussian samplers that are often hard to protect.

Note: A preliminary version of this work has been published as ePrint 2023/239. Unintentionally, one of the contributions was significantly overlapping with the result of Lyubashevsky and Wichs at PKC 2015 (ePrint 2014/1027), leading us to withdraw the paper. This new version presents the other contributions and provides a thorough comparison with ePrint 2014/1027, highlighting our actual contribution on this aspect. In the latest version, we chose to redirect the paper towards hash-and-sign signatures and thus relocated the aggregate signature in appendix. This choice was only dictated for the coherence of the paper and in particular does not result from any flaw of the latter contribution. The title also changed from 'Revisiting Preimage Sampling for Lattices' to 'Phoenix: Hash-and-Sign with Aborts from Lattice Gadgets'

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Lattice-Based CryptographyTrapdoorsPreimage SamplingSignature
Contact author(s)
corentin jeudy @ irisa fr
adeline roux-langlois @ cnrs fr
olivier sanders @ orange com
History
2023-10-04: last of 3 revisions
2023-03-27: received
See all versions
Short URL
https://ia.cr/2023/446
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/446,
      author = {Corentin Jeudy and Adeline Roux-Langlois and Olivier Sanders},
      title = {Phoenix: Hash-and-Sign with Aborts from Lattice Gadgets},
      howpublished = {Cryptology ePrint Archive, Paper 2023/446},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/446}},
      url = {https://eprint.iacr.org/2023/446}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.