### On Rejection Sampling in Lyubashevsky's Signature Scheme

##### Abstract

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)
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2022
Keywords
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
History
2022-12-05: revised
See all versions
Short URL
https://ia.cr/2022/1249

CC BY

BibTeX

@misc{cryptoeprint:2022/1249,
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{https://eprint.iacr.org/2022/1249}},
url = {https://eprint.iacr.org/2022/1249}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.