Sciences du logiciel - Xavier Leroy 03 - Le calcul sécurisé : calculer sur des données chiffrées ou privées : Chiffrement totalement homomorphe : calculer sur des données chiffrées (2)
Xavier Leroy
Chaire Sciences du logiciel
Année 2025-2026
Collège de France
03 - Le calcul sécurisé : calculer sur des données chiffrées ou privées : Chiffrement totalement homomorphe : calculer sur des données chiffrées (2)
Résumé
Ce cours a poursuivi l'étude du chiffrement totalement homomorphe entamée au cours précédent. Après un rappel de l'approche introduite par Gentry en 2009, qui combine chiffrement faiblement homomorphe et procédure de bootstrap, nous avons étudié trois directions pour rendre cette approche plus utilisable.
La première direction est l'utilisation de chiffrements faiblement homomorphes qui reposent sur le problème LWE (Learning With Errors) et ses variantes RLWE et GLWE. Le problème LWE, introduit par Regev en 2005, est une généralisation du problème LPN (Learning Parity with Noise), bien connu en théorie du codage et en théorie de l'apprentissage statistique, ainsi que du problème CVP (Closest Vector Problem) sur les réseaux euclidiens. LWE permet de construire des schémas de chiffrement élégants, post-quantiques, et faiblement homomorphes pour l'addition et la multiplication par une constante.
La deuxième direction consiste à améliorer l'opération de multiplication homomorphe pour qu'elle introduise moins de bruit dans les résultats. Nous avons détaillé l'approche BGV proposée par Brakerski, Gentry, et Vaikuntanathan en 2012, qui effectue une étape de réduction de module après chaque multiplication, afin de garder le bruit quasi-constant en valeur absolue. Cela augmente considérablement la profondeur multiplicative des circuits qui peuvent être évalués homomorphiquement sans recours à un bootstrap.
La troisième direction vise à rendre la procédure de bootstrap moins coûteuse. Nous avons étudié l'approche FHEW/TFHE proposée par Chillotti, Gama, Georgieva et Izabachène en 2016, qui repose sur un accès indexé homomorphe dans une table de constantes calculées et chiffrées à l'avance. Combinée avec un changement de clé et un changement de module, cette approche à base de tables débouche sur un bootstrap programmable, qui non seulement réduit le bruit mais aussi calcule de manière homomorphe une fonction des textes clairs dans les textes clairs.