Sac à dos de Naccache-Stern

En cryptologie, le sac à dos de Naccache-Stern est une fonction à trappe introduite en 1997 par les cryptologues David Naccache et Jacques Stern. La sécurité de cette construction repose sur une variante multiplicative du problème du sac à dos, pour laquelle aucun algorithme efficace n'est aujourd'hui connu (en 2018). Cependant, cette construction n'est pas considérée compétitive par rapport à des schémas standard ; son intérêt est ainsi principalement théorique.

Description

On considère trois algorithmes $G,E,D$ définis comme suit.

Génération des paramètres

Soit $p_{i}$ le $i$-ième nombre premier, commençant par $p_{0}=2$. L'algorithme $G$ prend en entrée un paramètre de sécurité $1^{\lambda }$, choisit un entier $n$ et un premier $p$ tel que $$p>\prod _{i=0}^{n}p_{i}.$$ L'algorithme choisit alors un entier $s$ premier avec $p-1$, puis retourne les paramètres publics $p,n$ et les racines $s$-ièmes $v_{i}=p_{i}^{1/s}{\bmod {p}}$ et la trappe, $s$ .

Évaluation en sens direct

L'algorithme $E$ prend en entrée les paramètres publics et un message $m$ représenté comme une chaîne binaire $m_{0},m_{1},\dotsc ,m_{n}$. Il retourne $$c=\prod _{i=0}^{n}v_{i}^{m_{i}}{\bmod {p}}.$$

Inversion avec trappe

L'algorithme $D$ prend en entrée les paramètres publics, un élément $c\in \mathbb {F} _{p}$, et un entier $s$. Il retourne $$m=\sum _{i=0}^{n}{\frac {2^{i}}{p_{i}-1}}\cdot \left(\operatorname {pgcd} (p_{i},c^{s}{\bmod {p}})-1\right)$$

Sécurité

La sécurité de la fonction à trappe repose sur la difficulté du problème de sac à dos multiplicatif suivant : étant donné $$c=\prod _{i=0}^{n}v_{i}^{m_{i}}{\bmod {p}}.$$retrouver les $m_{i}$. Contrairement aux cryptosystèmes à base de sacs à dos additifs, comme celui de Merkle-Hellman, les techniques de réduction de réseau euclidien ne s'appliquent pas à ce problème.

La meilleure attaque générique connue consiste à résoudre le problème du logarithme discret pour retrouver $s$ à partir de $p,p_{i},v_{i}$, ce qui est considéré difficile pour un calculateur classique. En revanche, l'algorithme quantique de Shor résout efficacement ce problème, et le sac à dos de Naccache-Stern n'est donc pas post-quantique. De plus, à l'heure actuelle (2018), il n'existe pas de preuve que le sac à dos de Naccache-Stern se réduit au logarithme discret.

La meilleure attaque spécifique connue (en 2018) utilise le théorème des anniversaires pour inverser partiellement la fonction sans connaître la trappe, sous l'hypothèse que le message est de poids de Hamming très faible. Apprendre plus d'un nombre logarithmique de bits du message est un problème ouvert.

Variantes et améliorations

Bande passante

La bande passante (taille du message divisée par la taille de $c$) tend asymptotiquement vers zéro, du fait de la raréfaction des nombres premiers. Ce phénomène peut toutefois être compensé en adoptant un meilleur encodage des messages.

Cryptosystèmes à base du sac à dos de Naccache-Stern

Le sac à dos de Naccache-Stern est déterministe et ne peut donc pas garantir de sécurité sémantique, ce qui est un obstacle à la construction d'un cryptosystème à clé publique. Il est toutefois possible de modifier la fonction en introduisant un aléa, ce qui retire cet obstacle.