Est-il possible d’effectuer des calculs sur des données sans connaître leurs valeurs ? A priori non répondrait tout un chacun. Pourtant, en utilisant des objets mathématiques très particuliers à base de réseaux euclidiens, l’informaticien Craig Gentry aujourd’hui chercheur à IBM Research a montré en 2009 que ce qui pourrait ressembler à de la magie est en fait une réalité. Depuis trois ans, mathématiciens et informaticiens s’acharnent à mettre en pratique de manière efficace cette réalisation théorique de cryptographie dite homomorphe. Si cette possibilité du chiffrement homomorphe met le monde de cryptographie en émoi, c’est que les implications sont excitantes. En jeu, pas moins que la confidentialité du vote électronique ou celle des données personnelles dématérialisées sur les « nuages » (le cloud computing), qui prennent une importance croissante dans le monde numérique d’aujourd’hui.

Vous souhaitez par exemple conserver vos données sur un serveur distant en toute confidentialité. Partant d’un message clair, vous utilisez un système cryptographique pour rendre le message illisible, puis vous envoyez ce message chiffré sur le serveur d’une entreprise. Si vous souhaitez juste récupérer ce message chiffré plus tard, pas de problème : l’entreprise vous renvoie le message chiffré et vous le décodez. En revanche, si vous souhaitez manipuler ces données, faire des recherches dessus sans rien révéler à l’entreprise de leur contenu, cette dernière doit être capable d’effectuer des calculs sur le message chiffré. Elle vous renvoie alors le fruit de ses calculs, que vous pouvez décoder et vous obtenez le résultat du calcul (déchiffré cette fois). Le point important, c’est qu’à aucun moment l’entreprise n’a eu accès à votre message clair et pourtant elle est parvenue à faire des calculs dessus.

Ce « calculer sans voir » qui est l’essence de la cryptographie homomorphe résulte de la possibilité de faire un même calcul par deux chemins différents. Imaginons que le message clair soit constitué de nombres entiers et que, pour chiffrer, il suffise de doubler chaque nombre de sorte que pour déchiffrer on divise par deux. Avec ce système, on peut faire des additions sur les données chiffrées : partons des entiers 5 et 11 dont on veut faire la somme. Cette somme s’obtient directement en additionnant les deux nombres (5+11 = 16), mais aussi en chiffrant ces deux nombres à l’aide de notre cryptosystème élémentaire (5->10 et 11->22), puis en additionnant ce message chiffré (10+22=32) et enfin en déchiffrant le message (32/2=16). L’entreprise n’a eu accès qu’aux valeurs chiffrées (10 et 22) et pourtant elle a pu faire un calcul sur les données du message clair. Evidemment, ce système de chiffrement n’est pas très dur à casser…

«Tout l’enjeu d’un système « complètement homomorphe » est d’être capable de « mélanger » deux message chiffrés de sorte que, lorsqu’on déchiffre, on puisse obtenir la somme de deux messages clairs, mais également leur produit » explique Damien Stehlé, professeur à l’Ecole normale supérieure de Lyon. A cette seule condition, sera t-on capable de manipuler les messages chiffrés pour faire les calculs que l’on souhaite…

Utilisés quotidiennement, lors d’un paiement par carte bancaire, en téléphonant à l’aide d’un mobile, les systèmes cryptographiques utilisés jusqu’ici souffrent d’un défaut majeur vis à vis du chiffrement homomorphe : ils ne savent faire qu’une seule opération, soit l’addition, soit la multiplication. En 2009, C. Gentry a donc créé la surprise en présentant un système « complètement homomorphe », capable de faire à la fois des opérations d’addition et de multiplication sur des données chiffrées, de répéter ces opérations, et de récupérer ensuite le message clair. « Sa contribution principale a été de trouver le bon objet mathématique sur lequel on peut faire ces opérations de manière sécurisée» explique Damien Stehlé. Et c’est en utilisant des « anneaux de polynômes » que la percée a été faite, ou plus précisément des réseaux euclidiens qui leurs correspondent.

Reste que l’efficacité pratique du système est encore lointaine. Les problèmes sur les réseaux sont réputés sûrs (c’est-à-dire difficilement cassable par un ordinateur) seulement si on prend des clés de chiffrement – la chaîne de caractère utilisée pour chiffrer ou déchiffrer le message – très longues : au lieu de clés de quelques centaines de chiffres utilisés dans les applications courantes, un cryptosystème complètement homorphe nécessite encore des clés longues de plusieurs centaines de mégaoctets, ce qui rend les opérations de chiffrement inopérantes en pratique car il faut plusieurs heures pour chiffrer ou déchiffrer.

Dans ce domaine en pleine effervescence de la cryptographie, les travaux se poursuivent donc pour pousser ce système dans ses retranchements et réduire la taille des clés. On peut aussi compter sur l’imagination des cryptographes qui n’ont pas cesser d’innover depuis les premiers documents chiffrés il y a des millénaires de cela. Et il se pourrait qu’un nouvel objet mathématique étrange, encore à trouver, permette de créer un cryptosystème homomorphe efficace.

Philippe Pajot