Date de l'exposé : 06 mai 2022 (salle Petri Turing à l'IRISA)
On Rejection Sampling in Lyubashevsky's Signature Scheme
Lyubashevsky’s signatures are based on the Fiat-Shamir with
aborts paradigm, whose central ingredient is the use of rejection sampling
to transform (secret-key-dependent) signature samples into samples from
a secret-key-independent distribution. The choice of these two underly-
ing distributions is part of the rejection sampling strategy, and various
instantiations have been considered up to this day. In this work, we inves-
tigate which strategy leads to the most compact signatures, given signing
runtime requirements. Our main contributions are as follows:
(i) We prove lower bounds for compactness of signatures given signing
runtime requirements, and (ii) show that these lower bounds are reached
considering a new and elementary choice of distributions, namely con-
tinuous uniform distributions over hyperballs. (iii) We also prove that,
for any fixed pair of distributions, classic rejection sampling is the best
strategy for minimizing the number of aborts, as well as (iv) propose a
novel strategy that allows to fix (any) bound on the number of aborts
while still guaranteeing correctness and security.
