Paper 2022/1249

On Rejection Sampling in Lyubashevsky's Signature Scheme

Julien Devevey, École Normale Supérieure de Lyon
Omar Fawzi, French Institute for Research in Computer Science and Automation, École Normale Supérieure de Lyon
Alain Passelègue, French Institute for Research in Computer Science and Automation, École Normale Supérieure de Lyon
Damien Stehlé, École Normale Supérieure de Lyon

Lyubashevsky’s signatures are based on the Fiat-Shamir with aborts paradigm, whose central ingredient is the use of rejection sampling to transform secret-dependent signature samples into samples from (or close to) a secret-independent target distribution. Several choices for the underlying distributions and for the rejection sampling strategy can be considered. In this work, we study Lyubashevsky’s signatures through the lens of rejection sampling, and aim to minimize signature size given signing runtime requirements. Several of our results concern rejection sampling itself and could have other applications. We prove lower bounds for compactness of signatures given signing run- time requirements, and for expected runtime of perfect rejection sampling strategies. We also propose a Rényi-divergence-based analysis of Lyuba- shevsky’s signatures which allows for larger deviations from the target distribution, and show hyperball uniforms to be a good choice of distri- butions: they asymptotically reach our compactness lower bounds and offer interesting features for practical deployment. Finally, we propose a different rejection sampling strategy which circumvents the expected runtime lower bound and provides a worst-case runtime guarantee.

Note: Subsection 5.4 has been significantly updated compared to the previous version of this article. First, parameters were set for SIS with $B > q$. As estimating the hardness of SIS for such large norm bounds is difficult, we decided to change the parameters so that the SIS bound $B$ is always lower than the modulus $q$. Second, the impact of the cut for hyperballs was underestimated in the Python script. We now provide a Maple worksheet in our security estimate repository showing that this is not the case anymore, and the obtained values are now hard-coded in the Python script. This flaw was leading to unnecessarily large parameters for the hyperball uniforms.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2022
Lattice-based signature signature Fiat-Shamir aborts rejection sampling
Contact author(s)
julien devevey @ ens-lyon fr
omar fawzi @ ens-lyon fr
alain passelegue @ ens-lyon fr
damien stehle @ ens-lyon fr
2022-12-05: revised
2022-09-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Julien Devevey and Omar Fawzi and Alain Passelègue and Damien Stehlé},
      title = {On Rejection Sampling in Lyubashevsky's Signature Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1249},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.