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

A pairing over an elliptic curve E/F_ to an extension field of Fp_ 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_) is reduced to DLP over Fp_ 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_ with embedding degrees k < (log p)^2 such as k=10, 12, 14, 20, 22, 24, 28