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. 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 . 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 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, 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 de générateur et d'ordre premier . On se donne également une fonction de hachage cryptographique . 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.