Signatures fondées sur les réseaux euclidiens : attaques, analyses et optimisations
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
Lattices have attracted a theoretical interest in the cryptographers' community those past years. They seem to offer a stronger foundation, but have also proved themselves very versatile. Nevertheless, efforts in the direction of the implementation and use of this innovative cryptography have remained very limited: essentially restricted to the ingenious yet premature cryptosystems of the NTRU company around the year 2000. This thesis joins this direction, in particular for the problems of digital signatures. We first present a new attack on the NTRUSign signature scheme: since its introduction, an information leakage has cast doubts about its practical security of that cryptosystem. Our work presents the first practical attack on that scheme despite the implementation of counterineasures. 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 conception and implementation of a new signature scheme, BLISS, with two objectives: provable security and practical efficiency. We introduce the usage of Bimodal Gaussian, that surprisingly allow one to benefit ath the same time from progress on trapless signatures, and from an NTRU-like trap generation. Our implementation is Open-Source, and compete favorably with standardized primitives such as RSA or ECDSA.
Abstract FR:
Les réseaux euclidiens ont été l'objet d'un fort engouement théorique de la part de la communauté des cryptographes ces dernières années. Ils semblent fournir un fondement plus solide, mais s'avèrent aussi plus souples. Cependant, les efforts en direction de la mise en pratique de cette cryptographie innovante restent limités: essentiellement restreints aux cryptosystèmes ingénieux mais précoces de la compagnie NRTU autour des années 2000. Cette thèses s'inscrit dans cette direction, en particulier pour le problème des signatures digitales. Nous présentons en premier lieu une nouvelle attaque sur le schéma de signature NTRUSign: depuis son apparition, la présence dans NTRUSign d'une fuite d'information laissait douter de sa sécurité pratique. Nos travaux présentent la première attaque pratique sur ce schéma malgré les contremesure: mises en place. Nous nous intéressons ensuite à une autre contremesure, l'échantillonnage Gaussien discret, elle prouvablement sure, mais jusqu'alors peu efficace. Nous proposons de nouveaux algorithmes adaptés et efficaces pour cette tache, avec et sans virgule flottante. Nous concluons cette these par la conception et l'implementation d'un nouveau schéma de signature, BLISS, en nous appuyant sur de nombreuses idées du domaine, et avec deux objectifs: la sécurité prouvable, et l'efficacité pratique. Nous introduisons l'utilisation de gaussiennes Bimodales, qui permet, de façon surprenante, de tirer avantage à la fois des progrès sur les signatures sans trappes, et de la génération de trappes a la façon de NTRU. Notre implementation Open-Source, s'avère se comparer favorablement aux primitives standardisées telles que RSA et ECDSA