Welcome to the resource topic for 2022/1249
Title:
On Rejection Sampling in Lyubashevsky’s Signature Scheme
Authors: Julien Devevey, Omar Fawzi, Alain Passelègue, Damien Stehlé
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.
ePrint: https://eprint.iacr.org/2022/1249
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .