Signature de Lamport

Représentation de séquence pour signer un document avec une signature Lamport. La clé privée utilise des mots courants pour faciliter la visualisation du processus. En utilisation réelle, des valeurs cryptographiquement sécurisées doivent être utilisées.

En cryptologie, le schéma de signature de Lamport^[a],[1] est un mécanisme à usage unique^[b] permettant de signer numériquement un document^[2]. Il a été introduit en 1979 par l'informaticien américain Leslie Lamport^[3]. 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^[4].

Les signatures de Lamport souffrent de nombreux désavantages techniques, en particulier leur usage unique, la taille des clés et des signatures^[5], 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é ${\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\}}$.

Signature

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

Vérification

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.

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 ${\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].

Notes et références

Notes

1. Parfois appelé « schéma de signature de Lamport-Diffie », puisqu'on peut retracer l'idée à (Diffie et Hellman 1976, p. 650), mais la construction en entier et l'analyse de sécurité apparaissent pour la première fois dans (Lamport 1979).
2. On parle dans ce contexte de « signature à usage unique », ou de « signature jetable » (OTS, pour l'anglais one time signature), en analogie au masque jetable pour le chiffrement.
3. Pour les implémentations, une fonction de hachage cryptographique pourra jouer ce rôle.

Références

1. (en) W. Diffie et M. Hellman, « New directions in cryptography », IEEE Transactions on Information Theory, vol. 22, n^o 6,‎ novembre 1976, p. 644–654 (ISSN 0018-9448, DOI 10.1109/tit.1976.1055638, lire en ligne, consulté le 1^er septembre 2018)
2. (en) Johannes Gehrke, Daniel Kifer, Ashwin Machanavajjhala et Arjen K. Lenstra, « Lamport One-Time Signatures », dans Encyclopedia of Cryptography and Security, Springer US, 2011 (ISBN 9781441959058, DOI 10.1007/978-1-4419-5906-5_1131, lire en ligne), p. 710–710
3. (en) Leslie Lamport, Constructing digital signatures from a one-way function, Technical Report SRI-CSL-98, SRI International Computer Science Laboratory, Oct. 1979.
4. (en) Tanja Lange, « Hash-Based Signatures », dans Encyclopedia of Cryptography and Security, Springer US, 2011 (ISBN 9781441959058, DOI 10.1007/978-1-4419-5906-5_413, lire en ligne), p. 540–542
5. Guillot, Philippe., La cryptologie : l'art des codes secrets, EDP Sciences, 2013, 196 p. (ISBN 978-2-7598-0995-0 et 2759809951, OCLC 854569776, lire en ligne), p. 143
6. (en) Anna Lysyanskaya, « Lecture 17: Digital Signature Schemes », 2016
7. (en) Daniel J. Bernstein, « Post-Quantum Cryptography », dans Encyclopedia of Cryptography and Security, Springer US, 2011 (ISBN 9781441959058, DOI 10.1007/978-1-4419-5906-5_386, lire en ligne), p. 949–950

• Portail de la cryptologie