Miyaji Laboratory

Over the past few years there has been an interest in pairing-based cryptography. A pairing is a function which is a map from a subgroup of $E (\Fq)$ to a multiplicative ring of extension field of a defined field $\Fq$. The degree of extension field is called an embedding degree. This value is very important to construct an efficient pairing-based. Since we have to compute a pairing value in $\f _{q^k}^*$, it is necessary to construct an elliptic curve with prescribed embedding degree which satisfy security level and efficiency. It is known that an embedding degree become large in proportion to the size of defined field. As practical cryptosystems request a size of defined field for $160$ bits, embedding degree become very large in high probability. So it is desired to construct an elliptic curve with an embedding degree which can be computed easily and satisfy a security level.

The way to construct an elliptic curve, which has prime order and a desired embedding degree, is only known when the embedding degree is $3,4,6,10,12$. Pairing-Friendly curves of prime order are absolutely essential in Pairing-Based Cryptosystems with longer useful life.

In this paper we describe a property of splitting of polynomials and application to a Pairing-Friendly cryptosystems.