Le chiffrement homomorphe
Problématique et présentation
Problématique : un compromis entre puissance de calcul et confidentialité
Imaginons la problématique suivante : Alice a chez elle des données confidentielles, sur lesquelles elle souhaite appliquer une fonction (par exemple, elle possède un agenda informatisé, et elle souhaite faire une recherche dans cet agenda). Toutefois, Alice n'a pas chez elle la puissance de calcul nécessaire pour effectuer cette fonction (on peut imaginer que l'agenda est trop grand, par exemple). Elle souhaite donc faire appel à son ami Bob qui a lui la puissance de calcul adéquate. Néanmoins, elle veut que ses données restent confidentielles, que Bob n'en ait pas connaissance. Alice va par conséquent chiffrer les données avant de les envoyer à Bob. Se pose alors le problème suivant : comment Bob peut-t-il appliquer une fonction sur ces données si elles sont chiffrées? C'est là toute la problématique du chiffrement homomorphe, que nous allons vous présenter au sein de ces pages.Présentation du chiffrement homomorphe
Le chiffrement homomorphe est un chiffrement qui a la propriété suivante : lorsque l'on applique une opération sur des données chiffrées, puis qu'on les déchiffre, on obtient le même résultat que si l'on avait appliqué l'opération sur les données en clair de départ. Dans notre problématique, cela se traduit par le fait que Bob peut effectuer la fonction de recherche sur l'agenda chiffré, obtenir un résultat sous forme de chiffré et le renvoyer à Alice qui peut le déchiffrer. Le message déchiffré qu'obtiendra alors Alice est le résultat de la recherche qu'elle voulait effectuer.
Formellement, voici comment on définit un cryptosystème homomorphe : Soit \(m\), un message. Un cryptosystème homomorphe est un cryptosystème \(G,E,D\) où quelque soit la fonction \(f\), il existe une fonction \(\tilde{f}\) telle que \(D(E(f(m))) = D(\tilde{f}(E(m)))\). On rappelle que le triplet \((G,E,D)\) représente un cryptosystème : il est constitué à partir de \(G\) (fonction de génération de clés), de \(E\) (fonction de chiffrement, "encryption" en anglais) et de \(D\) (fonction de déchiffrement).
Une fonction peut correspondre à tout type de fonction logique, autrement dit tout type de fonction qui peut être réalisée par un ordinateur classique.
Différents types de chiffrements homomorphes
Les cryptosystèmes homomorphes sont nombreux et différents. On peut en faire une classification selon deux grands axes : les opérations qu'un cryptosystème peut réaliser, et le nombre d'opérations qu'il peut réaliser.Opérations et fonctions
Une opération est une fonction de une à plusieurs variables qui s'applique à tous les éléments d'un ensemble donné et qui retourne un élément dudit ensemble. Les opérations peuvent être de types variables : opérations logiques (les variables sont des booléens), opérations arithmétiques (les variables sont des nombres) etc. Toutes les fonctions qui peuvent être réalisées par un ordinateur peuvent être ramenées, entre autres, à :
- Une fonction logique, c'est-à-dire une fonction qui prend des booléens en entrée et retourne des booléens en sortie. Ceci s'explique par le fait qu'un ordinateur est lui-même un agglomérat de circuits imprimés qui réalisent des fonctions logiques.
- Un polynôme. Ceci est dû au fait qu'un ordinateur travaillera toujours sur un ensemble numérisé, et donc discrétisé et fini. Etant donné qu'il est toujours possible de réaliser une interpolation d'un nombre fini de points à l'aide d'un polynôme, toute fonction qui s'exécute dans un ordinateur peut être ramenée à un polynôme.
- Il suffit de pouvoir réaliser une porte logique NAND (NON-ET) pour réaliser n'importe quelle fonction logique, et donc n'importe quelle fonction calculable par un ordinateur.
- Il suffit de pouvoir réaliser l'addition et la multiplication pour réaliser n'importe quel polynôme, et donc n'importe quelle fonction calculable par un ordinateur.
Chiffrement partiellement homomorphe
Un chiffrement partiellement homomorphe est un chiffrement qui permet de réaliser certaines opérations sur l'espace des chiffrés, mais pas l'ensemble des fonctions possibles, car ces opérations ne sont pas suffisantes pour cela. Par exemple, le cryptosystème RSA est homomorphe pour la multiplication, mais ne l'est pas pour l'addition, il ne peut donc pas réaliser l'ensemble des fonctions calculables par un ordinateur. De même pour le cryptosystème de Paillier qui est pour sa part homomorphe pour l'addition uniquement. Un chiffrement partiellement homomorphe est donc limité par la nature des opérations élémentaires qu'il peut réaliser.
Chiffrement totalement homomorphe
Un chiffrement est dit totalement homomorphe quand il permet de réaliser n'importe quelle fonction. Pour effectuer toutes les fonctions existantes, il suffit seulement en réalité de posséder la multiplication et l'addition. En effet, en informatique, tout algorithme peut être converti en circuit booléen, composé de portes logiques ET, ce qui correspond au produit, et de portes logiques XOR (ou-exclusif), ce qui correspond à la somme.
Chiffrement "somewhat" homomorphe
Un chiffrement somewhat homomorphe est un chiffrement qui permet de réaliser un nombre limité d'opérations sur l'espace des chiffrés. Par exemple les cryptosystèmes DGHV et GSW tels que nous les présentons utilisent du bruit pour chiffrer les messages. Ce bruit se démultipliant à chaque opération, il devient après quelques opérations trop important pour que le chiffré soit toujours déchiffrable. Le nombre d'opérations de ces cryptosystèmes est donc limité, mais nous verrons qu'il existe un procédé, le bootstrap, qui sous certaines hypothèses permet d'obtenir un cryptosystème totalement homomorphe à partir d'un cryptosystème somewhat homomorphe. Un chiffrement somewhat homomorphe est donc limité par le nombre d'opérations élémentaires qu'il peut réaliser.
Notions sur les circuits logiques
Une partie des chiffrements qui seront présentés sur ces pages fonctionneront sur des circuits logiques. C'est-à-dire qu'ils seront faits pour chiffrer des \(0\) et des \(1\), autrement dit des bits. Les opérations entre ces bits seront des portes logiques. Les principales portes logiques sont les portes AND, OR, XOR et NOT.
Il est possible de construire des circuits logiques à partir de ces portes. Toute fonction calculable par un ordinateur peut être représentée sous la forme d'un circuit logique : de la simple addition jusqu'à une intelligence artificielle très complexe, tout est le fruit d'un circuit logique. On peut par exemple construire un circuit qui effectue l'addition entre deux bits ainsi (où la première porte est une porte XOR et la deuxième une porte AND) :
La porte NAND (NON-ET), autrement dit la porte qui correspond à une porte AND suivie d'une porte NOT, est une porte dite "universelle". C'est-à-dire qu'il est possible de créer n'importe quelle fonction sous la forme d'un circuit constitué de portes NAND uniquement.
Implémentations
Ce site web vous propose de découvrir le chiffrement homomorphe à travers plusieurs démonstrateurs pédagogiques. Le premier est un démonstrateur du cryptosystème RSA déterministe, homomorphe pour la multiplication.
Le second vous présente le cryptosystème de Paillier, qui est quant à lui homomorphe pour l'addition. De telles propriétés seraient intéressantes dans l'application du vote électronique.
Enfin, le dernier démonstrateur explique le fonctionnement du cryptosystème DGHV, qui est totalement homomorphe et probabiliste.
Pour aller plus loin
Un article présentant le chiffrement homomorphe avec les réseaux euclidiens sous l'angle d'un jeu sérieux : Cryptis.
Une cryptographie nouvelle : le réseau euclidien
Un rapport de stage présentant l'implémentation de différentes techniques de chiffrement homomorphe.
Etude et implantation du chiffrement homomorphe
Une thèse sur le chiffrement homomorphe sur les cloud bancaires et une comparaison entre les différents algorithmes de chiffrement homomorphe.
Chiffrement Homomorphe appliqué au Cloud Bancaire