The generalized Weil pairing and the discrete logarithm problem on elliptic curves (Q596141): Difference between revisions

The paper deals with a generalization of the Weil pairing, which is used to give a new reduction algorithm from the discrete logarithm problem on elliptic curves (ECDLP) to the discrete logarithm problem in finite fields (DLP). \textit{A. J. Menezes, T. Okamoto} and \textit{S. A. Vanstone} (MOV) [IEEE Trans. Inf. Theory 39, 1639--1646 (1993; Zbl 0801.94011)] used the Weil pairing to translate the ECDLP from an elliptic curve \(E\) over \(\mathbb{F}_q\) to the DLP in a certain field extension \(\mathbb{F}_{q^k}\), where it can be solved using the subexponential attack of the index calculus method. So the MOV algorithm provides an efficient way to attack the ECDLP if \(k\)\, is small enough. This is the case for \(E\) supersingular (if \(\text{char}(\mathbb{F}_q)\) divides the trace of the Frobenius endomorphism). Later \textit{G. Frey} and \textit{H.-G. Ruck} (FR) [Math. Comput. 62, 865--874 (1994; Zbl 0813.14045)] gave another reduction algorithm based on the Tate pairing. The condition needed for the MOV algorithm to be subexponential is the same as for the FR algorithm except for elliptic curves for which the trace of the Frobenius is two; see \textit{N. Kanayama, T. Kobayashi, T. Saito} and \textit{S. Uchiyama} [IEICE Trans. Fundamentals, E83-A, No. 1, 17--22 (2000)] (that paper also provides a reduction algorithm for the ECDLP over trace two elliptic curves that differ from a simple realization of the FR algorithm). As the author says: \`\` The purpose of the paper is to bridge the gap between the MOV reduction and the FR reduction.'' To do so, he uses a generalization of the Weil pairing; see \textit{I. F. Blake, G. Seroussi} and \textit{N. P. Smart} [Elliptic curves in cryptography. (London Mathematical Society, Lect. Notes Ser. 265, Cambridge University Press) (1999; Zbl 0937.94008)] that is reviewed in section 2 of the paper. Then the paper shows how to construct an isomorphism between the group \(\langle P\rangle\subset E(\mathbb{F}_q)\), \(\#(P)=r\), \(r\) prime, and the group \(\mu_r\) of \(r\)th roots of unity. This gives an efficient reduction for elliptic curves with trace \(t\equiv 2 \bmod r\)\, (for the groups \(\langle P\rangle\) of interest in cryptography in fact \(t=2\)).