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

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

En revanche, la situation est différente pour le groupe des points rationnels d'une courbe elliptique : 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 $G$ et un générateur $g$ et une fonction $e:G\times G\to G_{T}$ tels que :

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

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

Le groupe $G_{T}$ dans lequel $e$ prend ses valeurs n'est autre que le groupe des racines $n$-ièmes de l'unité, pour un entier $n$ fixé. La fonction $e$ est obtenue à partir de l'accouplement de Weil, 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 $(G,G_{T},e)$ de générateur $g$ et d'ordre premier $p$. On se donne également une fonction de hachage cryptographique $H:\{0,1\}\to G$.

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

Génération de clés

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

Signature

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

Vérification

Cet algorithme prend en entrée la clé publique $v$, un message $M$ et une signature $\sigma$ et renvoie une erreur si $(g,v,H(M),\sigma )$ n'est pas un 4-uplet de Diffie-Hellman, autrement dit si $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

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

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

Essentiellement, $k$ mesure la taille de la plus petite extension de $\mathbb {F} _{q}$ dans laquelle toutes les racines $n$-ièmes de l'unité existent. Le calcul de l'accouplement de Weil est efficace lorsque $k$ est petit, ce qui permet de résoudre DDH. Mais si $k$ est trop petit, le problème du logarithme discret sur $E$ peut être plongé comme un problème de logarithme discret dans l'extension $\mathbb {F} _{q^{k}}$, où des algorithmes plus efficaces sont disponibles (par exemple GNFS), ce qui casse CDH. Il s'agit donc de trouver un compromis, c'est-à-dire une courbe telle que la valeur de $k$ assez grande pour que CDH soit difficile, mais assez petite pour que DDH soit toujours facile.

BLS proposent d'utiliser les courbes $E^{\pm }:y^{2}=x^{3}+2x\pm 1$ définie sur $\mathbb {F} _{3^{\ell }}$ avec $\ell$ premier. Il s'agit de courbes supersingulières, de degré de plongement 6, sur lesquelles CDH est au plus aussi difficile que le logarithme discret dans $\mathbb {F} _{3^{6\ell }}$. Depuis ces travaux, plusieurs courbes ont été proposées qui possèdent de meilleures propriétés 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 $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.

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

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.