Signature de Lamport

Le schéma de signature de Lamport est composé de trois algorithmes : génération de clés, signature et vérification.

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.

La sécurité du schéma de signature de Lamport face aux contrefaçons existentielles se ramène immédiatement (et dans le modèle standard) à la difficulté de calculer une préimage pour ${\displaystyle H}$^[6],[c]. Cependant, le schéma ne peut être utilisé que pour signer un seul message. En effet, la signature révèle par construction une partie (50%) de la clé privée.

Un calculateur quantique facilite la recherche d'une préimage (au moyen de l'algorithme de Grover), divisant par deux le niveau de sécurité par rapport à un adversaire classique. Ce phénomène est aisément compensé en doublant les paramètres de la fonction ${\displaystyle H}$ ; pour cette raison, le schéma de Lamport est considéré comme un candidat post-quantique^[4],[7].

• Portail de la cryptologie