On Fast Computation Of Bilinear Pairings

Identity-based cryptography is an active research area in modern cryptography. It has re-duced the complexity of certificate management of the certificate authority in public-key cryp-tosystem. Currently, many identity-based protocols use the bilinear pairing on elliptic curves.To make these protocols practical, the elliptic curves which are suitable for pairing applicationmust have some specially properties.(1) For the security of the cryptosystem, it requires thatthe elliptic curve has a subgroup of large prime order and the extension field which the bilinearpairing maps to is large enough;(2) For the efciency of the cryptosystem, it requires the ex-tension field which the bilinear pairing maps to must be small enough. In order to meet theserequirements, it requires the selected elliptic curves must have suitable embedding degree.The embedding degree of supersingular elliptic curves is≤6. Because of the simplicityof the group structure of supersingular elliptic curve, it may be vulnerable. To improve thesecurity level, we turn to ordinary elliptic curve. However, ordinary elliptic curves with smallembedding degree are very rare. They are hard to be found by randomly selection. So it needsto design special method to construct these curves. The composition of rational polynomialand cyclotomic polynomial which is factorable plays an important role in constructing ordinaryelliptic curve with small embedding degree. But these rational polynomials distribute sparsely.In identity-based cryptosystem, the computation of bilinear pairing plays a key role inthe performance of the cryptosystem. Usually, it uses Miller’s algorithm to compute bilinearpairing. In Miller’s algorithm many operations are done in extension field. To improve theefciency, it must reduce the number of multiply operation and inversion operation in extensionfield.This paper discusses constructing the composition of rational polynomial and cyclotomicpolynomial which is factorable, fast computation of Tate pairing and parallel computation ofTate pairing. The main results of this paper are as follows.(1) We give the sufcient and necessary condition for the reducibility of the composition ofrational polynomial and cyclotomic polynomial. Based on this sufcient and necessarycondition, we present a method to construct composition of rational polynomial and cyclo-tomic polynomial which is reduceable. It constructed a simple extension of the cyclotomicfield and used the primitive element theorem to generate the polynomial with desired prop-erty. This method can construct all polynomials which satisfy the special condition.(2) We analysis the property of loop control polynomial in Miller’s algorithm. Based on thisresult, we give a method to select elliptic curve parameters when constructing pairing-friendly elliptic curves. (3) In order to improve the performance of the Tate pairing computation method which isbased double-base chain, we use new Miller formula. It reduced the number of doublingoperation and tripling operation evidently. Compared with the original method, it has again about23%.(4) We present a method to speed up the computation of Tate pairing by constructing ellipticcurve with a subgroup whose order is a proth form prime. It reduced the number of additionoperation in Miller’s algorithm. By the same time, it has not lower the hamming weight ofthe subgroup order which guarantees the security level.(5) We extend the right-to-left binary method to pairing computation. Using the right-to-leftstructure in Miller’s algorithm, the addition operation and the doubling operation in thesame loop are uncorrelated. Thus it can use two cores of the multi-core processor to com-pute Tate pairing parallelly.(6) By decomposing the loop controlling parameter in Miller’s algorithm, we split the Millerformula into three uncorrelated parts. Then these parts can be computed by three diferentcores of multi-core processor. To balance the computational load between cores, we taketwo approaches: one is using the efciently computable endomorphism on elliptic curve,the other is using precomputation.