Vers l'efficacité et la sécurité du chiffrement homomorphe et du cloud computing

Le chiffrement homomorphe est une branche de la cryptologie, dans laquelle les schemas de chiffrement offrent la possibilite de faire des calculs sur les messages chiffres, sans besoin de les dechiffrer. L’interet pratique de ces schemas est du a l’enorme quantite d'applications pour lesquels ils peuvent etre utilises. En sont un exemple le vote electronique, les calculs sur des donnees sensibles, comme des donnees medicales ou financieres, le cloud computing, etc..Le premier schema de chiffrement (completement) homomorphe n'a ete propose qu'en 2009 par Gentry. Il a introduit une technique appelee bootstrapping, utilisee pour reduire le bruit des chiffres : en effet, dans tous les schemas de chiffrement homomorphe proposes, les chiffres contiennent une petite quantite de bruit, necessaire pour des raisons de securite. Quand on fait des calculs sur les chiffres bruites, le bruit augmente et, apres avoir evalue un certain nombre d’operations, ce bruit devient trop grand et, s'il n'est pas controle, risque de compromettre le resultat des calculs.Le bootstrapping est du coup fondamental pour la construction des schemas de chiffrement homomorphes, mais est une technique tres couteuse, qu'il s'agisse de la memoire necessaire ou du temps de calcul. Les travaux qui on suivi la publication de Gentry ont eu comme objectif celui de proposer de nouveaux schemas et d’ameliorer le bootstrapping pour rendre le chiffrement homomorphe faisable en pratique. L’une des constructions les plus celebres est GSW, propose par Gentry, Sahai et Waters en 2013. La securite du schema GSW se fonde sur le probleme LWE (learning with errors), considere comme difficile en pratique. Le bootstrapping le plus rapide, execute sur un schema de type GSW, a ete propose en 2015 par Ducas et Micciancio. Dans cette these on propose une nouvelle variante du schema de chiffrement homomorphe de Ducas et Micciancio, appelee TFHE.Le schema TFHE ameliore les resultats precedents, en proposant un bootstrapping plus rapide (de l'ordre de quelques millisecondes) et des cles de bootstrapping plus petites, pour un meme niveau de securite. TFHE utilise des chiffres de type TLWE et TGSW (scalaire et ring) : l’acceleration du bootstrapping est principalement due a l’utilisation d’un produit externe entre TLWE et TGSW, contrairement au produit externe GSW utilise dans la majorite des constructions precedentes.Deux types de bootstrapping sont presentes. Le premier, appele gate bootstrapping, est execute apres l’evaluation homomorphique d’une porte logique (binaire ou Mux) ; le deuxieme, appele circuit bootstrapping, peut etre execute apres l’evaluation d’un nombre d'operations homomorphiques plus grand, pour rafraichir le resultat ou pour le rendre compatible avec la suite des calculs.Dans cette these on propose aussi de nouvelles techniques pour accelerer l’evaluation des calculs homomorphiques, sans bootstrapping, et des techniques de packing des donnees. En particulier, on presente un packing, appele vertical packing, qui peut etre utilise pour evaluer efficacement des look-up table, on propose une evaluation via automates deterministes ponderes, et on presente un compteur homomorphe appele TBSR qui peut etre utilise pour evaluer des fonctions arithmetiques.Pendant les travaux de these, le schema TFHE a ete implemente et il est disponible en open source.La these contient aussi des travaux annexes. Le premier travail concerne l’etude d’un premier modele theorique de vote electronique post-quantique base sur le chiffrement homomorphe, le deuxieme analyse la securite des familles de chiffrement homomorphe dans le cas d'une utilisation pratique sur le cloud, et le troisieme ouvre sur une solution differente pour le calcul securise, le calcul multi-partite.