Construction Of Pairing-friendly Elliptic Curves And The Research Of Optimal Pairings On Them

In 1985, (?)eal Koblitz and Victor Miller proposed elliptic curves cryp-tography independently. The security of the cryptography algorithm is de-pended on the discrete logarithm problem in the point group of elliptic curves. The method to selove this problem, which was proposed by Pohig and Hellman, had complexity of (?), and r was the order of the point group of elliptic curves. When r is big, this method is computationally infeasible. In 1993, Menezes, Okamoto and Scott [6] had reduced the discrete logarithm problem in point group of elliptic curves to discrete logarithm problem in multiplication group of finite field. It is computationally infeasible, when embedding degrees are big. In 2000. D.Boneh and M.Franklin [16] proposed identity-based encryption. In 2001. D.Boneh. B.Lynn and H.Shacham [17] proposed short signatures. From now on, pairing based cryptography ba-come a major area of research in public key cryptography. All cryptographies need fast algorithms to compute bilinear pairing. So the embedding degrees need to be small.To apply these cryptographies, the elliptic curves, on which the cryp-tography satisfy the security and the bilinear pairings can be computed fast, need to be constructed. This curves with small embedding degree and large prime-order subgroup are called "pairing-friendly". They are rare and re-quire specific constructions. Freeman [9] gave two parameters to measure pairing-friendly elliptic curves:1. the embedding degree, k, which is not too big or too small.2.(?)= log q/log r. which measures the field size relative to the size of the prime-order subgroup on curve. It is the closer to 1 the bet-ter. When CM method [3] is used to construct elliptic curves. one only need q, r, t that satisfy the CM equation as the input of CM algorithm. Brezing and Weng [7] got q(χ),r(χ).t.(χ) in the cycloto(?)ii(?) field and used them as the input of CM method. They have gotten the family of elliptic curvesIn this paper, we improve the Brezing-Weng method. We find that there are some spacial properties of cyclotoinic polynomials when k = 3, 6,2l. We get the following result -D passes the test of r(χ). which is a new defiantion that is proposed in this paper. We get a new method to construct family of elliptic curves.Prof. Wang.[13] got the equvalent condition between general bilinear pairings and optimal pairings. In this paper, we generalized it on the family of elliptic curves and got the following theorem.Theorem:r(χ),s(x) are polynomials in Z[χ].hx(t)∈Z[χ][t] and its degree is less thanφ(k) - 1.hχ(s) (?) 0 mod r,hχ(s)(?) 0 mod r2.as,h is an optimal pairing.if there is only one efficient polynomial hi(χ), which degree is not zero.and deg(hi;(χ))= 1/(?)(k) deg(r(x)).We used it to get the optimal pairing on the pairing-friendly elliptic curves.