Signature de Lamport

L'algorithme de génération de clés prend en entrées un paramètre de sécurité ${\displaystyle \lambda }$ et une taille de messages ${\displaystyle n}$, puis détermine deux entiers ${\displaystyle k,\ell }$, et une fonction à sens unique ${\displaystyle H:\{0,1\}^{k}\to \{0,1\}^{\ell }}$. L'algorithme de génération de clés tire ensuite ${\displaystyle 2n}$ éléments uniformément au hasard ${\displaystyle y_{i,b}}$ pour ${\displaystyle i\in \{1,\dotsc ,n\}}$ et ${\displaystyle b\in \{0,1\}}$.

L'algorithme retourne la clé privée ${\displaystyle {\mathsf {sk}}=\{y_{i,b}\}}$, la clé publique ${\displaystyle {\mathsf {pk}}=\{z_{i,b}=H(y_{i,b})\}}$ et les paramètres publics ${\displaystyle {\mathsf {pp}}=\{\lambda ,n,k,\ell ,H\}}$.

L'algorithme de signature prend en entrées les paramètres publics, la clé privée, et ${\displaystyle m=(m_{1},\dotsc ,m_{n})\in \{0,1\}^{n}}$ un message à signer. La signature correspondante est ${\displaystyle \sigma =\{\sigma _{i}=y_{i,m_{i}}\}_{i=1}^{n}}$.

L'algorithme de vérification prend en entrées les paramètres publics, la clé publique, un message ${\displaystyle m}$ et une signature ${\displaystyle \sigma }$. S'il existe un indice ${\displaystyle i}$ tel que ${\displaystyle H(\sigma _{i})\neq z_{i,m_{i}}}$ alors l'algorithme retourne une erreur. Sinon, il renvoie un succès.