Cryptosystème homomorphe de Naccache-Stern

En cryptologie, le cryptosystème homomorphe de Naccache-Stern est un chiffrement à clé publique introduit en 1998 par les cryptologues David Naccache et Jacques Stern. La sécurité sémantique de ce cryptosystème repose sur le problème de la résiduosité supérieure, et il s'agit d'un système de chiffrement additivement homomorphe.

D'un point de vue historique, le cryptosystème de Naccache-Stern est une amélioration du cryptosystème de Benaloh-Fischer, lui-même une extension de celui de Goldwasser-Micali, dans une succession d'améliorations de bande passante de chiffrements homomorphes.

Description

Le cryptosystème s'appuie sur trois algorithmes $(G,E,D)$ correspondant respectivement à la génération de clés, au chiffrement, et au déchiffrement.

Génération de clés

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

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

La clé publique est alors définie comme ${\mathsf {pk}}=\{g,n,\sigma =uv\}$ et la clé privée correspondante est donnée par ${\mathsf {sk}}=p$ (ou $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.

Chiffrement

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

Déchiffrement

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

$${\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 $g$, à savoir

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

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

Homomorphisme additif

Le cryptosystème de Naccache-Stern jouit d'une propriété supplémentaire : il s'agit d'un chiffrement additivement homomorphe. En effet, on a pour tous messages $m_{1},m_{2}\in \mathbb {Z} /\sigma \mathbb {Z}$,

$${\begin{aligned}E(m_{1})&=x_{1}^{\sigma }g^{m_{1}}{\bmod {n}}\\E(m_{2})&=x_{2}^{\sigma }g^{m_{2}}{\bmod {n}}\end{aligned}}$$

de sorte que

$${\begin{aligned}E(m_{1})E(m_{2})&=x_{1}^{\sigma }g^{m_{1}}x_{2}^{\sigma }g^{m_{2}}{\bmod {n}}\\&=(x_{1}x_{2})^{\sigma }g^{m_{1}+m_{2}}{\bmod {n}}\end{aligned}}$$

qui se déchiffre en $m_{1}+m_{2}$. Contrairement au cryptosystème de Paillier, également additivement homomorphe, l'intérêt de la construction de Naccache-Stern est sa bande passante : on travaille modulo $n$ et non pas modulo $n^{2}$ comme Paillier.

Sécurité

Le cryptosystème de Naccache-Stern est sémantiquement sûr (IND-CPA) sous l'hypothèse de la difficulté du problème de la résiduosité supérieure. En réalité on peut montrer qu'il repose sur une hypothèse légèrement moins forte de résiduosité des premiers choisis. Dans un cas comme dans l'autre, la meilleure approche connue (en 2018) pour résoudre ces problèmes est d'obtenir une factorisation de $n$. Les meilleurs algorithmes classiques connus (i.e., GNFS et ses variantes) permettent alors de fixer les paramètres pour viser un niveau de sécurité donné.

En revanche, s'agissant d'un chiffrement homomorphe, ce cryptosystème est malléable et ne peut donc pas prétendre aux notions plus fortes de sécurité (IND-CCA notamment).

De plus, on connait pour le problème de la factorisation un algorithme quantique efficace : l'algorithme de Shor. Le cryptosystème de Naccache-Stern n'est donc pas un candidat post-quantique.