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. Son principe repose sur des travaux de Okamoto et Uchiyama présentés en 1998.

Le système est un homomorphisme additif; en d'autres termes, avec la clef publique et les chiffrés de $m_{1}$ et $m_{2}$, il est possible de calculer le chiffré de $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 : $p~$ et $q~$;
2. Calculer la clef publique ${\mathsf {pk}}\triangleq N=p\cdot q$ (un module RSA) et la clé privée ${\mathsf {sk}}\triangleq \varphi (N)=(p-1)\cdot (q-1)~$.

Chiffrement

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

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

Déchiffrement

Pour retrouver le texte clair $m$, on commence par remarquer que :

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

car

${\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 :

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

D’où :

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

On remarque que le calcul de $r$ n'est possible qu’à l'aide de la clef privée ${\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é $c_{1}={\mathsf {Chiffrer}}(m_{1})$ et un chiffré $c_{2}={\mathsf {Chiffrer}}(m_{2})$, il est possible de construire un chiffré $c_{1+2}={\mathsf {Chiffrer}}(m_{1}+m_{2})$ sans connaître ni $m_{1}$ ni $m_{2}$.

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

${\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 $m_{1}+m_{2}$ sous l'aléa $r_{1}\cdot r_{2}$.

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