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   Vol.E83-A   No.4   pp.756-763
Publication Date: 2000/04/25
Online ISSN: 
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)>>
Buy this Article

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.