The Weil pairing, and its efficient calculation (Q1772231)

For the computation of the Weil pairing on elliptic curves many papers cite ``Miller's algorithm'' referring to an unpublished manuscript by Victor Miller. A typed version of that paper became available over the internet some years ago. This paper is an extended version of those initial notes combined with material on the mathematical background and many recent references. The evaluation of the Weil pairing \(e_n(P,Q)\) on points of order \(n\) requires to find a function \(f_{n,P}\) such that \(\text{div}(f_{n,P})=n[P]-n[O]\) and then to evaluate \(f_{n,P}(D_Q)\), where \(D_Q\) is a divisor equivalent to \(Q-O\) and vice versa for \(f_{n,Q}\). In fact one is only interested in the value of the evaluation and not in the function itself. This paper shows how to use addition-subtraction chains -- most prominently the double-and-add method -- to compute this value in \(O(\log n)\) operations. This is done iteratively together with the computation of \(nP\) in the group of points by evaluating the lines arising from the addition or doubling at \(D\) and updating the intermediate results. Miller also shows that the value of the Weil pairing equals \[ e_n(P,Q)=(-1)^n\frac{f_{n,P}(Q)}{f_{n,Q}(P)}. \] This equality is proven unconditionally and allows to speed up the evaluation by a factor of \(2\) compared to the original definition. For cryptographic applications the Weil pairing is of interest as it provides a bilinear map from the elliptic curve to an extension field \(\mathbb F_{q^k}\) of the ground field \(\mathbb F_q\). If this embedding degree \(k\) is small then the transfer of the Discrete Logarithm Problem (DLP) in \(E(\mathbb F_q)\) to the DLP in \(\mathbb F_{q^k}^*\) leads to an easier problem as computing discrete logarithms is subexponential in the multiplicative group of finite fields. \textit{A. J. Menezes}, \textit{T. Okamoto}, and \textit{S. A. Vanstone} [IEEE Trans. Inf. Theory 39, No. 5, 1639--1646 (1993; Zbl 0801.94011)] point out that the embedding degree of supersingular curves is at most \(6\). For some time the Weil pairing was only seen as a means to attack curves with low embedding degree and therefore Miller's algorithm remained state of the art for a long time as it provided a polynomial time transfer. \textit{A. Joux} [Algorithmic number theory, ANTS-IV, Lect. Notes Comput. Sci. 1838, 385--393 (2000; Zbl 1029.94026); J. Cryptology 17, No. 4, 263--276 (2004; Zbl 1070.94007)] used the Weil pairing constructively to establish a tripartite key exchange and \textit{D. Boneh} and \textit{M. Franklin} [Crypto 2001, Lect. Notes Comput. Sci. 2139, 213--229 (2001; Zbl 1002.94023); SIAM J. Comput. 32, No. 3, 586--615 (2003; Zbl 1046.94008)] constructed an identity based cryptosystem from the Weil pairing. In the sequel more applications of pairings in cryptography were proposed such that also constant factors in the speed of efficient evaluation of the Weil pairing became of interest. For a recent overview see \textit{P. S. L. M. Barreto}, \textit{B. Lynn}, and \textit{M. Scott} [J. Cryptology 17, No. 4, 321--334 (2004; Zbl 1123.94334)]. Note that some applications use the Tate-Lichtenbaum pairing as described by \textit{G. Frey} and \textit{H.-G. Rück} [Math. Comput. 62, No. 206, 865--874 (1994; Zbl 0813.14045)] instead of the Weil pairing. The computation also needs the evaluation of \(f_{n,P}(Q)\). As a second topic Miller gives algorithms to determine the group structure of the elliptic curve, i.e. to find the elementary divisors, using the Weil pairing. The first but more time-consuming one also gives generators of the group but requires the factorization of the group order to determine the orders of the input points \(P\) and \(Q\). The algorithms make use of the facts that \(e_n(P,P)=1\) and that the pairing is non-degenerate, i.e. for each \(P\neq O\) there exists a point \(Q\) over the algebraic closure such that \(e_n(P,Q)\neq 1\). For the case that the generators should be echelonized, \textit{D. R. Kohel} and \textit{I. E. Shparlinski} [Algorithmic number theory, ANTS-IV, Lect. Notes Comput. Sci. 1838, 395--404 (2000; Zbl 1032.11034)] provided an algorithm.