Le chiffrement totalement homomorphe (FHE)

Un schéma partiellement homomorphe ne sait faire qu'une opération. Or n'importe quel calcul se ramène à des additions et des multiplications. Il fallait donc un schéma qui accepte les deux. Ce fut le graal de la cryptographie pendant trente ans.

La définition du FHE

Un schéma totalement homomorphe (en anglais Fully Homomorphic Encryption, FHE) permet d'effectuer sur les chiffrés à la fois des additions et des multiplications, en nombre arbitraire.

Pourquoi ces deux opérations suffisent ? Parce qu'avec l'addition et la multiplication modulo 2, on reconstruit les portes logiques XOR et AND, et avec ces portes on construit n'importe quel circuit, donc n'importe quel calcul. Un schéma FHE peut donc, en principe, évaluer un programme complet sur des données chiffrées.

La percée de Gentry (2009)

Le problème est resté ouvert de 1978 jusqu'à 2009, année où Craig Gentry présente le premier schéma FHE de l'histoire, dans sa thèse. Sa construction repose sur les réseaux euclidiens (en anglais lattices), une structure mathématique dont certains problèmes sont réputés difficiles, y compris face à un ordinateur quantique.

Le problème du bruit

Pour être sûrs, ces schémas ajoutent un peu de bruit aléatoire à chaque chiffré. Ce bruit est petit au départ, mais il s'accumule à chaque opération :

• une addition augmente le bruit modérément ;
• une multiplication le fait croître beaucoup plus vite.

Si le bruit dépasse un certain seuil, le déchiffrement devient faux : le message est perdu. On ne peut donc enchaîner qu'un nombre limité d'opérations.

niveau de bruit
   |
seuil ─ ─ ─ ─ ─ ─ ─ ─●─ ─ ─ ─ ─ ─  (au-delà : déchiffrement faux)
   |              ╱
   |           ╱
   |        ╱
   |     ╱
   |  ╱
   |╱_______________________ opérations
      op  op  op  op  op

Le bootstrapping : l'idée géniale

La contribution décisive de Gentry est le bootstrapping. L'idée : faire évaluer au schéma son propre déchiffrement, de façon homomorphe. Le résultat est un nouveau chiffré du même message, mais dont le bruit a été réinitialisé à un niveau bas.

chiffré très bruité  --[ bootstrapping ]-->  même message, bruit réinitialisé

Une fois le bruit remis à zéro, on peut repartir et continuer à calculer. En répétant le bootstrapping, on enchaîne un nombre illimité d'opérations — ce qui rend le schéma totalement homomorphe, et pas seulement pour quelques opérations.

En résumé

Le FHE permet des additions et des multiplications arbitraires, donc n'importe quel calcul sur des données chiffrées. Le premier schéma est dû à Gentry (2009), fondé sur les réseaux euclidiens. Chaque opération ajoute du bruit qui, au-delà d'un seuil, rend le déchiffrement faux ; le bootstrapping réinitialise ce bruit et permet de calculer indéfiniment.