Sac à dos de Naccache-Stern

Summarize Timeline Fact Check

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

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)}$$