Signature de Boneh-Lynn-Shacham

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 ${\displaystyle \mathbb {F} _{q}^{\times }}$.

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 ${\displaystyle G}$ et un générateur ${\displaystyle g}$ et une fonction ${\displaystyle e:G\times G\to G_{T}}$ tels que :

• Étant donnés ${\displaystyle (g,g^{x},g^{y})}$ il soit difficile de calculer ${\displaystyle g^{xy}}$ ;
• Étant donnés ${\displaystyle (g^{z},g^{x},g^{y})}$, on a ${\displaystyle e(g^{x},g^{y})=e(g,g)^{xy}}$ et ${\displaystyle e(g,g^{z})=e(g,g)^{z}}$. En comparant ces deux valeurs, on détermine si ${\displaystyle xy=z}$.

Un groupe de ce type est dit « gap Diffie-Hellman ».

Le groupe ${\displaystyle G_{T}}$ dans lequel ${\displaystyle e}$ prend ses valeurs n'est autre que le groupe des racines ${\displaystyle n}$-ièmes de l'unité, pour un entier ${\displaystyle n}$ fixé. La fonction ${\displaystyle e}$ est obtenue à partir de l'accouplement de Weil[Note 3], lequel se calcule via l'algorithme de Miller.

Le schéma de signature BLS repose sur trois algorithmes décrits ci-dessous. On se donne préalablement un groupe gap Diffie-Hellman ${\displaystyle (G,G_{T},e)}$ de générateur ${\displaystyle g}$ et d'ordre premier ${\displaystyle p}$. On se donne également une fonction de hachage cryptographique ${\displaystyle H:\{0,1\}\to G}$[Note 4].

En principe, le groupe et la fonction de hachage sont choisis en fonction d'un paramètre de sécurité donné ${\displaystyle 1^{\lambda }}$. Le groupe, la fonction ${\displaystyle H}$, et le paramètre de sécurité sont implicitement partagés avec tous les algorithmes.

Un nombre ${\displaystyle x\in \mathbb {Z} /(p)}$ est choisi et constitue la clé privée. Le point ${\displaystyle v=g^{x}}$ constitue la clé publique.

Soit ${\displaystyle M\in \{0,1\}^{*}}$ un message, la signature est ${\displaystyle \sigma =H(M)^{x}}$.

Cet algorithme prend en entrée la clé publique ${\displaystyle v}$, un message ${\displaystyle M}$ et une signature ${\displaystyle \sigma }$ et renvoie une erreur si ${\displaystyle (g,v,H(M),\sigma )}$ n'est pas un 4-uplet de Diffie-Hellman, autrement dit si ${\displaystyle e(v,H(M))\neq e(g,\sigma )}$. Sinon la signature est valide.

En effet, on a pour une signature générée honnêtement

$${\displaystyle {\begin{aligned}e(v,H(M))&=e(g^{x},H(M))\\&=e(g,H(M))^{x}\\&=e(g,H(M)^{x})\\&=e(g,\sigma )\end{aligned}}}$$

Une particularité inhabituelle de ce schéma de signature est que la vérification (qui invoque le calcul de ${\displaystyle e}$, c'est-à-dire de l'algorithme de Miller) est plus lente que la signature (qui n'est qu'une multiplication sur la courbe).

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 ${\displaystyle E}$ une courbe elliptique définie sur un corps fini ${\displaystyle \mathbb {F} _{q}}$, possédant ${\displaystyle m}$ points, et soit ${\displaystyle n}$ un entier premier tel que ${\displaystyle n^{2}\nmid m}$. S'il existe un point ${\displaystyle P}$ sur ${\displaystyle E}$ d'ordre ${\displaystyle n}$, on dit que le groupe ${\displaystyle \langle P\rangle }$ engendré par ${\displaystyle P}$a pour « degré de plongement » ${\displaystyle k}$, où ${\displaystyle k}$ est le plus petit entier satisfaisant :

$${\displaystyle n\mid q^{k}-1\qquad {\text{mais}}\qquad n\nmid q^{\ell }-1{\text{ pour tout }}\ell =1,\dotsc ,k-1}$$

Essentiellement, ${\displaystyle k}$ mesure la taille de la plus petite extension de ${\displaystyle \mathbb {F} _{q}}$ dans laquelle toutes les racines ${\displaystyle n}$-ièmes de l'unité existent. Le calcul de l'accouplement de Weil est efficace lorsque ${\displaystyle k}$ est petit, ce qui permet de résoudre DDH. Mais si ${\displaystyle k}$ est trop petit, le problème du logarithme discret sur ${\displaystyle E}$ peut être plongé comme un problème de logarithme discret dans l'extension ${\displaystyle \mathbb {F} _{q^{k}}}$, 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 ${\displaystyle k}$ assez grande pour que CDH soit difficile, mais assez petite pour que DDH soit toujours facile.

BLS proposent d'utiliser les courbes ${\displaystyle E^{\pm }:y^{2}=x^{3}+2x\pm 1}$ définie sur ${\displaystyle \mathbb {F} _{3^{\ell }}}$ avec ${\displaystyle \ell }$ 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 ${\displaystyle \mathbb {F} _{3^{6\ell }}}$. 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)..

Un autre ingrédient des signatures BLS est la fonction de hachage ${\displaystyle H:\{0,1\}\to G}$, 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].