Signature de Boneh-Lynn-Shacham

Schéma de signature à base de couplages

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],[2]. 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[3]. 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[4].

DescriptionModifier

Groupe gap Diffie-HellmanModifier

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 BLSModifier

Paramètres publicsModifier

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

Un nombre   est choisi et constitue la clé privée. Le point   constitue la clé publique.

SignatureModifier

Soit   un message, la signature est  .

VérificationModifier

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 techniquesModifier

Choix du groupeModifier

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],[5],[6]. 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[7],[8],[9] ainsi que d'autre accouplements plus faciles à calculer (notamment ceux de Tate)..

Hachage vers les courbes elliptiquesModifier

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[10],[11].

SécuritéModifier

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

Notes et référencesModifier

NotesModifier

  1. Au sens habituel qu'il n'existe pas d'algorithme en temps polynomial pour résoudre ce problème.
  2. On utilise ici, en suivant BLS, une notation multiplicative pour le groupe des points de la courbe elliptique.
  3. 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  .
  4. On exige que la fonction   ne prenne jamais pour valeur l'élément neutre de  .
  5. Il s'agit exactement de l'attaque de Menezes-Okamoto-Vanstone.
  6. Ce choix permet d'éviter les attaques basées sur la descente de Weil, voir références ci-après.
  7. Une courbe supersingulière ne peut pas avoir une valeur de   plus grande.

RéférencesModifier

  1. 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
  2. (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
  3. (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
  4. (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
  5. (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
  6. (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 20 septembre 2018)
  7. (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
  8. (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
  9. (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
  10. (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
  11. (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 20 septembre 2018)