Accouplement de Weil

Fonction bilinéaire non dégénérée définie entre les points de torsion d'une variété abélienne

En géométrie algébrique et en théorie des nombres, l'accouplement[Note 1] de Weil est une relation mathématique entre certains points d'une courbe elliptique, plus spécifiquement une application bilinéaire fonctorielle entre ses points de torsion. Cet accouplement est nommé en l'honneur du mathématicien français André Weil, qui en a systématisé l'étude[1]. Il s'agit d'un outil important dans l'étude de ces courbes[2].

Il est possible de définir un accouplement de Weil pour les courbes définies sur le corps des complexes[3] ou sur des corps finis[4] ; dans ce dernier cas, l'algorithme de Miller permet de le calculer efficacement, ce qui est à la base de la cryptographie à base de couplages sur les courbes elliptiques. Une construction similaire s'étend aux variétés algébriques plus générales[Note 2],[5].

DéfinitionModifier

On considère une courbe elliptique   définie sur un corps  . Soit   un entier[Note 3], et on suppose que  contient une racine primitive  -ième de l'unité, et on note  le groupe cyclique des racines  -ièmes de l'unité dans  . Notons enfin les points de  -torsion de la courbe :

 

 est l'application de « multiplication par  » dans le groupe des points rationnels de la courbe,  est l'élément neutre du groupe (le « point à l'infini »), et  est la clôture algébrique de  .Alors il existe un accouplement :

 
que l'on appelle accouplement de Weil. Cette fonction possède notamment les propriétés suivantes :
  • Bilinéarité :  .
  • Alternante :   et en particulier,  .
  • Non-dégénerescence : si   pour tout   alors  ; de même si   pour tout  alors  .
  • Invariance par les opérations du groupe de Galois : pour tout  ,  

Degré de plongementModifier

Pour une courbe définie sur un corps fini  , le plus petit entier   tel que   est appelé « degré de plongement ». Il correspond au degré de la plus petite extension dans laquelle les racines  -ièmes de l'unité sont définies. Cette terminologie provient de l'attaque MOV[6] qui permet notamment d'attaquer le problème du logarithme discret sur une courbe elliptique   en plongeant le problème dans un corps fini, précisément  , dans lequel des algorithmes plus efficaces sont connus tels que le crible du corps de nombre généralisé. Les applications cryptographiques reposent donc souvent sur des courbes à haut degré de plongement pour éviter de telles attaques : par exemple Curve25519 a un degré de plongement supérieur à  [7]. Dans les applications de cryptographie à base de couplages on utilise au contraire des courbes dont le degré de plongement est faible : la courbe de Barreto-Naehrig BN(2,254) par exemple a un degré de plongement égal à 12[7]. C'est notamment le cas de plusieurs courbes supersingulières[8],[9].

Construction expliciteModifier

Courbe elliptique définie sur  Modifier

Une courbe elliptique définie sur   correspond à un quotient    appartient au demi-plan de Poincaré. Soient  deux points de  -torsion, on définit l'accouplement de Weil par[3] :

 

On vérifie immédiatement que cette expression satisfait les propriétés d'un accouplement.

Cas général sur une courbe elliptiqueModifier

D'une manière générale, si on connaît une base de  , alors on peut obtenir aisément une expression analogue : soit  une base de  , on écrit  , et on définit

 

Cependant, étant donnés des points  , il est nécessaire en général de résoudre un problème de logarithme discret sur la courbe elliptique pour être capable d'exprimer les coordonnées   utilisées dans l'expression ci-dessus.

Le cas général est en fait mieux décrit en termes de diviseurs, qui se prête également volontiers au calcul explicite. Si   est un point de  -torsion de la courbe, on pose le diviseur   et on note  un élément du corps des fonctions sur  qui possède  pour diviseur[Note 4]. Sommairement, l'accouplement de Weil est défini par «   » sauf que cette expression n'est pas définie. En effet,  possède un pôle en  (et de même en intervertissant  et  ). Il suffit cependant de remplacer  (ou  ) par un diviseur linéairement équivalent, c'est-à-dire qui diffère de   (resp.  ) uniquement d'un diviseur principal.

En pratique, cela revient à décaler   en faisant intervenir un point arbitraire   pour obtenir  . La valeur de l'accouplement de Weil est bien sûr invariante par une telle modification[4].

Le calcul d'une fonction   correspondant à un diviseur donné   a longtemps été considéré difficile, jusqu'à l'introduction du très efficace algorithme de Miller [10].

Le caractère alternant de l'accouplement ainsi obtenu est évident ; la bilinéarité découle en général de la loi de réciprocité de Weil, à savoir que pour deux fonctions   du corps de fonctions de la courbe sur un corps algébriquement clos,  [1].

Accouplement de Weil  -adiqueModifier

Soit   un premier positif (et premier avec la caractéristique de   lorsque celle-ci est positive), alors on peut étendre l'accouplement de Weil   initialement défini sur   pour l'appliquer au module de Tate  -adique,  . On vérifie pour cela que la suite des accouplements pour les puissances successives de   est projective, c'est-à-dire que  , ce qui découle directement de la bilinéarité. Puisque l'application « multiplication par   »  et que l'application « mise à la puissance   »   forment également des systèmes projectifs compatibles, on définit l'accouplement de Weil  -adique comme la limite projective des accouplements sur  :

 

ExempleModifier

Prenons  ,  [Note 5]. On a  . Le point   est d'ordre  . Le degré de plongement est   (car  ). Posons  . Alors   est aussi d'ordre 3. L'algorithme de Miller permet d'obtenir les diviseurs :

 
qui correspondent à

 

À cause du point soulevé précédemment, on ne peut pas directement évaluer, il faut faire intervenir un point pour déplacer le diviseur. Par souci de symétrie considérons deux points et on déplacera les deux diviseurs :

 

deux points de  . Et on pose

 
Les fonctions correspondantes s'obtiennent aisément au moyen de de l'algorithme de Miller :
 
Et finalement on a l'accouplement de Weil :
 
On obtient   et on vérifie que c'est une racine cubique de l'unité. De même,
 
ce qui vérifie les relations de bilinéarité.

Voir aussiModifier

Notes et référencesModifier

NotesModifier

  1. On utilise parfois le terme de « couplage » par analogie avec l'anglais pairing, mais Weil lui-même utilise bien « accouplement » avec le sens mathématique précis que recouvre ce terme.
  2. Dans ce cas, l'accouplement porte entre les points de torsion de la variété et les points de torsion de sa variété duale.
  3. Si  est de caractéristique positive, on requiert que  et  soient premiers entre eux.
  4. Un tel élément existe et est unique à une constante multiplicative près.
  5. Il s'agit d'une courbe elliptique supersingulière.

RéférencesModifier

  1. a et b André Weil, « Sur les fonctions algébriques à corps de constantes fini », Les Comptes rendus de l'Académie des sciences, vol. 210,‎ , p. 592–594
  2. (en) Joseph H. Silverman, « A Survey of Local and Global Pairings on Elliptic Curves and Abelian Varieties », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, (ISBN 9783642174544, DOI 10.1007/978-3-642-17455-1_24, lire en ligne), p. 377–396
  3. a et b (en) Steven D. Galbraith, « The Weil pairing on elliptic curves over C », IACR ePrint Archive, no 323,‎ (lire en ligne, consulté le 14 août 2018)
  4. a et b (en) Joseph H. Silverman, « The Arithmetic of Elliptic Curves », Graduate Texts in Mathematics,‎ (ISSN 0072-5285 et 2197-5612, DOI 10.1007/978-0-387-09494-6, lire en ligne, consulté le 14 août 2018)
  5. (en) James Milne, « Abelian varieties »
  6. (en) A.J. Menezes, T. Okamoto et S.A. Vanstone, « Reducing elliptic curve logarithms to logarithms in a finite field », IEEE Transactions on Information Theory, vol. 39, no 5,‎ , p. 1639–1646 (ISSN 0018-9448, DOI 10.1109/18.259647, lire en ligne, consulté le 14 août 2018)
  7. a et b (en) Daniel J. Bernstein, « SafeCurves : Transfers », sur cr.yp.to,
  8. (en) Steven D. Galbraith, « Supersingular Curves in Cryptography », dans Advances in Cryptology — ASIACRYPT 2001, Springer Berlin Heidelberg, (ISBN 9783540429876, DOI 10.1007/3-540-45682-1_29, lire en ligne), p. 495–513
  9. (en) Alfred Menezes, « Supersingular Elliptic Curves in Cryptography », dans Pairing-Based Cryptography – Pairing 2007, Springer Berlin Heidelberg, (ISBN 9783540734888, DOI 10.1007/978-3-540-73489-5_15, lire en ligne), p. 293–293
  10. Vanessa Vitse, Couplages sur courbes elliptiques définies sur des corps finis : Mémoire de Master 2, Université Versailles Saint-Quentin, , 42 p. (lire en ligne)