These de Léo Ducas. Signatures Fondees sur les Reseaux Euclidiens:
Attaques, Analyse et Optimisations
Signatures Fondees sur les Reseaux Euclidiens:
Attaques, Analyse et Optimisations
Lattice Based Signatures:
Attacks, Analysis and Optimization
Léo Ducas
Thesis PDF
Slides PDF
Slides with 3D HTML (section 3)
Résumé:
Les réseaux euclidiens font l'objet d'un fort engouement de la part de la
communauté de
recherche théorique en cryptographie ces dernières années. Ils offrent des
fondations
peut-être plus solides, et s'avèrent aussi plus souples. Cependant, les
efforts
d'implémentation efficace de cette cryptographie innovante restent limités
: il s'agit essentiellement des cryptosystèmes NTRU introduits à la fin
des années 1990.
Cette thèse s'inscrit dans cette direction,
en se focalisant sur cas des signatures numériques.
Nous présentons d'abord la première attaque pratique sur le schéma de
signature NTRUSign
lorsque des contremesures sont mises en place,
notamment celles proposées par l'entreprise NTRU.
Pour cela, nous montrons que l'attaque de Nguyen-Regev est plus robuste
que prévue :
elle permet d'apprendre des structures plus complexes que des
parallélépipèdes,
comme les zonotopes et des parallélépipèdes déformés.
Nous nous intéressons ensuite à une autre contremesure :
l'échantillonnage Gaussien discret, qui permet de prouver des propriétés
de securité,
mais qui était jusqu'alors peu efficace. Nous proposons de nouveaux
algorithmes adaptés et efficaces pour cette tache, avec et sans virgule
flottante.
Nous concluons cette thèse par la conception et l'implémentation d'un
nouveau schéma de signature, BLISS, en nous appuyant sur de nombreuses
idées du domaine, et en ayant deux objectifs :
la sécurité prouvée, et l'efficacité pratique. Nous introduisons
l'utilisation de gaussiennes bimodales, qui permet, de façon surprenante,
de tirer parti à la fois des progrès sur les signatures sans trappes, et
de la génération de trappes à la manière de NTRU. Notre implémentation
Open-Source s'avère compétitive avec les normes RSA et ECDSA.
Abstract:
Lattices have attracted significant interest in theoretical cryptographic
research
in the past few years. They offer perhaps stronger foundations, and have
also proved
very versatile. However, efforts towards efficient implementations of
lattice-based
cryptosystems have remained limited: they are essentially restricted to
NTRU primitives
introduced at the end of the 1990s. This thesis goes in this direction,
and focuses on digital signatures.
We first present a practical attack on the \textsc{NTRUSign} signature scheme
in the presence of countermeasures, such as the one proposed by NTRU.
To do this, we show that the Nguyen-Regev attack is more robust than
expected:
it is able to learn more complex objects than parallelepipeds,
such as zonotopes or deformed parallelepipedes.
We then move our attention to an alternative countermeasure that is
provably secure, yet not so efficient. We propose new algorithms that are
adapted and efficient for this task, with or without usage of floating
point.
We conclude this thesis with the design and implementation of a new
signature scheme, BLISS, with two objectives in mind: provable security
and practical efficiency.
We introduce the use of Bimodal Gaussian, which surprisingly allows one to
benefit from both trapdoor-less signatures and NTRU-like trapdoor
generation. Our implementation is Open-Source, and competes favorably with
the RSA and ECDSA standards.