Sac à dos de Naccache-Stern

Soit ${\displaystyle p_{i}}$ le ${\displaystyle i}$-ième nombre premier, commençant par ${\displaystyle p_{0}=2}$. L'algorithme ${\displaystyle G}$ prend en entrée un paramètre de sécurité ${\displaystyle 1^{\lambda }}$, choisit un entier ${\displaystyle n}$ et un premier ${\displaystyle p}$ tel que

$${\displaystyle p>\prod _{i=0}^{n}p_{i}.}$$

L'algorithme choisit alors un entier ${\displaystyle s}$ premier avec ${\displaystyle p-1}$, puis retourne les paramètres publics ${\displaystyle p,n}$ et les racines ${\displaystyle s}$-ièmes ${\displaystyle v_{i}=p_{i}^{1/s}{\bmod {p}}}$[Note 2] et la trappe, ${\displaystyle s}$ .

L'algorithme ${\displaystyle E}$ prend en entrée les paramètres publics et un message ${\displaystyle m}$ représenté comme une chaîne binaire ${\displaystyle m_{0},m_{1},\dotsc ,m_{n}}$. Il retourne

$${\displaystyle c=\prod _{i=0}^{n}v_{i}^{m_{i}}{\bmod {p}}.}$$

L'algorithme ${\displaystyle D}$ prend en entrée les paramètres publics, un élément ${\displaystyle c\in \mathbb {F} _{p}}$, et un entier ${\displaystyle s}$. Il retourne

$${\displaystyle m=\sum _{i=0}^{n}{\frac {2^{i}}{p_{i}-1}}\cdot \left(\operatorname {pgcd} (p_{i},c^{s}{\bmod {p}})-1\right)}$$

La bande passante (taille du message divisée par la taille de ${\displaystyle 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[3] - [4].

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[5].