Presentation 1998/7/31
A Note on the Discrete Logarithm Problem on Elliptic Curves of Trace Two
Shigenori UCHIYAMA, Taiichi SAITOH,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) To the best of our knowledge, there are few effective algorithms that solve the elliptic curve discrete logarithm problem. More precisely, Menezes, Okamoto and Vanstone [6] showed that if E is a supersingular elliptic curve defined over a finite field F, then the discrete logarithm problem over E can be efficiently reduced to the discrete logarithm problem over the multiplicative subgroup of an extension of F by using the Weil pairing, the so-called MOV reduction. By using a variant of the Tate pairing, Frey and Ruck [2] gave a generalization of this for discrete logarithms over the divisor class groups of curves. We call this reduction the FR reduction. Recently, Semaev [10], Smart [13], and Satoh and Araki [9] showed that if E is an anomalous elliptic curve defined over a prime finite field F, then the discrete logarithm problem over E can be efficiently reduced to the additive group F. In this paper, we compare the effectiveness of the MOV reduction and that of the FR reduction. More precisely, this paper shows that the effectiveness of the MOV reduction is the same as that of the FR reduction for all curves except elliptic curves o f trace two, i. e., elliptic curves of trace two are the only curves where the FR reduction is effective but the MOV reduction is not effective. We then propose an explicit reduction algorithm for the discrete logarithm problem over elliptic curves of trace two by using a different pairing from that with the FR reduction.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) Elliptic Curve / Discrete Logarithm Problem / MOV reduction / supersingular / anomalous
Paper # ISEC98-27
Date of Issue

Conference Information
Committee ISEC
Conference Date 1998/7/31(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To Information Security (ISEC)
Language ENG
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) A Note on the Discrete Logarithm Problem on Elliptic Curves of Trace Two
Sub Title (in English)
Keyword(1) Elliptic Curve
Keyword(2) Discrete Logarithm Problem
Keyword(3) MOV reduction
Keyword(4) supersingular
Keyword(5) anomalous
1st Author's Name Shigenori UCHIYAMA
1st Author's Affiliation NTT Laboratories()
2nd Author's Name Taiichi SAITOH
2nd Author's Affiliation Research Project of Info-communication Security
Date 1998/7/31
Paper # ISEC98-27
Volume (vol) vol.98
Number (no) 228
Page pp.pp.-
#Pages 7
Date of Issue