Signature de Lamport

En cryptologie, le schéma de signature de Lamport est un mécanisme à usage unique permettant de signer numériquement un document. Il a été introduit en 1979 par l'informaticien américain Leslie Lamport. La construction des signatures de Lamport repose uniquement sur les fonctions à sens unique, une approche qui a inspiré plusieurs constructions cryptographiques et qui s'avère être un candidat post-quantique.

Les signatures de Lamport souffrent de nombreux désavantages techniques, en particulier leur usage unique, la taille des clés et des signatures, qui ont motivé la création d'algorithmes plus efficaces (par Merkle et d'autres).

Description

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

Génération de clés

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

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

Signature

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

Vérification

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

Sécurité

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 $H$. 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 $H$ ; pour cette raison, le schéma de Lamport est considéré comme un candidat post-quantique.