Paper 2023/446

Revisiting Preimage Sampling for Lattices

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

Preimage Sampling is a fundamental process in lattice-based cryptography whose performance directly affects the one of the cryptographic mechanisms that rely 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. We first revisit the Lyubashevsky-Wichs (LW) sampler for Micciancio-Peikert (MP) trapdoors which leverages rejection sampling but suffered from strong parameter requirements that hampered performance. We propose 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 30% compared to the original MP sampling technique. It sheds a new light on the LW sampler hoping to open promising perspectives for the efficiency of advanced lattice-based constructions relying on such mechanisms. We then show that we can leverage the special shape of the resulting preimages to design the first lattice-based aggregate signature supporting public aggregation and that achieves relevant compression compared to the concatenation of individual signatures. Our scheme is proven secure in the aggregate chosen-key model coined by Boneh et al. in 2003, based on the well-studied assumptions Module Learning With Errors and Module Short Integer Solution.

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.

Available format(s)
Public-key cryptography
Publication info
Lattice-Based CryptographyTrapdoorsPreimage SamplingAggregate Signature
Contact author(s)
corentin jeudy @ irisa fr
adeline roux-langlois @ cnrs fr
olivier sanders @ orange com
2023-05-16: last of 2 revisions
2023-03-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Corentin Jeudy and Adeline Roux-Langlois and Olivier Sanders},
      title = {Revisiting Preimage Sampling for Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2023/446},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.