Efficient lattice-based zero-knowledge proofs and applications / Rafaël Del Pino ; sous la direction de David Pointcheval et de Vadim Lyubashevsky

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : anglais / English

Informatique

Cryptographie

Classification Dewey : 005.8

Pointcheval, David (1970-....) (Directeur de thèse / thesis advisor)

Lyubashevsky, Vadim (Directeur de thèse / thesis advisor)

Stehlé, Damien (1981-.... ; chercheur en informatique) (Président du jury de soutenance / praeses)

Fouque, Pierre-Alain (1974-....) (Rapporteur de la thèse / thesis reporter)

Brakerski, Zvika (Rapporteur de la thèse / thesis reporter)

Wee, Hoeteck (Membre du jury / opponent)

Agrawal, Shweta (Membre du jury / opponent)

Université de Recherche Paris Sciences et Lettres (2015-2019) (Organisme de soutenance / degree-grantor)

École doctorale Sciences mathématiques de Paris centre (Paris ; 2000-....) (Ecole doctorale associée à la thèse / doctoral school)

École normale supérieure (Paris ; 1985-....). Département d'informatique (Laboratoire associé à la thèse / thesis associated laboratory)

École normale supérieure (Paris ; 1985-....) (Autre partenaire associé à la thèse / thesis associated third party)

Résumé / Abstract : Le chiffrement à base de réseaux euclidiens a connu un grand essor durant les vingt dernières années. Autant grâce à l’apparition de nouvelles primitives telles que le chiffrement complètement homomorphe, que grâce à l’amélioration des primitives existantes, comme le chiffrement á clef publique ou les signatures digitales, qui commencent désormais à rivaliser avec leurs homologues fondés sur la théorie des nombres. Cela dit les preuves à divulgation nulle de connaissance, bien qu’elles représentent un des piliers des protocols de confidentialité, n’ont pas autant progressé, que ce soit au niveau de leur expressivité que de leur efficacité. Cette thèse s’attelle dans un premier temps à améliorer l’état de l’art en matière de preuves à divulgation nulle de connaissance. Nous construisons une preuve d’appartenance à un sous ensemble dont la taille est indépendante de l’ensemble en question. Nous construisons de même une preuve de connaissance amortie qui est plus efficace et plus simple que toutes les constructions qui la précèdent. Notre second propos est d’utiliser ces preuves à divulgation nulle de connaissance pour construire de nouvelles primitives cryptographiques. Nous concevons une signature de groupe dont la taille est indépendante du groupe en question, ainsi qu’un schéma de vote électronique hautement efficace, y compris pour des élections à grand échelle.

Résumé / Abstract : Lattice based cryptography has developed greatly in the last two decades, both with new and stimulating results such as fully-homomorphic encryption, and with great progress in the efficiency of existing cryptographic primitives like encryption and signatures which are becoming competitive with their number theoretic counterparts. On the other hand, even though they are a crucial part of many privacy-based protocols, zero-knowledge proofs of knowledge are still lagging behind in expressiveness and efficiency. The first goal of this thesis is to improve the quality of lattice-based proofs of knowledge. We construct new zero-knowledge proofs of knowledge such as a subset membership proof with size independent of the subset. We also work towards making zero-knowledge proofs more practical, by introducing a new amortized proof of knowledge that subsumes all previous results. Our second objective will be to use the proofs of knowledge we designed to construct novel and efficient cryptographic primitives. We build a group signature whose size does not depend on the size of the group, as well as a practical and highly scalable lattice-based e-voting scheme.