Cryptosystème homomorphe de Naccache-Stern

Modèle:Ne pas confondre

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^[1]. La sécurité sémantique de ce cryptosystème repose sur le problème de la résiduosité supérieure^[2], 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^[3], lui-même une extension de celui de Goldwasser-Micali^[4], 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^{λ}$ et retourne un couple de clés obtenues de la manière suivante^{[Note 1]}Modèle:,^[5] :

Deux ensembles de nombres premiers^{[Note 2]} $p_{1}, \dots, p_{k}$ et $q_{1}, \dots, q_{k}$ sont choisis, tous distincts. Le nombre $k$ est déterminé par l'algorithme en fonction de $λ$ , 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 = 2 a u + 1$ et $q = 2 b v + 1$ soient simultanément premiers.
Le produit $n = p q$ et calculé, et un élément $g \in ℤ / n ℤ$ d'ordre $φ (n) / 4$ est choisi, où $φ$ est la fonction d'Euler^{[Note 3]}.

La clé publique est alors définie comme $𝗉 𝗄 = {g, n, σ = u v}$ et la clé privée correspondante est donnée par $𝗌 𝗄 = 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^[1].

Chiffrement

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

Déchiffrement

L'algorithme de déchiffrement prend en entrée un chiffré $c \in ℤ / n ℤ$ et la clé privée $𝗌 𝗄$ . On calcule alors pour chaque $i, j = 1, \dots, k$ $\begin{matrix} c_{i} & = c^{φ (n) / p_{i}} mod n \\ c_{j} & = c^{φ (n) / q_{j}} mod n \end{matrix}$ On peut écrire ces équations en prenant pour base le générateur $g$ , à savoir $\begin{matrix} c_{i} & = g^{u_{i}} mod n \\ c_{j} & = g^{v_{j}} mod n \end{matrix}$ Pour un message chiffré, on a $u_{i} = m_{i} φ (n) / p_{i}$ (resp. $v_{j} = m_{j} φ (n) / q_{j}$ ) où $m_{i} = m {mod p}_{i}$ (resp. $m_{j} = m {mod 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 ℤ / σ ℤ$ , $\begin{matrix} E (m_{1}) & = x_{1}^{σ} g^{m_{1}} mod n \\ E (m_{2}) & = x_{2}^{σ} g^{m_{2}} mod n \end{matrix}$ de sorte que $\begin{matrix} E (m_{1}) E (m_{2}) & = x_{1}^{σ} g^{m_{1}} x_{2}^{σ} g^{m_{2}} mod n \\ = (x_{1} x_{2})^{σ} g^{m_{1} + m_{2}} mod n \end{matrix}$ 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^[2]. En réalité on peut montrer qu'il repose sur une hypothèse légèrement moins forte de résiduosité des premiers choisis^[4]. 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.

Notes et références

Notes

↑ Nous suivons ici pour l'essentiel la description de la « version probabiliste » décrite dans (Naccache et Stern 1998), qui est le cas général et qui est la seule capable de sécurité sémantique.
↑ (Naccache et Stern 1998) observent qu'il n'est pas nécessaire que les nombres soient premiers : il suffit qu'ils soient premiers entre eux. Le choix de nombres premiers a le mérite de faciliter l'analyse.
↑ Lorsque les $p_{i}, q_{i}$ sont les $2 k$ plus petits nombres premiers, le théorème des nombres premiers permet d'estimer la probabilité qu'un élément $g$ pris au hasard convienne à environ $1 / \ln 2 k$ .
↑ Si le nombre $x$ est fixé, ce qui correspond à la « version déterministe » de (Naccache et Stern 1998), on n'a plus de sécurité sémantique : le cryptosystème est mieux décrit comme une fonction à trappe.

Références

Modèle:Portail

[5] Nous suivons ici pour l'essentiel la description de la « version probabiliste » décrite dans (Naccache et Stern 1998), qui est le cas général et qui est la seule capable de sécurité sémantique.

[7] (Naccache et Stern 1998) observent qu'il n'est pas nécessaire que les nombres soient premiers : il suffit qu'ils soient premiers entre eux. Le choix de nombres premiers a le mérite de faciliter l'analyse.

[8] Lorsque les $p_{i}, q_{i}$ sont les $2 k$ plus petits nombres premiers, le théorème des nombres premiers permet d'estimer la probabilité qu'un élément $g$ pris au hasard convienne à environ $1 / \ln 2 k$ .

[9] Si le nombre $x$ est fixé, ce qui correspond à la « version déterministe » de (Naccache et Stern 1998), on n'a plus de sécurité sémantique : le cryptosystème est mieux décrit comme une fonction à trappe.

[:0-1] 1,0 et ^1,1 Modèle:Article

[:1-2] 2,0 et ^2,1 Modèle:Chapitre

[3] Modèle:Article

[:2-4] 4,0 et ^4,1 Modèle:Article

[6] Modèle:Ouvrage

[1]

[2]

[3]

[4]

[Note 1]

[5]

[Note 2]

[Note 3]

[Note 4]

Cryptosystème homomorphe de Naccache-Stern

Sommaire

Description

Génération de clés

Chiffrement

Déchiffrement

Homomorphisme additif

Sécurité

Notes et références

Notes

Références

Menu de navigation

Cryptosystème homomorphe de Naccache-Stern

Description

Génération de clés

Chiffrement

Déchiffrement

Homomorphisme additif

Sécurité

Notes et références

Notes

Références

Menu de navigation

Rechercher