Des calculs dans le cloud complètement confidentiels, même vis-à-vis du serveur ? Grâce à la cryptographie, cela sera sans doute bientôt possible. Du moins certains l'espèrent.
1. Qu'est-ce que le chiffrement homomorphe ?
À l'heure du cloud computing, de plus en plus d'applications sont exécutées sur des serveurs distants au lieu d'être exécutées localement sur la machine de l'usager. Pensez par exemple ChatGPT : on lui envoie des requêtes en langage naturel, elles sont traitées par d'énormes réseaux de neurones sur un serveur, et seulement le résultat nous est renvoyé.
Lorsqu'un utilisateur veut déléguer des calculs à un agent extérieur, il doit lui partager ses données. Pendant le transfert, la confidentialité peut être garantie facilement grâce à des protocoles utilisant de la cryptographie. Mais une fois sur le serveur, les données doivent être déchiffrées pour pouvoir travailler dessus. Ainsi, impossible de garantir la moindre confidentialité vis-à-vis du serveur si on veut qu'il effectue des calculs. Mais dans certains cas, la sensibilité de ces données fait que l'usage d'outils distants est délicat : par exemple, les données médicales qu'on pourrait envoyer à des applications d'aide au diagnostic utilisant de l'intelligence artificielle. Une solution miracle pourrait venir de la cryptographie, et plus précisément des technologies de chiffrement homomorphe.
Pour résumer, le chiffrement homomorphe permet à un usager de chiffrer ses données, et à un serveur d'effectuer des opérations mathématiques sur ces données sans jamais avoir à les déchiffrer, permettant de garantir une confidentialité totale à l'usager. L'idée n'est pas neuve et a été imaginée dès 1978, mais posée comme un défi par les créateurs du chiffrement RSA. Si des techniques de chiffrements homomorphes partielles sont connues depuis longtemps (permettant de réaliser seulement des additions chiffrées par exemple), c'est seulement en 2009 qu'un premier schéma de chiffrement complètement homomorphe permettant d'effectuer n'importe quelle opération est proposé par Craig Gentry [1]. Ce schéma, bien que parfaitement correct et fonctionnel d'un point de vue théorique, était très loin d'être utilisable en pratique, car extrêmement lent. La technologie a récemment connu un bond en avant spectaculaire initié par des avancées techniques significatives, au point que nombreux sont les acteurs du domaine croyant que le développement d'applications complètement « homomorphisées » et fonctionnelles sera possible sous quelques années à peine.
Mais le défi technique est de taille, pour deux raisons principales :
- Les chiffrements homomorphes doivent garantir trois propriétés très mal assorties : la sécurité (la confidentialité des données doit être garantie tout au long du processus), la précision (les calculs doivent être corrects malgré le chiffrement) et l'efficacité (les applications homomorphes doivent s’exécuter dans des temps raisonnables).
- Le développement d'applications homomorphes est très complexe, et requiert des connaissances pointues en cryptographie. Pour permettre à un plus large spectre de développeurs de concevoir de telles applications, il est nécessaire de développer des technologies de compilation permettant d'« homomorphiser » n'importe quel programme déjà existant. Un tel compilateur devrait non seulement produire des programmes sécurisés et corrects, mais également optimiser tous les différents paramètres et opérations pour produire les programmes les plus efficaces et économiques possibles.Pour mieux comprendre l'usage de tels chiffrements, voici un protocole-type d'interaction entre un client et un serveur utilisant du chiffrement homomorphe :- Le client choisit une clé secrète et l'utilise pour chiffrer ses données, que nous appelons m. Le chiffré obtenu est noté c. Il est envoyé au serveur.
- À partir de sa clé secrète, le client produit une autre clé appelée clé d'évaluation, qu'il envoie également au serveur. Cette clé a une structure très particulière, qui lui confère des propriétés limitées. Avec cette clé, le serveur pourra effectuer des calculs homomorphes, mais ne pourra pas déchiffrer les messages, ni reconstruire la clé secrète d'origine.
- Le serveur utilise la clé d'évaluation pour calculer, de manière aveugle, le résultat d'une fonction f appliquée aux données chiffrées c. Il obtient un nouveau chiffré c' et le renvoie au client. Notez que ces calculs sont beaucoup plus lents que s’ils avaient été effectués en clair. L’ordre de grandeur retenu est généralement un facteur 10 000 en temps et en mémoire. À l'issue de cette procédure, il envoie le résultat chiffré c' au client.
- Le client déchiffre c' à l'aide de sa clé secrète. Il obtient alors une valeur m'. Si tout s'est bien passé, ce nouveau message vérifie l'égalité m' = f(m).Dans cet article, nous allons passer en revue deux des algorithmes de chiffrement homomorphe les plus prometteurs : CKKS [2] et TFHE [3]. Apparus respectivement en 2016 et 2018, ces chiffrements sont les premiers à atteindre des performances « raisonnables » (nous reviendrons là-dessus pour quantifier cela). Sans ensevelir le lecteur sous les détails techniques, nous présenterons leurs fonctionnalités, leurs forces et faiblesses, et verrons que ces deux chiffrements sont très différents, mais extrêmement complémentaires.
2. Petite plongée dans les schémas de chiffrement homomorphes
Avant de présenter les spécificités de CKKS et de TFHE, attardons-nous un peu sur leurs points communs. Ces deux chiffrements sont basés sur la cryptographie des réseaux euclidiens [4] [5]. Cette technologie est également en plein essor, car elle est considérée comme résistante aux attaques des ordinateurs quantiques, contrairement aux anciens systèmes comme RSA (basée sur la factorisation des nombres entiers) et les systèmes basés sur les courbes elliptiques. Sans rentrer dans les constructions mathématiques abstraites, nous devons évoquer l'élément essentiel garantissant la sécurité de ces schémas : le bruit. En effet, lors du chiffrement on va venir ajouter des « parasites », c'est-à-dire perturber un peu les données en leur ajoutant (ou soustrayant) des petites valeurs aléatoires. Ce bruit doit être dimensionné correctement : pas assez de bruit et le chiffrement ne sera pas assez résistant aux attaques, trop de bruit et les calculs homomorphes seront complètement faussés et les résultats inexploitables. Doser le bruit est un art extrêmement complexe et subtil et est un des plus grands challenges auxquels un cryptographe fait face lorsqu'il développe des systèmes homomorphes.Cette injection de bruit dans les données cause un énorme problème : en effet, à mesure que le serveur effectue ses calculs homomorphes, ce bruit tend à rapidement s'amplifier jusqu'à complètement brouiller le résultat. Ainsi, les schémas de chiffrement homomorphe intègrent un mécanisme de gestion du bruit pour éviter toute perte d'information dans les données. Deux stratégies existent, et définissent les deux grandes familles de schémas : la famille « nivelée » et la famille « bootstrappée ». CKKS et TFHE sont les meilleurs représentants de leur famille respective. Commençons par présenter la branche la plus ancienne : la branche nivelée.
2.1 La branche nivelée avec CKKS
Avant de choisir un algorithme de chiffrement homomorphe, il faut se poser deux questions : quel type de donnée allons-nous manipuler, et quel type d'opération allons-nous effectuer ?Pour ce qui est du type de données, CKKS permet de manipuler des valeurs flottantes, avec une certaine précision. Plus précisément, il manipule des vecteurs de flottants et permet d'exécuter des opérations en parallèle sur chaque composante du vecteur. Il permet ainsi de traiter les données par paquets, contrairement à TFHE qui (on le verra dans la section suivante) traite les données une par une. Bien sûr, une précision plus grande implique des temps de calcul plus longs ! Mais sa capacité à paralléliser le rend compétitif même à précision élevée (40 bits par exemple). Pour donner une idée, CKKS opère sur des paquets de quelques milliers de valeurs à la fois.Côté opérations, CKKS permet d'effectuer des sommes et des produits en homomorphe. La somme est très rapide et ne fait pas trop croître le bruit, par contre le produit de deux chiffrés consomme beaucoup de ressources et augmente le bruit. En effet, chaque multiplication va consommer ce que l'on appelle un niveau de bruit. Ainsi, pour évaluer une certaine fonction, il faut estimer combien de multiplications un chiffré donné va subir (on appelle cette métrique la profondeur multiplicative) et prévoir un nombre de niveaux de bruit suffisant dans les chiffrés pour pouvoir encaisser toutes les multiplications. Évidemment, on n'a rien sans rien, et plus un chiffré possède un nombre élevé de niveaux de bruit, plus les opérations homomorphes sont lentes.
Ces propriétés font de CKKS un candidat sérieux pour implémenter des réseaux de neurones en homomorphe : les couches linéaires sont très efficaces et peuvent traiter un grand nombre de points de données en entrée de manière parallèle. Mais pour évaluer les fonctions d'activation des neurones, les choses se compliquent, car elles sont par essence non linéaires. Une manière de contourner ce problème est de travailler avec des approximations polynomiales de ces fonctions. Un autre problème est la profondeur du réseau : comme expliqué ci-dessus, la profondeur multiplicative est limitée, par conséquent seuls des réseaux peu profonds peuvent être évalués avec CKKS. Cette limite sera bientôt franchie dans les nouvelles versions du chiffrement, car une opération de bootstrapping de plus en plus efficace est actuellement développée par la communauté autour de CKKS. Cette opération permet d'évaluer des fonctions à profondeur multiplicative illimitée, comme nous allons le voir dans la section suivante qui traite des schémas possédant une telle opération.
2.2 La branche bootstrappée avec TFHE
Nous allons à présent nous intéresser au chiffrement TFHE, qui possède une opération de bootstrapping. Commençons par nous poser les mêmes questions que dans la section précédente.En termes de type de données, TFHE est bien plus limité que son homologue : un chiffré ne peut contenir qu'une petite valeur entière de quelques bits. Si cela peut paraître décevant, les possibilités offertes par TFHE compensent largement cette limitation. En effet, intéressons-nous aux opérations homomorphes qu'il nous offre.TFHE permet lui aussi de sommer deux chiffrés, et également de multiplier un chiffré avec une constante en clair. Par contre, l'opération de multiplication chiffré-chiffré de CKKS est remplacée par une opération de lookup table (une « table de correspondance » en français). Concrètement, on peut définir n'importe quelle table associant chaque valeur possible d'un chiffré à une autre valeur. Cela permet d'évaluer n'importe quelle fonction à une entrée ! La durée de cette opération dépend de la taille de l'entrée : plus les chiffrés manipulent des grandes valeurs, plus cette opération est lente.La possibilité d'évaluer des lookup tables offre une réelle flexibilité au développeur, bien plus qu'avec la simple multiplication de CKKS. Mais ce n'est pas le plus beau ! Lorsqu'on évalue une lookup table, le bruit dans les chiffrés est réinitialisé à un niveau raisonnable (c'est l'opération de bootstrapping), ce qui permet de résoudre complètement le problème de croissance du bruit ! Ainsi, contrairement à CKKS avec lequel la profondeur multiplicative est limitée, il est possible avec TFHE d'effectuer autant d'opérations homomorphes qu'on le souhaite sans jamais avoir à se soucier du bruit. On parle alors de chiffrement complètement homomorphe (Fully Homomorphic Encryption), car n'importe quel calcul peut être effectué en homomorphe, peu importe sa complexité !
Si nous récapitulons et comparons les deux chiffrements, on s'aperçoit qu'ils sont extrêmement complémentaires :
- CKKS permet de manipuler des données avec une très grande précision, mais TFHE ne supporte que des faibles précisions.
- CKKS permet de facilement paralléliser des calculs, ce que TFHE ne permet pas de faire.
- Par contre, TFHE permet une profondeur multiplicative infinie grâce à son opération de bootstrapping efficace, contrairement à CKKS qui est limitée par les niveaux de bruit dans les chiffrés.
- Enfin, TFHE permet d'évaluer n'importe quelle fonction, alors que CKKS ne permet que des sommes et des produits.
Chacun des deux chiffrements a donc ses forces et ses faiblesses. Pour illustrer ce que nous venons de voir, je vous propose d'essayer d'implémenter une petite fonction en TFHE.
3. Un exemple d'implémentation de fonction homomorphe
Définissons notre fonction : elle prendra en entrée une chaîne de caractères chiffrée et renverra cette même chaîne, mais dont tous les caractères auront été transformés en majuscule ou en minuscule. Pour cela, nous allons utiliser la librairie tfhe-rs que vous pouvez retrouver ici : https://github.com/zama-ai/tfhe-rs. La librairie étant écrite en Rust, nous allons également utiliser ce langage. Si vous n'êtes pas familier avec Rust, pas de panique ! Nous n'utiliserons que les fonctionnalités basiques du langage et vous ne devriez avoir aucun mal à suivre avec vos connaissances de base en programmation. C'est parti !
Commençons par préciser un peu ce que l’on veut obtenir. Pour nous simplifier la vie, nous allons nous restreindre à des chaînes de caractères ASCII. Pour rappel, un caractère ASCII est encodé sur 7 bits, les majuscules allant de 65 à 90 et les minuscules de 97 à 122. Notez que la distance entre la version majuscule et minuscule d’une lettre donnée est toujours de 32.
Nous utiliserons donc le type FheUint8 de la librairie tfhe-rs pour stocker un caractère chiffré sur 8 bits. Définissons un nouveau type appelé FheAsciiString qui contiendra une chaîne de caractères chiffrée.
On commence par quelques imports et définitions de constantes :
FheUint8};pub const UP_LOW_DISTANCE: u8 = 32;
et on définit notre nouveau type FheAsciiString. Notez que sous le capot, il s’agit simplement d’un vecteur (i.e. une liste) de FheUint8. :
Nous avons besoin de fonctions pour chiffrer et déchiffrer des chaînes de caractères. Commençons par le chiffrement :
Analysons la signature de cette fonction : elle prend en entrée une chaîne de caractères en clair et la clé secrète de l’utilisateur, et renvoie une chaîne chiffrée. La première ligne est une assertion qui vérifie que tous les caractères sont bien des caractères ASCII. On construit alors une chaîne de caractères chiffrée en itérant sur chaque caractère clair. Pour chacun d’entre eux, on appelle la fonction de chiffrement d’un FheUint8 et on les regroupe tous dans un FheAsciiString.
La fonction de déchiffrement est simplement le miroir de la précédente : on parcourt chaque caractère de la chaîne chiffrée et on appelle la fonction de déchiffrement d'un FheUint8 sur chacun d'eux.
Il reste à réaliser les fonctions de modification de casse. Essayons de définir une fonction to_upper, qui prend en entrée un caractère chiffré c et qui peut faire deux choses :
- Si le caractère est un caractère minuscule, elle renvoie le même caractère dans sa version majuscule.
- Si le caractère est déjà un caractère majuscule, ou n’est pas une lettre du tout, elle ne fait rien et renvoie simplement le caractère sans le modifier.
Cela soulève plusieurs problèmes : pour commencer, on doit faire une comparaison pour savoir si un caractère est une minuscule. Comment faire une comparaison avec TFHE ? Comme souvent, la réponse est avec une lookup table ! Concrètement, la table prend en entrée le caractère chiffré, et renvoie un 1 ou un 0 chiffré suivant s’il est plus petit ou plus grand que la valeur passée en argument. tfhe-rs fournit des fonctions toutes faites, par exemple pour vérifier si la valeur chiffrée est supérieure ou égale à 96, on écrira :
et pour vérifier si la valeur est inférieure ou égale à 123 on écrit :
Chacune de ces deux fonctions renvoie un bit chiffré. Pour modéliser le test « c est-il une lettre minuscule ? », il nous reste à combiner les deux bits chiffrés avec un and. C’est très facile avec tfhe-rs , qui surcharge les opérateurs logiques booléens pour les faire fonctionner avec des valeurs chiffrées. Là encore, en pratique ce and est réalisé par une look-up table, mais cette fois à deux entrées. La condition va donc s'écrire très naturellement :
Plutôt simple n’est-ce pas ? Mais ne vous y trompez pas, derrière ce prédicat tout simple se cachent en réalité trois lookup tables chiffrées (dont une bivariée). C’est très loin d’être trivial, et nous verrons qu'elles se font ressentir dans les temps d'exécution !
Maintenant que nous avons un prédicat, nous devons construire une structure if-then-else pour traiter les deux cas de la fonction séparément. Et nous nous heurtons à un nouveau problème.
En effet, rappelez-vous que la réponse à la question « Ce caractère est-il une lettre minuscule ? » est chiffrée. Par conséquent, impossible pour le serveur de décider quelle branche exécuter ! Ainsi, nous allons devoir avoir recours à une petite pirouette algorithmique.
Nous avons vu qu’en ASCII la différence entre une lettre minuscule et son homologue majuscule est de 32. Donc, si le caractère est une minuscule, nous devons lui retrancher 32. Sinon, on ne lui retranche rien du tout. Assez de suspense, voilà la fonction to_upper :
Comme vous pouvez le voir, nous avons ajouté deux nouvelles opérations homomorphes, elles aussi implémentées par la librairie tfhe-rs :
- Une multiplication * entre le résultat du test chiffré et la constante 32 en clair (qui est contenue dans UP_LOW_DISTANCE). Ainsi, si la lettre est bien une minuscule, la multiplication donnera la valeur 32 chiffrée. Sinon, elle renverra un 0 chiffré. Rappelez-vous que si TFHE ne supporte pas la multiplication entre deux chiffrés, il est tout à fait possible de multiplier un chiffré avec un clair. Le résultat d’une telle opération est bien sûr chiffré.
- Puis une soustraction - homomorphe, qui est également une opération de base du schéma.
Cette petite fonction nous aura permis d’illustrer un concept central dans le développement homomorphe : on ne peut pas construire de structure de type if-then-else, car les variables sont chiffrées pour le serveur qui exécute le code ! Ainsi, il faut ruser et trouver des moyens détournés pour contourner ce genre de problème.
Nous avons fait le plus gros du travail ! Construire la fonction to_lower est alors une formalité, il suffit de remplacer l'addition par une soustraction, et de légèrement modifier la condition pour tester si la lettre est une majuscule :
Enfin, il reste à écrire les fonctions de modification de casse pour une chaîne entière : elles appliquent simplement les fonctions to_upper et to_lower à chaque caractère chiffré :
Il nous reste à tester ! On fait cela dans une fonction main, qui génère les clés du client et du serveur, chiffre une phrase, et applique les fonctions string_to_upper et string_to_lower sur la chaîne de caractères chiffrée :
Et voilà ! On peut vérifier que la sortie du programme correspond bien à nos attentes :
Tout au long de l'article, nous avons mentionné le fait que les opérations homomorphes sont très lentes. Voilà une excellente occasion de s'en rendre compte ! Pour vous donner un ordre d'idée, le programme précédent tourne en 13,5 secondes sur un ordinateur portable standard (sans parallélisation ni optimisation particulière). Le même programme en clair tourne en seulement quelques microsecondes... L'impact sur les performances est donc immense. Notez que la quasi-intégralité du temps de calcul correspond aux évaluations de lookup tables, c'est-à-dire aux opérations de bootstrapping.
Pour améliorer les performances du FHE à un niveau « acceptable » pour une utilisation en production, plusieurs pistes sont envisagées, l'une des principales étant la conception de hardware dédié.
Conclusion
Le chiffrement homomorphe est très loin de se limiter à ce qui a été introduit dans cet article. D'autres schémas de chiffrement existent et plusieurs autres librairies open source sont développées. Si vous désirez approfondir, un excellent point de départ est le site de la communauté fhe.org qui vise à centraliser le plus de ressources possible sur le sujet. N'hésitez pas à y faire un tour si le sujet vous intéresse.
Références
[1] C. Gentry, « Fully homomorphic encryption using ideal lattices », Proceedings of the forty-first annual ACM symposium on Theory of computing, 2009
[2] I. Chilloti et al., « TFHE: Fast Fully Homomorphic Encryption over the Torus », Journal of Cryptology, 2019
[3] J. Cheon et al., « Homomorphic Encryption for Arithmetic of Approximate Numbers », Proceedings of ASIACRYPT 2017, 2017
[4] C. Bootland et al., « SoK: On the Security of Cryptographic Problems from Linear Algebra », Number Theoretic Methods in Cryptology, 2019
[5] J. Howe et al., « SoK : How (not) to design and Implement Post-Quantum Cryptography », Topics In Cryptology – CT-RSA 2021, 2021
