Cryptographie!

Le chiffrement homomorphe

Pourquoi le chiffrement homomorphe?
  L'heure est à l'externalisation des données. C'est le cloud computing, qui permet de mutualiser les structures de conservation et de traitement des données. L'un des problèmes de ceci est la préservation de la confidentialité entre le client et le fournisseur. Certes, la cryptographie usuelle peut répondre en partie à ce problème, puisque le client peut décider de ne stocker que des données chiffrées.

  Mais ceci n'est pas réaliste… Comment faire par exemple, si vous voulez effectuer une recherche dans vos données? Impossible, normalement, de le faire directement sur les données chiffrées! Sauf si votre système de chiffrement dispose de la propriété suivante : les algorithmes de traitement de données passent à travers la couche de chiffrement. Autrement dit, si le client veut effectuer certains calculs sur ces données, il suffit qu'il demande au fournisseur d'effectuer ces calculs sur les données chiffrées, le fournisseur transmet le résultat (qui est chiffré), le client le déchiffre et il obtient le résultat voulu (en clair). On appelle ces chiffrements des chiffrements homomorphes.
Chiffrement homomorphe additif, multiplicatif et chiffrement complètement homomorphe
  En général, les messages clairs comme chiffrés sont représentés sous forme de nombres. Les traitements que l'on applique à ces nombres sont des additions et des multiplications. On a donc besoin d'un algorithme de chiffrement $C_K$ de clé $K$, dont l'algorithme de déchiffrement est $D_K$, tel que l'on puisse faire ces opérations aussi bien sur les données en clair que sur les données chiffrées, sans que cela ne change le résultat. Il doit donc vérifier les propriétés suivantes : $$D_K(C_K(n)+C_K(m))=n+m$$ $$D_L(C_k(n)\times C_K(m) )=n\times m.$$ La première propriété s'appelle l'homomorphie additive, et la seconde l'homomorphie multiplicative. Un algorithme est complètement homomorphe si les deux propriétés sont vérifiées simultanément.

  Il est assez facile de trouver un tel algorithme. Imaginons par exemple que notre algorithme de chiffrement soit la multiplication par $2$, $C_K(n)=2n$, d'algorithme de déchiffrement $D_K(n)=n/2$. L'homomorphie additive est facile à vérifier, car $$C_K(n)+C_K(m)=2n+2m=2(n+m).$$ L'homomorphie multiplicative ne peut pas être vérifiée directement. Il faut d'abord décider d'une règle pour la multiplication des données chiffrées. On décide que $$n\otimes m =\frac{n\times m}2$$ si $n$ et $m$ sont deux données chiffrées. Mais alors, avec cette règle $$C_K(n)\otimes C_K(m)=\frac{2n\times 2m}2=2(n\times m)$$ et donc $$D_K(C_K(n)\otimes C_K(m) )=n\times m.$$ $C_K$ est donc un algorithme de chiffrement homomorphe, pourvu qu'on change la règle de multiplication des données chiffrées (en réalité, on s'autorise aussi à changer la règle d'addition).

  Mais bien sûr la multiplication par deux est un très mauvais algorithme de chiffrement qui n'assure pas du tout la sécurité! Dès 1978, Rivest, Adleman et Dertouzos avaient conjecturé l'existence d'un algorithme de chiffrement (sûr!) complètement homomorphe. En réalité, on connaissait déjà des algorithmes de chiffrement additivement homomorphe ou multiplicativement homomorphe. C'est le cas par exemple de RSA. Si $(n,e)$ est la clé publique de RSA et $(n,d)$ est la clé privée, l'algorithme de chiffrement est $C(M)=M^e\ (\!\!\!\!\mod n)$ et l'algorithme de déchiffrement est $D(M)=M^d\ (\!\!\!\!\mod n)$. On a bien $$C(M_1)\times C(M_2)=M_1^e\times M_2^2=(M_1M_2)^e\ (\!\!\!\!\mod n)=C(M_1\times M_2).$$ Cependant, cette propriété est aussi une faiblesse de RSA lorsque ce système est mal utilisé.

  D'autres algorithmes de chiffrement homomorphe multiplicatif (comme El-Gamal) ou additif (comme le cryptosystème de Pailler) existent. Cependant, ce n'est qu'en 2009 que Craig Gentry, alors doctorant à l'université de Stanford, inventa le premier chiffrement complètement homomorphe. Cette découverte ne peut pour le moment pas être mise en pratique, car elle impose des clés très longues (dans la première implémentation du système de Gentry, elle faisait plus de 2 Gigabits, à comparer aux 256 bits utilisés dans l'AES par exemple!), des données chiffrées prenant beaucoup plus de place que les données en clair, et les algorithmes de traitement de données sont encore très lents. Mais un cap théorique a été franchi, et le chiffrement homomorphe est clairement un challenge pour les cryptologues d'aujourd'hui et de demain.
Un protocole : le retrait d'informations privé
  Terminons cette page par une application déjà utilisable en pratique des chiffrements homomorphes additifs : le retrait d'informations privé (sans fautes d'orthographe : c'est le retrait qui est privé). Le contexte est le suivant. On dispose d'une grande base de données que l'on souhaite interroger de façon privée : on ne veut pas que le possesseur de la base de données sache à quel élément de cette base on s'intéresse. Ce peut être le cas par exemple d'un investisseur abonné à un service d'informations financières, et qui ne désire pas révéler à quelles sociétés il s'intéresse.

  On suppose que la base de données est organisée de la façon suivante : chaque entrée est indexée par un entier unique, on les note $I_1,\dots,I_d$. Les entrées de la base de données ne sont pas supposés chiffrées, ce sont simplement des nombres entiers. On souhaite obtenir l'élément $I_k$ sans que le possesseur de la base de données ne le sache. Voici comment procéder. On suppose qu'on dispose d'un cryptosystème additivement homomorphe $C_K$. Il vérifie $$C_K(n+m)=C_K(n)+C_K(m),$$ et donc également $$C_K(2n)=C_K(n)+C_K(n)=2C_K(n).$$ Par extension, pour tous les entiers $n_1,\dots,n_d$ et $a_1,\dots,a_d$, on a : $$C_K(a_1n_1+\dots+a_dn_d)=a_1C_K(n_1)+\dots+a_dC_K(n_d).$$   L'utilisateur commence par calculer des chiffrés $m_i$, où $m_i$ est un chiffré de 0 sauf pour $i=k$. Dans ce cas, $m_k$ est un chiffré de $1$. On suppose que notre système de chiffrement est randomisé, et donc que tous les $m_i$ sont différents (0 peut être chiffré de plusieurs façons différentes). L'utilisateur envoie alors à l'administrateur de la base de données la requête $(m_1,\dots,m_d)$. Il n'a aucun moyen de savoir quel est celui des $m_i$ qui correspond à $1$. Il calcule alors $I_1m_1+\dots+I_dm_d$, et il renvoie ce résultat au client. Celui calcule alors $D_K(I_1m_1+\dots+I_dm_d)$ et récupère $I_k$. En effet, on a $$I_1m_1+\dots+I_dm_d=I_1C_K(0)+\dots+I_kC_k(1)+\dots+I_dC_K(0)=C_K(I_1\times 0+\dots+I_k\times 1+\dots+I_d\times 0)=C_K(I_k).$$

Consulter aussi