The generalized Weil pairing and the discrete logarithm problem on elliptic curves

DOI10.1016/J.TCS.2003.06.002MaRDI QIDQ596141zbMATH OpenOpenAlexFDO

Authors Theodoulos Garefalakis

Publication date 10 August 2004

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2003.06.002

zbMATH Keywords

cryptography elliptic curves Weil pairing, discrete logarithm problem

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Elliptic curves (14H52) Cryptography (94A60)

Review text

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\)).

Recommendations

Cites work

Cited in

(8)

This page was built for publication: The generalized Weil pairing and the discrete logarithm problem on elliptic curves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q596141)