Signature de Lamport

Schéma de signature à usage unique, à base de fonctions à sens unique

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).

DescriptionModifier

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ésModifier

L'algorithme de génération de clés prend en entrées un paramètre de sécurité   et une taille de messages  , puis détermine deux entiers  , et une fonction à sens unique  . L'algorithme de génération de clés tire ensuite   éléments uniformément au hasard   pour   et  .

L'algorithme retourne la clé privée  , la clé publique   et les paramètres publics  .

SignatureModifier

L'algorithme de signature prend en entrées les paramètres publics, la clé privée, et   un message à signer. La signature correspondante est  .

VérificationModifier

L'algorithme de vérification prend en entrées les paramètres publics, la clé publique, un message   et une signature  . S'il existe un indice   tel que   alors l'algorithme retourne une erreur. Sinon, il renvoie un succès.

SécuritéModifier

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

Notes et référencesModifier

NotesModifier

  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érencesModifier

  1. (en) W. Diffie et M. Hellman, « New directions in cryptography », IEEE Transactions on Information Theory, vol. 22, no 6,‎ , p. 644–654 (ISSN 0018-9448, DOI 10.1109/tit.1976.1055638, lire en ligne, consulté le 1er 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, (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. a et b (en) Tanja Lange, « Hash-Based Signatures », dans Encyclopedia of Cryptography and Security, Springer US, (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, (ISBN 9782759809950 et 2759809951, OCLC 854569776, lire en ligne), p. 143
  6. (en) Anna Lysyanskaya, « Lecture 17: Digital Signature Schemes »,
  7. (en) Daniel J. Bernstein, « Post-Quantum Cryptography », dans Encyclopedia of Cryptography and Security, Springer US, (ISBN 9781441959058, DOI 10.1007/978-1-4419-5906-5_386, lire en ligne), p. 949–950