International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: On Rejection Sampling in Lyubashevsky's Signature Scheme

Julien Devevey , ENS de Lyon
Omar Fawzi , INRIA & ENS de Lyon
Alain Passelègue , INRIA & ENS de Lyon
Damien Stehlé , ENS de Lyon
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2022
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.
Video from ASIACRYPT 2022
  title={On Rejection Sampling in Lyubashevsky's Signature Scheme},
  author={Julien Devevey and Omar Fawzi and Alain Passelègue and Damien Stehlé},