Realizing the Menezes-Okamoto-Vanstone (MOV) Reduction Efficiently for Ordinary Elliptic Curves
スポンサーリンク
概要
- 論文の詳細を見る
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 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 ⫮q-1, such a minimum extension degree is the minimum k such that l∖q^k -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.
- 社団法人電子情報通信学会の論文
- 2000-04-25
著者
-
Zheng Y
Univ. North Carolina Charlotte Nc Usa
-
Zheng Yuliang
Department Of Software And Information Systems
-
Shikata Junji
Graduate School Of Environment And Information Sciences Yokohama National University
-
IMAI Hideki
The author is with Institute of Industrial Sience, the University of Tokyo
-
Imai H
Research Center For Information Security (rcis) National Institute Of Advanced Industrial Science An
-
Imai Hideki
3rd Department Institute Of Industrial Science The University Of Tokyo
-
Shikata J
The Graduate School Of Environment And Information Sciences Yokohama National University
-
Shikata Junji
The Authors Are With The Institute Of Industrial Science The University Of Tokyo
-
ZHENG Yuliang
The author is with the School of Network Computing, Monash University
-
SUZUKI Joe
The authors are with the Graduate School of Science, Osaka University
-
Suzuki Joe
The Authors Are With The Department Of Mathematics Graduate School Of Science Osaka University
-
Suzuki Joe
The Authors Are With The Graduate School Of Science Osaka University
関連論文
- 非超特異楕円曲線に対するMOVアルゴリズムの実現(2)
- Information Theoretical Secure Oblivious Polynomial Evaluation : Model, Bounds and Constructions
- On Non-Pseudorandomness from Block Ciphers with Provable Immunity Against Linear Cryptanalysis (Special Section on Cryptography and Information Security)
- On Strictly Geometrically Uniform Codes: Construction and New Codes
- 情報量的安全性に基づく暗号化方式について
- Unconditionally Secure Group Signatures
- An Algorithm for Cryptanalysis of Certain Keystream Generators Suitable for High-Speed Software and Hardware Implementations : Special Section on Cryptography and Information Security
- A Novel Fast Correlation Attack Suitable for Simple Hardare Implementation
- Discussions on Unconditionally Secure VSS Robust against Dishonest Majority
- Discussions on Unconditionally Secure VSS Robust against Dishonest Majority