Chiffrement homomorphe : une idée vieille de 50 ans, qui prend « vie » depuis 10 ans

[Rediffusion du Mag #3] Cela fait des années que la question du chiffrement homomorphe est « dans l’air », retenant surtout l’attention des chercheurs. Il faut dire que la promesse de tels dispositifs est d’effectuer des opérations sur des données alors qu’elles sont chiffrées. On les utilise sans les connaître. 

De quoi changer en profondeur la manière dont on gère les questions de vie privée. On s’approche peu à peu de systèmes réellement exploitables, expliquant un intérêt croissant de certains acteurs ces dernières années.

En mars 2021, la Darpa annonçait ainsi s’associer à Intel et Microsoft pour travailler à des systèmes exploitant ce procédé. L'été suivant, on apprenait que Facebook recrutait des chercheurs dans le domaine, dans l’espoir d’exploiter le chiffrement homomorphe pour WhatsApp, selon The Information. 

Dans le même temps, le gouvernement français présentait son plan Cyber, doté de 65 millions d’euros pour la recherche. Une telle somme, « c'est beaucoup et c'est peu, ça dépend le point de vue que l'on prend », expliquait alors Gildas Avoine, professeur à l'INSA Rennes.

Un des principaux sujets concernait l’utilisation par les algorithmes de données personnelles, médicales, financières, économiques… Pouvoir les traiter avec une garantie de confidentialité est un enjeu majeur en cryptographie. C’est là que le chiffrement homomorphe entre en scène.

Afin d‘y voir clair dans ce domaine de la cryptographie, nous nous sommes entretenus avec Renaud Sirdey, directeur de recherche au CEA (Commissariat à l'énergie atomique et aux énergies alternatives) et spécialiste de la cryptographie (homomorphe) depuis plusieurs années. 

Le chiffrement homomorphe expliqué simplement

Il commence par nous rappeler que « le chiffrement homomorphe, avant toute chose, ce sont des cryptosystèmes ». Ce terme est utilisé pour désigner un ensemble cryptographique, qui comprend aussi bien les messages chiffrés, en clair, les algorithmes et les clés de (dé)chiffrement associées. 

La robustesse d’un cryptosystème s’appuie – et se démontre – avec les mathématiques. En effet, l’attaquer revient à s’attaquer à « la résolution d’un problème mathématique conjecturé comme étant difficile ». Et quand on parle de difficulté dans le cas présent, cela se traduit dans la pratique par un temps quasi infini – ou en tout cas très long (en milliers, voire milliards d’années) – pour en venir à bout, même avec les supercalculateurs actuels.

Généralement, pour effectuer un traitement sur des données chiffrées, par exemple pour modifier un texte ou retoucher une photo, il faut commencer par les déchiffrer. Ce n’est plus le cas avec le chiffrement homomorphe, qui consiste à « prendre deux éléments chiffrés et leur appliquer un opérateur qui produit un nouveau chiffré ». Il n’y a pas besoin de déchiffrer les messages, ni donc de les connaître, pour effectuer des calculs.

C’est le point essentiel : « lorsqu'on fait du chiffrement homomorphe, tout produit dérivé des chiffrés d'entrées est également scellé sous le cryptosystème », y compris les résultats intermédiaires, nous précise Renaud Sirdey.

Les données chiffrées peuvent ainsi être confiées à un tiers (un service cloud par exemple) sans avoir besoin de lui accorder la moindre confiance puisqu’il ne peut pas accéder aux informations en clair. Pour déchiffrer les données, les calculs intermédiaires ou bien le résultat, il faut avoir la clé.

On dispose ainsi d’opérateurs homomorphes permettant d’effectuer des additions et des multiplications, ce qui implique qu’« il n’y a pas de restriction de principe » sur les usages que l’on peut en tirer. En effet, n’importe quel algorithme mathématique peut se résumer à une suite d’additions et de multiplications. Voici pour la théorie, dans la pratique ce n’est pas forcément aussi simple…

En effet, une des principales difficultés est « que ces opérateurs d’addition et de multiplication homomorphes ont des structures mathématiques radicalement différentes d’une simple addition/multiplication ». Elles sont beaucoup plus complexes à réaliser… et c’est peu de le dire.

De plus, ces opérateurs homomorphes « vont avoir un coût [en termes de performances, ndlr], et ce coût computationnel supplémentaire est vraiment très loin d’être négligeable ». Il est donc essentiel de réussir à minimiser cet impact. C’est ce qui explique qu’entre l’idée du chiffrement homomorphe et les premières percées « pratiques », il s'est écoulé des dizaines d’années. 

1978 : « naissance » du chiffrement homomorphe

Renaud Sirdey nous explique d’ailleurs qu’il « y a une histoire derrière cette notion de chiffrement homomorphe » puisque « l’idée a été posée il y a très longtemps, le premier article qui en parle date de 1978 ». C’est à cette époque que Ronald Rivest et Adi Shamir – le R et le S de RSA – « ont proposé la vision d’une première définition d’un système homomorphe ».

Il n’était alors composé que de « quelques constructions mathématiques, avec des opérateurs homomorphes rapidement cassés, mais qui étaient proposés sans prétention ». Peu importe, la machine était lancée. 

« Dans les années 80, les premiers systèmes à sécurité prouvés ont été proposés. On s'est aperçu qu’ils avaient aussi des propriétés homomorphes relativement à l’addition ou à la multiplication, mais pas les deux. Donc ces propriétés ont été un peu ignorées, car quelque part elles ne dérangeaient pas les preuves de sécurité et on ne voyait pas très bien forcément ce qu'on pouvait faire avec. De toute façon elles étaient très limitées », nous précise le directeur de recherche.

« Dans les années 90, on a commencé à avoir des systèmes de chiffrement homomorphes additifs, dont notamment les cryptosystèmes de Paillier qui ont commencé à voir des performances intéressantes ». Conçus en 1998, ils s’appuient sur les travaux d’Okamoto et Uchiyama, présentés un an auparavant.

C’était le début d’une nouvelle aventure : « On a commencé à dire qu'on voulait faire des choses avec, en particulier […] en traitement de signal. Il y a une communauté de recherche qui s'est structurée autour du traitement du signal dans le domaine chiffré ».

À cette époque, « le consensus dans la communauté crypto était que le chiffrement homomorphe – qui a à la fois les bonnes propriétés de sécurité et qui fasse un bon compromis au niveau du surcoût de calcul – c'était quelque chose qui n'existait pas ». Il faudra encore attendre une dizaine d’années pour que les choses bougent avec un cryptosystème « complet ».

La « révolution » date d’il y a 10 ans

C’est aux alentours des années 2010 que la situation a évolué, avec les travaux de Craig Gentry. Ce chercheur (qui avait alors 37 ans) « un peu contre toute attente, a réussi à faire une première construction crédible d’un cryptosystème avec sécurité prouvée d’un côté, et avec d’un autre côté des opérateurs de calculs efficaces pour un théoricien ».

Ce dernier point est très important et mérite de s’y attarder quelques instants. Pour simplifier, cela veut dire que pour un système lambda, « le surcoût pour faire des opérations homomorphes est un polynôme de lambda ». Cette étape est un aboutissement pour la partie théorique et donc le début d’une nouvelle aventure pratique : « c’est un polynôme, moi j’ai fini mon boulot, c'est efficace, c'est la définition de l'efficacité pour les théoriciens », nous sous-titre Renaud Sirdey.

En revanche, le directeur de recherche du CEA ajoute qu'en pratique, c’est parfois (souvent ?) plus compliqué : « Si le polynôme à un degré supérieur à trois, voire quatre ça ne sert pas à grand-chose ». Le coût sera toujours trop important pour l’utiliser concrètement.

« Les premières constructions crédibles des systèmes de chiffrement homomorphe étaient un peu de cet acabit, c’est-à-dire : théoriquement satisfaisant, mais induisant un surcoût pratique beaucoup trop élevé ». Craig Gentry avait donc entrouvert la porte, d’autres s’y sont depuis engouffrés.

…la course est lancée

Ce changement de paradigme était important, car il a joué le rôle de catalyseur pour la communauté scientifique : « C'est à partir de ce moment-là, il y a une dizaine d’années, qu’une solution théorique au problème du chiffrement homomorphe a commencé à être envisageable ».

Avec le cryptosystème de Craig Gentry, on voit davantage « les implications de cette percée théorique ». « Les conséquences étaient telles, que plusieurs équipes se sont lancées en essayant de transformer la théorie en pratique ».

C’est à cette période que la communauté de recherche s’est un peu structurée, « ce qui a permis d'en améliorer fortement les performances, sachant que pour les chiffrements homomorphes, c'est un peu un problème multifacette », touchant à plusieurs domaines de recherche.

Renaud Sirdey en profite pour remettre en contexte le chiffrement homomorphe par rapport à son idée d'origine, 50 ans avant : « Quand on écrit un papier à la fin des années 70 et qu‘on n’a pas encore le cloud ni toute cette informatique qui se dématérialise complètement, la pertinence ou les enjeux se voient un peu moins ».

Aujourd’hui, on imagine bien l’intérêt d’envoyer des données chiffrées sur un service en ligne, puis d’y lancer des calculs homomorphes et récupérer le résultat, sans compromettre la confidentialité des données durant ces étapes. Avec les questions de souveraineté, cette approche « zero trust » (c’est-à-dire qu’on n’accorde aucune confiance à l’hébergeur) prend encore plus d’intérêt. 

« Je pense que Gentry – ça n'engage que moi – ferait un bon prix Turing [parfois considéré comme équivalent au Nobel en informatique, ndlr] d’ici quelques années », ajoute Renaud Sirdey. Craig Gentry a déjà reçu plusieurs prix pour ses travaux, dont celui de l’ACM (Association for Computing Machinery), de Grace Murray Hopper et de MacArthur.

RSA ou AES en version homomorphe ? Non !

De nos jours, le chiffrement homomorphe se développe avec des cryptosystèmes spécialement conçus, mais nous avons demandé à Renaud Sirdey si l'on pouvait l’utiliser sur un existant.

La réponse est non : « On ne peut pas doter RSA ou un système symétrique AES d’opérateurs homomorphes. Il se trouve que RSA est un peu particulier, car dans sa version déterministe – très peu utilisée car assez faible –, il est homomorphe pour la multiplication ». Il ne lui manquerait donc que l’addition afin d’avoir un ensemble « universel ».

« Il faut quand même des structures mathématiques très particulières au niveau du cryptosystème pour permettre l'existence de ces opérateurs homomorphes », ajoute le chercheur. « Je ne peux pas partir d’un cryptosystème quelconque de mon choix et dire maintenant, je vais le doter – ou lui bricoler – des opérateurs homomorphes, ça ne va pas marcher ».

Le chiffrement homomorphe induit un surcoût important

Comme nous l’avons déjà expliqué, le passage à un cryptosystème homomorphe n’est pas anodin, même de nos jours : « Le surcoût [en puissance de calcul] est toujours extrêmement élevé, c'est-à-dire de plusieurs ordres de grandeur. Si vous voulez mettre un chiffre, vous pouvez dire que ça coûte 10 000 fois «  plus cher  » de faire une opération dans le domaine chiffré, en comparaison d'une simple addition ou multiplication qui ne mobilise qu’une seule instruction dans un processeur quand elle travaille sur les données en clair ».

Comparer un calcul basique sur des données en clair à sa variante chiffrée revient à troquer une simple instruction de processeur (addition ou multiplication) contre un opérateur mathématique complexe : « On sent bien que, quoi qu'il arrive, on va avoir un surcoût important »…

Cependant, pour le chercheur, il ne faut pas forcément raisonner en termes de surcoût – qui est obligatoire –, mais prendre le problème dans l’autre sens : « moi, j'ai besoin de rendre un service, par exemple faire se rencontrer un algorithme avec des données, mais aujourd'hui, je ne peux pas le faire, car je ne souhaite pas dévoiler les données et/ou l’algorithme ». Le chiffrement homomorphe est alors une solution pour « résoudre des situations de blocage ».

« On ne le fait pas pour le plaisir »

Renaud Sirdey met les points sur les « i » : « le but n'est pas – et ne sera probablement jamais – de dire : "aller hop maintenant, on ne se pose pas de question", le cloud va se mettre à travailler de manière totalement indifférenciée sur n'importe quel type de données dans le domaine chiffré ». Le chiffrement homomorphe coûte cher et ça continuera à l’avenir : « on ne le fait pas pour le plaisir ».

Pour le chercheur du CEA, on est actuellement à une période de bascule : « Aujourd'hui, je dirais qu’on est encore un tout petit peu en amont » du lancement de la cryptographie homomorphe par des géants du cloud. « Il n'y a pas encore – à ma connaissance – de service complètement opérationnel et commercial qui utilise aujourd'hui du chiffrement homomorphe […] Par contre, c’est quelque chose qui est sur le point d'arriver ».

Il y a aussi évidemment de grands groupes comme Microsoft « qui sont très actifs aussi dans le développement de logiciels et même de logiciels open source pour faire de la crypto homomorphe, et qui sont sur le point de fournir, par exemple dans Azure, des API de calcul homomorphe ». Il suffit « juste attendre que ça arrive »… mais en gardant bien à l’esprit que « ça ne va pas arriver – c'est vraiment ça le message important – de manière universelle ».

Dans le monde et notamment en France, de nombreuses sociétés et start-ups travaillent sur ce sujet. C’est notamment le cas de Cosmian avec qui nous avons pu échanger, comme nous le verrons dans un prochain article.

Cet article a initialement été publié dans le magazine #3 de Next INpact distribué début 2022. Il est pour le moment réservé à nos abonnés et sera ensuite accessible à tous, comme l'ensemble de nos contenus. Nos magazines sont disponibles à la vente au sein de notre boutique en ligne.