Cryptosystème homomorphe de Naccache-Stern

L'algorithme de génération de clé prend en entrée un paramètre de sécurité ${\displaystyle 1^{\lambda }}$ et retourne un couple de clés obtenues de la manière suivante[Note 1] - [5] :

• Deux ensembles de nombres premiers[Note 2] ${\displaystyle p_{1},\dotsc ,p_{k}}$ et ${\displaystyle q_{1},\dotsc ,q_{k}}$ sont choisis, tous distincts. Le nombre ${\displaystyle k}$ est déterminé par l'algorithme en fonction de ${\displaystyle \lambda }$, et les premiers sont choisis « petits », en un sens précisé plus tard.
• Le produit des ${\displaystyle p_{i}}$ (resp. des ${\displaystyle q_{i}}$) est calculé et noté ${\displaystyle u}$ (resp. ${\displaystyle v}$)
• Deux grands premiers ${\displaystyle a,b}$ sont alors choisis de sorte que ${\displaystyle p=2au+1}$ et ${\displaystyle q=2bv+1}$ soient simultanément premiers.
• Le produit ${\displaystyle n=pq}$ et calculé, et un élément ${\displaystyle g\in \mathbb {Z} /n\mathbb {Z} }$ d'ordre ${\displaystyle \varphi (n)/4}$ est choisi, où ${\displaystyle \varphi }$ est la fonction d'Euler[Note 3].

La clé publique est alors définie comme ${\displaystyle {\mathsf {pk}}=\{g,n,\sigma =uv\}}$ et la clé privée correspondante est donnée par ${\displaystyle {\mathsf {sk}}=p}$ (ou ${\displaystyle q}$, ce qui est équivalent).

Les nombreux tests de primalité intervenant lors de la génération de clés sont relativement coûteux, mais peuvent être en partie absorbés par une implémentation appropriée[1].

L'algorithme de chiffrement prend en entrée un message ${\displaystyle m\in \mathbb {Z} /\sigma \mathbb {Z} }$ et la clé publique ${\displaystyle {\mathsf {pk}}}$. Un élément aléatoire ${\displaystyle x\in \mathbb {Z} /n\mathbb {Z} }$ est choisi[Note 4], puis le chiffré est obtenu en calculant ${\displaystyle E(m)=x^{\sigma }g^{m}{\bmod {n}}}$.

L'algorithme de déchiffrement prend en entrée un chiffré ${\displaystyle c\in \mathbb {Z} /n\mathbb {Z} }$ et la clé privée ${\displaystyle {\mathsf {sk}}}$. On calcule alors pour chaque ${\displaystyle i,j=1,\dotsc ,k}$

$${\displaystyle {\begin{aligned}c_{i}&=c^{\varphi (n)/p_{i}}{\bmod {n}}\\c_{j}&=c^{\varphi (n)/q_{j}}{\bmod {n}}\end{aligned}}}$$

On peut écrire ces équations en prenant pour base le générateur ${\displaystyle g}$, à savoir

$${\displaystyle {\begin{aligned}c_{i}&=g^{u_{i}}{\bmod {n}}\\c_{j}&=g^{v_{j}}{\bmod {n}}\end{aligned}}}$$

Pour un message chiffré, on a ${\displaystyle u_{i}=m_{i}\varphi (n)/p_{i}}$ (resp. ${\displaystyle v_{j}=m_{j}\varphi (n)/q_{j}}$) où ${\displaystyle m_{i}=m{\bmod {p}}_{i}}$ (resp. ${\displaystyle m_{j}=m{\bmod {p}}_{j}}$). En résolvant un logarithme discret modulo ${\displaystyle n}$on obtient alors ${\displaystyle m_{i},m_{j}}$ ce qui permet via le théorème chinois des restes de retrouver ${\displaystyle m}$. Résoudre le logarithme discret est en général considéré difficile : c'est pourquoi les premiers ${\displaystyle p_{i},q_{j}}$ ont été choisis petits, au sens qu'une recherche exhaustive de ${\displaystyle m_{i},m_{j}}$ est possible.