Accouplement de Weil

Pour une courbe définie sur un corps fini ${\displaystyle \mathbb {F} _{q}}$, le plus petit entier ${\displaystyle \ell }$ tel que ${\displaystyle n\mid q^{\ell }-1}$ est appelé « degré de plongement ». Il correspond au degré de la plus petite extension dans laquelle les racines ${\displaystyle n}$-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 ${\displaystyle E(\mathbb {F} _{q})}$ en plongeant le problème dans un corps fini, précisément ${\displaystyle \mathbb {F} _{q^{\ell }}}$, 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 à ${\displaystyle 2^{249}}$[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].

Une courbe elliptique définie sur ${\displaystyle \mathbb {C} }$ correspond à un quotient ${\displaystyle E=\mathbb {C} /\langle 1,\tau \rangle }$où ${\displaystyle \tau }$ appartient au demi-plan de Poincaré. Soient ${\displaystyle a+b\tau ,c+d\tau \in E[n]}$deux points de ${\displaystyle n}$-torsion, on définit l'accouplement de Weil par[3] :

$${\displaystyle w_{n}(a+b\tau ,c+d\tau )=\exp \left[2i\pi n\left(ad-bc\right)\right]}$$

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

D'une manière générale, si on connaît une base de ${\displaystyle E[n]}$, alors on peut obtenir aisément une expression analogue : soit ${\displaystyle \{A,B\}}$ une base de ${\displaystyle E[n]}$, on écrit ${\displaystyle P=aA+bB,Q=cA+dB}$, et on définit

$${\displaystyle w_{n}(P,Q)=w_{n}(aA+bB,cA+dB)=w_{n}(A,B)^{\left(ad-bc\right)}}$$

Cependant, étant donnés des points ${\displaystyle P,Q}$, 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 ${\displaystyle a,b,c,d}$ 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 ${\displaystyle P}$ est un point de ${\displaystyle n}$-torsion de la courbe, on pose le diviseur ${\displaystyle D_{P}=n(P)-n(O)}$ et on note ${\displaystyle f_{P}}$ un élément du corps des fonctions sur ${\displaystyle E({\overline {k}})}$ qui possède ${\displaystyle D_{P}}$ pour diviseur[Note 4]. Sommairement, l'accouplement de Weil est défini par « ${\displaystyle f_{P}(D_{Q})/f_{Q}(D_{P})}$ » sauf que cette expression n'est pas définie. En effet, ${\displaystyle f_{P}}$ possède un pôle en ${\displaystyle O\in \operatorname {supp} D_{Q}}$ (et de même en intervertissant ${\displaystyle P}$ et ${\displaystyle Q}$). Il suffit cependant de remplacer ${\displaystyle D_{P}}$ (ou ${\displaystyle D_{Q}}$) par un diviseur linéairement équivalent, c'est-à-dire qui diffère de ${\displaystyle D_{P}}$ (resp. ${\displaystyle D_{Q}}$) uniquement d'un diviseur principal.

En pratique, cela revient à décaler ${\displaystyle D_{P}}$ en faisant intervenir un point arbitraire ${\displaystyle R}$ pour obtenir ${\displaystyle D_{P}'=n(P+R)-n(R)}$. La valeur de l'accouplement de Weil est bien sûr invariante par une telle modification[4].

Le calcul d'une fonction ${\displaystyle f_{P}}$ correspondant à un diviseur donné ${\displaystyle D_{P}}$ 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 ${\displaystyle f,g}$ du corps de fonctions de la courbe sur un corps algébriquement clos, ${\displaystyle f(\operatorname {div} g)=g(\operatorname {div} f)}$[1].

Soit ${\displaystyle \ell }$ un premier positif (et premier avec la caractéristique de ${\displaystyle k}$ lorsque celle-ci est positive), alors on peut étendre l'accouplement de Weil ${\displaystyle e_{\ell ^{n}}}$ initialement défini sur ${\displaystyle E[\ell ^{n}]}$ pour l'appliquer au module de Tate ${\displaystyle \ell }$-adique, ${\displaystyle T_{\ell }(E)}$. On vérifie pour cela que la suite des accouplements pour les puissances successives de ${\displaystyle \ell }$ est projective, c'est-à-dire que ${\displaystyle e_{\ell ^{n+1}}(P,Q)^{\ell }=e_{\ell ^{n}}\left([\ell ]P,[\ell ]Q\right)}$, ce qui découle directement de la bilinéarité. Puisque l'application « multiplication par ${\displaystyle \ell }$ » ${\displaystyle [\ell ]:E[\ell ^{n+1}]\to E[\ell ^{n}]}$ et que l'application « mise à la puissance ${\displaystyle \ell }$ » ${\displaystyle (\cdot )^{\ell }:\mu _{\ell ^{n+1}}\to \mu _{\ell ^{n}}}$ forment également des systèmes projectifs compatibles, on définit l'accouplement de Weil ${\displaystyle \ell }$-adique comme la limite projective des accouplements sur ${\displaystyle E[\ell ^{n}]}$ :

$${\displaystyle w_{T_{\ell }}:T_{\ell }(E)\times T_{\ell }(E)\to \varprojlim \mu _{\ell ^{n}}}$$