Signature de Boneh-Lynn-Shacham
En cryptologie, le schéma de signature de Boneh-Lynn-Shacham (BLS) est un mécanisme de signature numérique inventé en 2001 par Dan Boneh, Ben Lynn et Hovav Shacham[1]. Il s'agit du premier exemple de signature construit en cryptographie à base de couplages, s'appuyant sur l'accouplement de Weil pour obtenir des signatures très courtes[2]. Son introduction a motivé de nombreuses questions théoriques et pratiques (groupes « gap Diffie-Hellman », hachage vers les courbes elliptiques, etc. voir plus bas) et il a permis la conception de nouvelles primitives efficaces[3].
Description
Groupe gap Diffie-Hellman
La construction BLS s'appuie sur un groupe dans lequel résoudre la version décisionnelle du problème de Diffie-Hellman est facile, mais résoudre la version calculatoire est difficile[Note 1]. Un tel écart (en anglais, gap) n'est pas connu pour les groupes classiques utilisés en cryptographie, tels que les groupes multiplicatifs des corps finis .
En revanche, la situation est différente pour le groupe des points rationnels d'une courbe elliptique[Note 2] : le problème calculatoire peut demeurer difficile, mais l'existence de l'accouplement de Weil rend trivial le problème décisionnel de Diffie-Hellman. Autrement dit, il est possible d'exhiber un groupe et un générateur et une fonction tels que :
- Étant donnés il soit difficile de calculer ;
- Étant donnés , on a et . En comparant ces deux valeurs, on détermine si .
Un groupe de ce type est dit « gap Diffie-Hellman ».
Le groupe dans lequel prend ses valeurs n'est autre que le groupe des racines -ièmes de l'unité, pour un entier fixé. La fonction est obtenue à partir de l'accouplement de Weil[Note 3], lequel se calcule via l'algorithme de Miller.
Signature BLS
Paramètres publics
Le schéma de signature BLS repose sur trois algorithmes décrits ci-dessous. On se donne préalablement un groupe gap Diffie-Hellman de générateur et d'ordre premier . On se donne également une fonction de hachage cryptographique [Note 4].
En principe, le groupe et la fonction de hachage sont choisis en fonction d'un paramètre de sécurité donné . Le groupe, la fonction , et le paramètre de sécurité sont implicitement partagés avec tous les algorithmes.
Génération de clés
Un nombre est choisi et constitue la clé privée. Le point constitue la clé publique.
Signature
Soit un message, la signature est .
Vérification
Cet algorithme prend en entrée la clé publique , un message et une signature et renvoie une erreur si n'est pas un 4-uplet de Diffie-Hellman, autrement dit si . Sinon la signature est valide.
En effet, on a pour une signature générée honnêtement Une particularité inhabituelle de ce schéma de signature est que la vérification (qui invoque le calcul de , c'est-à-dire de l'algorithme de Miller) est plus lente que la signature (qui n'est qu'une multiplication sur la courbe).
Aspects techniques
Choix du groupe
La construction de Boneh-Lynn-Shacham repose sur un groupe gap Diffie-Hellman, et propose d'obtenir un tel groupe à partir de courbes elliptiques. La difficulté est de construire une courbe sur laquelle le problème calculatoire de Diffie-Hellman (CDH) est difficile (donc, a fortiori, le problème du logarithme discret), mais le problème décisionnel (DDH) est facile. On décrit ici la démarche adoptée pour BLS.
Soit une courbe elliptique définie sur un corps fini , possédant points, et soit un entier premier tel que . S'il existe un point sur d'ordre , on dit que le groupe engendré par a pour « degré de plongement » , où est le plus petit entier satisfaisant :Essentiellement, mesure la taille de la plus petite extension de dans laquelle toutes les racines -ièmes de l'unité existent. Le calcul de l'accouplement de Weil est efficace lorsque est petit, ce qui permet de résoudre DDH. Mais si est trop petit, le problème du logarithme discret sur peut être plongé comme un problème de logarithme discret dans l'extension , où des algorithmes plus efficaces sont disponibles (par exemple GNFS), ce qui casse CDH[Note 5]. Il s'agit donc de trouver un compromis, c'est-à-dire une courbe telle que la valeur de assez grande pour que CDH soit difficile, mais assez petite pour que DDH soit toujours facile.
BLS proposent d'utiliser les courbes définie sur avec premier[Note 6],[4],[5]. Il s'agit de courbes supersingulières, de degré de plongement 6[Note 7], sur lesquelles CDH est au plus aussi difficile que le logarithme discret dans . Depuis ces travaux, plusieurs courbes ont été proposées qui possèdent de meilleures propriétés[6],[7],[8] ainsi que d'autre accouplements plus faciles à calculer (notamment ceux de Tate)..
Hachage vers les courbes elliptiques
Un autre ingrédient des signatures BLS est la fonction de hachage , qui prend ses valeurs dans le groupe, c'est-à-dire ici dans une courbe elliptique. Il s'agit d'un problème ardu en général, qui n'était pas résolu au moment de la publication de BLS. La première construction d'une fonction de hachage de ce type a été proposée en 2010[9],[10].
Sécurité
Le schéma de signature BLS est prouvé sûr contre les contrefaçons existentielles dans les attaques adaptatives à message choisi (EF-CMA2), par réduction dans le modèle de l'oracle aléatoire à la résolution du problème calculatoire de Diffie-Hellman dans le groupe [1].
Application
Les signatures du BLS sont largement utilisées dans la version 2 (Eth2) de la blockchain Ethereum pour garantir de manière cryptographique qu'un validateur Eth2 spécifique a effectivement vérifié une transaction particulière[11].
Notes et références
Notes
- ↑ Au sens habituel qu'il n'existe pas d'algorithme en temps polynomial pour résoudre ce problème.
- ↑ On utilise ici, en suivant BLS, une notation multiplicative pour le groupe des points de la courbe elliptique.
- ↑ Ce n'est pas l'accouplement de Weil lui-même, puisqu'il s'agit d'une forme alternante i.e. , ce qui donnerait un résultat trivial lorsque .
- ↑ On exige que la fonction ne prenne jamais pour valeur l'élément neutre de .
- ↑ Il s'agit exactement de l'attaque de Menezes-Okamoto-Vanstone.
- ↑ Ce choix permet d'éviter les attaques basées sur la descente de Weil, voir références ci-après.
- ↑ Une courbe supersingulière ne peut pas avoir une valeur de plus grande.
Références
- ↑ a et b (en) Dan Boneh, Ben Lynn et Hovav Shacham, « Short Signatures from the Weil Pairing », dans Advances in Cryptology — ASIACRYPT 2001, Springer Berlin Heidelberg, (ISBN 9783540429876, DOI 10.1007/3-540-45682-1_30, lire en ligne), p. 514–532
- ↑ (en) Dan Boneh, « BLS Short Digital Signatures », dans Encyclopedia of Cryptography and Security, Springer US, (ISBN 9781441959058, DOI 10.1007/978-1-4419-5906-5_140, lire en ligne), p. 158–159
- ↑ (en) Dan Boneh, Craig Gentry, Ben Lynn et Hovav Shacham, « Aggregate and Verifiably Encrypted Signatures from Bilinear Maps », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, (ISBN 9783540140399, DOI 10.1007/3-540-39200-9_26, lire en ligne), p. 416–432
- ↑ (en) Steven D. Galbraith⋆ et Nigel P. Smart, « A Cryptographic Application of Weil Descent », dans Cryptography and Coding, Springer Berlin Heidelberg, (ISBN 9783540668879, DOI 10.1007/3-540-46665-7_23, lire en ligne), p. 191–200
- ↑ (en) P. Gaudry, F. Hess et N. P. Smart, « Constructive and destructive facets of Weil descent on elliptic curves », Journal of Cryptology, vol. 15, no 1, , p. 19–46 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s00145-001-0011-x, lire en ligne, consulté le )
- ↑ (en) Paulo S. L. M. Barreto, Ben Lynn et Michael Scott, « Constructing Elliptic Curves with Prescribed Embedding Degrees », dans Security in Communication Networks, Springer Berlin Heidelberg, (ISBN 9783540004202, DOI 10.1007/3-540-36413-7_19, lire en ligne), p. 257–267
- ↑ (en) David Freeman, « Constructing Pairing-Friendly Elliptic Curves with Embedding Degree 10 », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, (ISBN 9783540360759, DOI 10.1007/11792086_32, lire en ligne), p. 452–465
- ↑ (en) David Freeman, Peter Stevenhagen et Marco Streng, « Abelian Varieties with Prescribed Embedding Degree », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, (ISBN 9783540794554, DOI 10.1007/978-3-540-79456-1_3, lire en ligne), p. 60–73
- ↑ (en) Eric Brier, Jean-Sébastien Coron, Thomas Icart et David Madore, « Efficient Indifferentiable Hashing into Ordinary Elliptic Curves », dans Advances in Cryptology – CRYPTO 2010, Springer Berlin Heidelberg, (ISBN 9783642146220, DOI 10.1007/978-3-642-14623-7_13, lire en ligne), p. 237–254
- ↑ (en) Reza R. Farashahi, Pierre-Alain Fouque, Igor Shparlinski et Mehdi Tibouchi, « Indifferentiable deterministic hashing to elliptic and hyperelliptic curves », Mathematics of Computation, vol. 82, no 281, , p. 491–512 (ISSN 0025-5718 et 1088-6842, DOI 10.1090/S0025-5718-2012-02606-8, lire en ligne, consulté le )
- ↑ (en) « ethereum/eth2.0-specs », sur GitHub (consulté le )
Portail de la cryptologie