Cryptosystème de Paillier

Le cryptosystème de Paillier est un cryptosystème basé sur un algorithme asymétrique conçu par Pascal Paillier en 1999^[1]. Son principe repose sur des travaux de Okamoto et Uchiyama présentés en 1998^[2].

Le système est un homomorphisme additif; en d'autres termes, avec la clef publique et les chiffrés de ${\displaystyle m_{1}}$ et ${\displaystyle m_{2}}$, il est possible de calculer le chiffré de ${\displaystyle m_{1}+m_{2}}$. Comme de plus ce chiffrement est prouvé sûr face à un attaquant passif, les chiffrés sont indistinguables, ce qui permet de remélanger un chiffré en rajoutant un chiffrement de zéro à un chiffré existant. Cette propriété est importante dans de nombreuses constructions visant à préserver la vie privée, étant donné qu'elle rend intraçable un message ainsi remélangé.

Fonctionnement

Génération des clefs

1. Choisir deux nombres premiers de grande taille, indépendants et aléatoires : ${\displaystyle p~}$ et ${\displaystyle q~}$;
2. Calculer la clef publique ${\displaystyle {\mathsf {pk}}\triangleq N=p\cdot q}$ (un module RSA) et la clé privée ${\displaystyle {\mathsf {sk}}\triangleq \varphi (N)=(p-1)\cdot (q-1)~}$.

Chiffrement

Soit ${\displaystyle m~}$ un message à chiffrer avec ${\displaystyle 0\leq m<N~}$. Soit ${\displaystyle r~}$, un entier aléatoire tel que ${\displaystyle 0<r<N~}$ (appelé l'aléa). Le chiffré est alors :

${\displaystyle c=(1+N)^{m}\cdot r^{N}\mod N^{2}}$

Déchiffrement

Pour retrouver le texte clair ${\displaystyle m}$, on commence par remarquer que :

${\displaystyle c\equiv r^{N}\mod N,}$

car

${\displaystyle {\begin{aligned}{\frac {c}{r^{N}}}&=(1+N)^{m}\mod N^{2}\\&=1+m\cdot N+N^{2}\cdot \left(\sum _{i=2}^{m}{\binom {m}{i}}N^{i-2}\right)\mod N^{2}\\&=1+m\cdot N\mod N^{2}.\end{aligned}}}$

On obtient ainsi :

${\displaystyle r=c^{N^{-1}{\bmod {\varphi }}(N)}\mod N.}$

D’où :

${\displaystyle m={\frac {(c\cdot r^{-N}\mod N^{2})-1}{N}}.}$

On remarque que le calcul de ${\displaystyle r}$ n'est possible qu’à l'aide de la clef privée ${\displaystyle {\mathsf {sk}}=\varphi (N)}$, qui reste secrète sous l'hypothèse de la difficulté de la factorisation.

Homomorphisme

Le cryptosystème de Paillier est un homomorphisme additif, c'est-à-dire qu’avec la clef publique, un chiffré ${\displaystyle c_{1}={\mathsf {Chiffrer}}(m_{1})}$ et un chiffré ${\displaystyle c_{2}={\mathsf {Chiffrer}}(m_{2})}$, il est possible de construire un chiffré ${\displaystyle c_{1+2}={\mathsf {Chiffrer}}(m_{1}+m_{2})}$ sans connaître ni ${\displaystyle m_{1}}$ ni ${\displaystyle m_{2}}$^[3].

Cette opération s'effectue en multipliant ${\displaystyle c_{1}}$ et ${\displaystyle c_{2}}$, ce qui mène à:

${\displaystyle {\begin{aligned}c_{1}\cdot c_{2}&=(1+N)^{m_{1}}r_{1}^{N}\cdot (1+N)^{m_{2}}\cdot r_{2}^{N}{\bmod {N}}^{2}\\&=(1+N)^{m_{1}+m_{2}}(r_{1}\cdot r_{2})^{N}{\bmod {N}}^{2}\end{aligned}}}$

Qui correspond à un chiffré de ${\displaystyle m_{1}+m_{2}}$ sous l'aléa ${\displaystyle r_{1}\cdot r_{2}}$.

Notes et références

1. Paillier 1999.
2. Okamoto et Uchiyama 1998.
3. Paillier 1999, Sec. 8. Properties.

Annexes

Bibliographie

• [Okamoto et Uchiyama 1998] (en) Tatsuaki Okamoto et Shigenori Uchiyama, « A new public-key cryptosystem as secure as factoring », Eurocrypt,‎ 1998, p. 308–318 (DOI 10.1007/BFb0054135, lire en ligne)
• [Paillier 1999] (en) Pascal Paillier, « Public-Key Cryptosystems Based on Composite Degree Residuosity Classes », Eurocrypt,‎ 1999, p. 223–238 (DOI 10.1007/3-540-48910-X_16, lire en ligne [PDF])

Articles connexes

• Cryptographie asymétrique
• Chiffrement homomorphe
• Malléabilité

Liens externes

• (en) Paillier's Cryptosystem Revisited
• (en) Extensions to the Paillier Cryptosystem with Applications to Cryptological Protocols

• Portail de la cryptologie