Comparing the MOV and FR Reductions in Elliptic Curve Cryptography

摘要

This paper addresses the discrete logarithm problem in elliptic curve cryptography. In particular, we generalize the Menezes, Okamoto, and Vanstone (MOV) reduction so that it can be applied to some non-supersingular elliptic curves (ECs); decrypt Frey and Rueck (FR)'s idea to describe the detail of the FR reduction and to implemnet it for actual elliptic curves with finite fields on a practical scale; and based on them compare the (extended) MOV and FR reductions from an algorithmic point of view. (This paper has primarily an expository role.)