The generalized Weil pairing and the discrete logarithm problem on elliptic curves
type: Item
instance of: scholarly article
title: The generalized Weil pairing and the discrete logarithm problem on elliptic curves
zbMATH Open document ID: 1057.94018
author: Theodoulos Garefalakis
published in: Theoretical Computer Science
publication date: 2004-08-10T00:00:00Z
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\)…
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 14H52
zbMATH DE Number: 2085535
zbMATH Keywords: elliptic curves
zbMATH Keywords: Weil pairing, discrete logarithm problem
zbMATH Keywords: cryptography
reviewed by: Juan Tena Ayuso
MaRDI profile type: Publication
full work available at URL: j.tcs.2003.06.002
OpenAlex ID: W2122177483
cites work: Q4847920
cites work: Q4341740
cites work: Function field sieve method for discrete logarithms over finite fields
cites work: Q4409129
cites work: Q4265362
cites work: Computing Logarithms in Finite Fields of Characteristic Two
cites work: Q4783728
cites work: Q4474196
cites work: Fast evaluation of logarithms in fields of characteristic two
cites work: The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems
cites work: A Remark Concerning m-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves
cites work: Q4737495
cites work: The index calculus method using non-smooth polynomials
cites work: Discrete Logarithms in $GF ( P )$ Using the Number Field Sieve
cites work: Comparing the MOV and FR Reductions in Elliptic Curve Cryptography
cites work: Elliptic Curve Cryptosystems
cites work: Q3360980
cites work: Reducing elliptic curve logarithms to logarithms in a finite field
cites work: Q3718617
cites work: Q3808150
cites work: Q3710637
DOI: 10.1016/J.TCS.2003.06.002
Recommended article: Q3149772
Recommended article: Q3044320
Recommended article: Q4314052
Recommended article: The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems
Recommended article: Q4502490
Recommended article: Comparing the MOV and FR Reductions in Elliptic Curve Cryptography
Recommended article: Q2998505
Recommended article: Summation Polynomial Algorithms for Elliptic Curves in Characteristic Two
Recommended article: Q2724449
Recommended article: Algorithms and Computation
description: scientific article; zbMATH DE number 2085535