
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Realizing the MenezesOkamotoVanstone (MOV) Reduction Efficiently for Ordinary Elliptic Curves
Junji SHIKATA Yuliang ZHENG Joe SUZUKI Hideki IMAI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E83A
No.4
pp.756763 Publication Date: 2000/04/25 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: PAPER Category: Information Security Keyword: elliptic curve cryptography, elliptic curve discrete logarithm problem, MenezesOkamotoVanstone (MOV) algorithm, supersingular elliptic curves, ordinary elliptic curves,
Full Text: PDF(458KB)>>
Summary:
The problem we consider in this paper is whether the MenezesOkamotoVanstone (MOV) reduction for attacking elliptic curve cryptosystems can be realized for genera elliptic curves. In realizing the MOV reduction, the base field F_{q} is extended so that the reduction to the discrete logarithm problem in a finite field is possible. Recent results by Balasubramanian and Koblitz suggest that, if l q1, such a minimum extension degree is the minimum k such that lq^{k}1, which is equivalent to the condition under which the FreyRuck (FR) reduction can be applied, where l is the order of the group in the elliptic curve discrete logarithm problem. Our point is that the problem of finding an ltorsion point required in evaluating the Weil pairing should be considered as well from an algorithmic point of view. In this paper, we actually propose a method which leads to a solution of the problem. In addition, our contribution allows us to draw the conclusion that the MOV reduction is indeed as powerful as the FR reduction under l q1 not only from the viewpoint of the minimum extension degrees but also from that of the effectiveness of algorithms.

