Wiki du cours

Rédacteur: [Cyprien Rivier]

A traiter [Modifier]

Suivre principalement [1]

• Chiffrement homomorphe additif utilisant le cryptosystème d'ElGamal.
• Chiffrement homomorphe de Boneh-Goh-Nissim.

Chiffrement homomorphe [Modifier]

Dans cet article nous allons considérer exclusivement des algorithmes de cryptage sur les courbes elliptiques. Soit \( (G,E,D) \) un chiffrement à clé symétrique ou asymétrique. Un message \(m \in M\) avec \(M\) l'espace des messages est donc envoyé sur : \(E(m)=c\), \(c \in C\) avec \(C\) l'espace des cryptogrammes.
Ce chiffrement est dit homomorphe si \(E\) est un homomorphisme de groupes entre \(M\) et \(C\).
Nous allons maintenant montrer en quoi ElGamal est un chiffrement (asymétrique) homomorphe pour l'addition.

Rappel sur ElGamal

Rappelons la définition du chiffrement d'ElGamal.

• \(Gen()\) : l'algorithme de création de clé consiste à :
  • Choisir une courbe elliptique \(E\) sur un corps fini \(\mathbb{F}_{p}\).
  • Choisir un point \(P \in E\) tel que son ordre soit égal à \(n\) un nombre premier. (\(nP=\infty\))
  • Fixer un entier \(s\) choisi aléatoirement dans l'intervalle \( [1,n]\).
  • On obtient la clé publique \(pk = (P, Q=sP)\) ainsi que la clé privée \(sk = s\).
• \(E(pk,M)\) avec \(M \in E(\mathbb{F}_{p})\): l'algorithme d'encodage consiste à :
  • Fixer un entier \(r\) choisi aléatoirement dans l'intervalle \( [1,n]\).
  • Renvoyer la paire de points \(C=(rP, M+rQ)\).
• \(D(C,sk)\) avec \(C=(C_1,C_2)\): l'algorithme de déchiffrement consiste à renvoyer \(M'=C_2-sC_1\)

ElGamal est un chiffrement homomorphe additif

Soient 2 messages \(M, M' \in E(\mathbb{F}_{p})\). Leurs cryptogrammes respectifs sont :
\(C= E(pk,M) = (rP, M+rQ) \) et
\(C'= E(pk,M') = (r'P, M'+r'Q) \)
On remarque que \(E(pk,M)+E(pk,M')= C+C' = (rP+r'P, M+rQ+M'+rQ) = ((r+r')P, (M+M')+(r+r')Q) = E(pk,M+M') \). Cela montre bien que \(C+C'\) est bien un cryptogramme de \(M+M'\) et que \(E\) est un homomorphisme additif de groupe.

Un chiffrement complètement homomorphe est un chiffrement qui est homomorphe pour l'addition et la multiplication. ElGamal est uniquement homomorphe pour l'addition et n'est donc pas complètement homomorphe. Le grand avantage d'un chiffrement complètement homomorphe serait de pouvoir effectuer des opérations arbitraires sur les cryptogrammes tout en gardant le résultat secret. Cela permettrait par exemple de déléguer à une tierce personne des calculs à effectuer sans que cette personne n'ait accès à nos données.
Nous allons maintenant présenter le système BGN pour Boneh, Goh et Nissim qui est proche d'être complètement homomorphe.

Le système BGN [Modifier]

Le système ElGamal considérait des courbes \(E(\mathbb{F}_{p})\) où \(p\) est un nombre premier. Le système BGN se base quant à lui sur des courbes elliptiques \(E(\mathbb{F}_{n})\) où \(n\) est un nombre non premier qui est très difficile à factoriser.
Le système BGN se définit de la manière suivante :

• \(Gen()\) : l'algorithme de création de clé consiste à :
  • Choisir \(q\) et \(r\) des grands nombres premiers et les garder secrets. Poser \(n=qr\).
  • Construire une courbe elliptique supersingulière \(E(\mathbb{F}_{p})\) contenant un point \(P\) d'ordre \(n\). Poser \(\mathbb{G}=\langle P \rangle\).
    • Pour ce faire : commencer par choisir un petit entier \(l\) tel que \(4ln-1\) soit un nombre premier. Poser \(p=4ln-1\).
    • Considérer la courbe elliptique \(E:y^2=x^3+x\) sur \(\mathbb{F}_{p}\). Cette courbe est supersingulière de cardinal \(p+1=4ln\) car \(p=3 (\)mod \(4)\).
    • Choisir un point aléatoire \(P' \in E(\mathbb{F}_{p})\). On pose \(P=4lP'\) et on obtient que \(P\) est d'ordre \(n\).
  • Choisir aléatoirement dans \(\mathbb{G}\setminus\infty\) un point \(Q'\). Poser \(Q=rQ'\), \(Q\) est bien d'ordre \(q\). (Il y a une petite probabilité pour que \(Q\) soit d'ordre \(\infty\) et dans ce cas on recommence depuis le début.)
  • Construire le couplage de Weil modifié \(ê: \mathbb{G}\times \mathbb{G} \rightarrow µ_n \subset \mathbb{F}_{p^2}\).
  • Publier la clé publique \(pk= (E, ê, n, P, Q)\) et garder secrète la clé \(sk= q\).
• \(E(pk,m)\) : Choisir aléatoirement \(t\) dans l'intervalle \([1,n]\). Obtenir \(C=mP+tQ\).
• \(D(sk,C)\) : Calculer \(\tilde{P}=qP\) et \(\tilde{C}=qC\). Obtenir \(m'=\log_\tilde{P} \tilde{C}\).
  • Le déchiffrement fonctionne car si \(C=mP+tQ\), alors \(\tilde{C}=qmP+qtQ=qmP=m\tilde{P}\).
  • Il faut noter que l'on calcule ici un logarithme discret, ce qui, comme nous l'avons vu, peut s'avérer très difficile à faire. Il est donc nécessaire de se restreindre à des entiers raisonnablement petits afin de pouvoir les résoudre par force brute.

L'addition

On définit l'addition dans le système BGN comme suit :

• \(Add(pk,C_1,C_2)\) : Choisir aléatoirement \(t'\) dans l'intervalle \([1,n]\) et calculer \(C'=C_1+C_2+t'Q \in \mathbb{G}\).
  On vérifie aisément que si \(C_1\) est un cryptogramme de \(m_1\) et \(C_2\) un cryptogramme de \(m_2\), \(C_1+C_2\) est un cryptogramme de \(m_1+m_2\) et BGN est donc homomorphe pour l'addition.

On dit \(\textit{un}\) et non \(\textit{le}\) cryptogramme car il y en a \(q\) possibles pour un message donné de part l'étape de randomisation.

La multiplication

On ne peut pas effectuer n'importe quelle multiplication dans EBG (sinon on aurait trouvé un système complètement homomorphe), mais on peut en effectuer une :

• \(Mult(pk,C_1,C_2)\) : Choisir aléatoirement \(u\) dans l'intervalle \([1,n]\) et calculer \(D=ê(C_1,C_2) \cdot ê(Q,Q)^u \in µ_n\).
  En remplaçant \((C_1,C_2)\) on obtient \(D=ê(m_1P+t_1Q,m_2P+t_2Q)\cdot ê(Q,Q)^u = ê(P,P)^{m_1m_2}\cdot ê(P,Q)^{m_1t_2+m_2t_1}\cdot ê(Q,Q)^{t_1t_2+u}\).
  

Nous pouvons simplifier cette expression en utilisant que :

1. Le couplage de Weil satisfait la propriété de non-dégénérescence et donc \(g=ê(P,P)\) est un élément de \(\mathbb{F_p^2}\) d'ordre \(n\).
   
2. De la même façon \(h=ê(Q,Q)\) est un élément de \(\mathbb{F_p^2}\) d'ordre \(q\).
   
3. \(ê(P,Q)^q=ê(P,qQ)=1\), ce qui implique que \(ê(P,Q)\) est d'ordre \(q\) et \(ê(P,Q)=h^a\) pour un certain \(a\).
   

Par conséquent, \(D=Mult(pk,C_1,C_2)=g^{m_1m_2}h^{u'}\) pour un certain entier \(u'\).

Remarque :
Il est important d'avoir à l'esprit que cette multiplication envoie 2 cryptogrammes \((C_1,C_2)\in C\) sur un autre cryptogramme \(D\in µ_n\). Il y a donc 2 espaces de cryptogrammes : \(C\) des points sur la courbe elliptique et \(µ_n\) le groupe cyclique des racines n-ièmes de l'unité de \(\mathbb{F}_{p^2}\).

Déchiffrement de la multiplication
Si l'on s'intéresse maintenant à déchiffrer \(D\) le résultat de la multiplication pour trouver le message \(m\) correspondant, on peut utiliser le fait que \(h\) est d'ordre \(q\) :

• \(Dec'(sk,D)\) : Calculer \(\tilde{g}=g^q\), \(\tilde{D}=D^q\), puis renvoyer \(log_\tilde{g} \tilde{D}\).
  

Addition dans l'espace \(µ_n\)
On a également la possibilité d'additionner des éléments \((D_1,D_2)\) de \(µ_n\) :

• \(Add'(pk,D_1,D_2)\) : Choisir aléatoirement \(u\) dans l'intervalle \([1,n]\) et renvoyer \(D'=D_1 \cdot D_2 \cdot h^u\).
  

Remarque :
Si l'on souhaite envoyer directement un message \(m\) dans l'espace \(µ_n\) sans passer par la fonction \(Enc()\) et l'espace \(C\), on peut faire \(m \to g^mh^u\).

Comme on vient de le voir, les ensembles de départ et d'arrivée de cette multiplication ne sont pas les mêmes. On ne pourrait donc pas répéter cette multiplication avec \((D_1,D_2)\) des résultats de cette multiplication. Si l'on considère les cryptogrammes sur \(C\) comme des variables, cette multiplication (combinée avec \(Add()\) et \(Add'()\)) ne permet d'obtenir que des expressions de degré 2. Elle est donc incomplète, raison pour laquelle BGN n'est pas parfaitement homomorphe.

Note

Un chiffrement complètement homomorphe a été découvert à Stanford en 2009 par Craig Gentry.

Références [Modifier]

[1] David Mandell Freeman, Homomorphic Encryption and the BGN Cryptosystem
[2] Dan Boneh, Eu-Jin Goh, Kobbi Nissim, Evaluating 2-DNF formulas on ciphertexts