Paper 2022/1249

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.