For Full-Text 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 Menezes-Okamoto-Vanstone (MOV) Reduction Efficiently for Ordinary Elliptic Curves
Junji SHIKATA Yuliang ZHENG Joe SUZUKI Hideki IMAI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/04/25
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Information Security
elliptic curve cryptography, elliptic curve discrete logarithm problem, Menezes-Okamoto-Vanstone (MOV) algorithm, supersingular elliptic curves, ordinary elliptic curves,
Full Text: PDF(458KB)>>
The problem we consider in this paper is whether the Menezes-Okamoto-Vanstone (MOV) reduction for attacking elliptic curve cryptosystems can be realized for genera elliptic curves. In realizing the MOV reduction, the base field Fq 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 q-1, such a minimum extension degree is the minimum k such that l|qk-1, which is equivalent to the condition under which the Frey-Ruck (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 l-torsion 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 q-1 not only from the viewpoint of the minimum extension degrees but also from that of the effectiveness of algorithms.