| 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 | |