Signatures Fondées sur les Réseaux Euclidiens dans le Paradigme de Fiat-Shamir
Julien Devevey · HAL (Le Centre pour la Communication Scientifique Directe) · 2023
The Fiat-Shamir paradigm enables the systematic design of signature schemes fromidentification protocols. The latter are three-moves interactive protocols between aprover holding onto some secret information and a verifier with a correlated publicinformation. There are efficient and elegant designs for them and as the Fiat-Shamirtransform is simple and flexible, its popularity is easily explained. Unfortunately,its use in the lattice setting turns out to be more difficult and researchers usuallyrely on a variant, the Fiat-Shamir with aborts transform. This thesis proposes astudy of this paradigm and its use in conjunction with Euclidean lattices. First, werecover the security of this transform after identifying flaws in the previous securityreductions. This is also a pretense to study the runtime of the signature as wellas discuss the zero-knowledge flavor satisfied by Lyubashevsky’s scheme, the mostfamous aborting identification protocols based on Euclidean lattices.We then move on to study it in more details. This scheme relies on a generictechnique called rejection sampling, and can be adapted to work with a wide rangeof pairs of distributions to sample from and to reject to, as long as these two dis-tributions are “close”. Under a target average number of iterations of the scheme,we minimize the average Euclidean norm of the final signature, by wisely choos-ing the pair of source and target distributions. This directly decreases the size ofthe signature and also makes forgery attacks harder, allowing for smaller parameterchoices.Next we propose HAETAE, an implementation of the bimodal, uniform over Eu-clidean balls, version of Lyubashevsky’s signature scheme. Let us quickly compare itwith the two lattice-based signature schemes selected by NIST for standardisation.Contrary to Dilithium, which aimed for easy implementation, we aimed for low sig-nature sizes. This results in a scheme with up to 40% smaller signature sizes thanDilithium but up to 8 times signing runtime. When compared to Falcon, however,we still have bigger signature sizes but lower signing runtime. Our implementationis constant-time and relies only on fixed-point arithmetic.Finally, we propose a novel way to avoid rejection sampling by using discreteGaussian convolutions. Contrary to flooding, this solution appears to preserve thesignature and verification key size of the signature scheme and can even be provento be asymptotically smaller. While it requires sampling from an elliptical discreteGaussian, this distribution can be made independent from the message. Our tech-nique can be seen as a generalisation of the bimodal technique, where instead ofrelying on two centers, we randomly pick one over a line with a discrete Gaussiandistribution. This center corrects the distribution of the first message, making thelast message independent from the secret, which was the critical problem that led tothe introduction of rejection sampling in the first place.