New Concrete Relation between Trace, Definition Field,and Embedding Degree*

摘要

A pairing over an elliptic curve E/F_pm to an extension field of F_pmk has begun to be attractive in cryptosystems, from the practical and theoretical point of view. From the practical point of view, many cryptosystems using a pairing, called the pairing-based cryptosystems, have been proposed and, thus, a pairing is a necessary tool for cryptosystems. From the theoretical point of view, the so-called embedding degree k is an indicator of a relationship between the elliptic curve Discrete Logarithm Problem (ECDLP) and the Discrete Logarithm Problem (DLP), where ECDLP over E(F_pm) is reduced to DLP over F_pmk by using the pairing. An elliptic curve is determined by mathematical parameters such as the j-invariant or order of an elliptic curve, however, explicit conditions between these mathematical parameters and an embedding degree have been described only in a few degrees. In this paper, we focus on the theoretical view of a pairing and investigate a new condition of the existence of elliptic curves with pre-determined embedding degrees. We also present some examples of elliptic curves over 160-bit, 192-bit and 224-bit F_pm with embedding degrees k < (log p)~2 such as k = 10,12,14,20,22,24,28.