Some New Optimal Pairings

Since elliptic curves cryptography(ECC) was introduced by Koblitz [1] and Miller [2], it was valued gradually by many researcher of cryptanalysis. In 2000, Sakai et al. [3] proposed an ID-based key agreement protocol using the bilinear pairing, then pairing-based cryptosystems arc becoming one of the most attractive research areas in elliptic curve cryptography. Other examples are Boneh and Franklin's Identity Based Encryption scheme [4] and Joux's three-party key agreement [5].There are two problems for implementing paring-based cryptosystems. The one is that the pairing-friendly elliptic curves required to implement pairing-based systems must have certain properties that embedding degree is small and the prime-order subgroup is large. Randomly generated elliptic curves are unlikely to have these properties. To this end it is important that it should be easy to find such pairing-friendly elliptic curves for all kinds of applications and all desired levels of security. In recent years, the interest is to explore various methods of constructing pairing-friendly ellip-tic curves with prescribed embedding degrees. Freeman [6] had given the precise definition of pairing-friendly curves and gathered all of the existing constructions of pairing-friendly elliptic curves. He made a distinction be-tween methods that construct individual curves and those that construct parametric families of curves.The other one is to compute the bilinear paring more efficiently. The most common cryptographic pairings used in applications are the Weil and the Tate pairings on elliptic curves over finite fields. In terms of efficiency it is generally accepted that the Tate pairing is superior to the Weil pair-ing. The Tate pairings can be evaluated in polynomial time by Miller's algorithm. There are many methods to improve the computation of bilin-ear pairings, including changing the base in Miller's algorithm, replacing divisors by points, etc. One important aspect of research is focused on op-timizing the computation by shortening the iteration in Miller's algorithm. Inspired by the Duursma-Lee method for some special supersingular curves in [8], Barreto et al. [9] introduced the Eta pairing which has a half length of Miller loop compared to the original Tate pairing on supersingular abelian varieties. Later, Hess et al. [10] suggested the Ate pairing which shortens the length of Miller loop obviously on ordinary elliptic curves. Matsuda et al. [11] optimize the Ate pairing and the twisted Ate pairing and show that both them are always at least as fast as the Tate pairing. The length of the Miller loop in the Ate pairings depends on the value of trace of Frobenius t modulo the subgroup order r. Zhao et al. [12] suggested the Atei pair-ings which has been one of the fastest pairings till now. Vercauteren [13] introduced the notion of optimal pairings which by definition attains the lower bound and conjectured that any non-degenerate pairing on an elliptic curve without extra efficiently computable endomorphisms different from Frobenius requires at least (?) basic Miller iterations. Hess [14] proved this conjecture and thereby justified the term of optimal pairing.Denote withÏ€q the Frobenius endomorphism, i.e,Ï€q:Eâ†'E:(x, y) (xq,yq). Define G1= E[r]∩Ker(Ï€q-[1])= E(Fq)[r], G2=E[r]∩Ker(Ï€q-[q]). Consider a fixed power m∈Z of Tate pairing on G2×G1, t(Q,P)m=fr,Q(P)(?)=fmr,Q(P)(?) Since the Tate pairing is nondegenerate, the right hand side of function also define a nondegenerate pairing for any m∈Z with r (?) m. The main idea is then to find a nice multiple of r such that the evaluation fmr,Q(P) can be written as a power of the evaluation of a simpler function fλ,q(P).For Ate pairing, letλ≡T≡q≡t - 1 mod r and m= (?), the reduced Ate pairing aλ:G2×x G1â†'ur:(Q, P)â†'fλ,Q(P)(?) defines a bilinear pairing which is nondegenerate for r (?) m. Zhao et al. [12] introduced the Atei pairing which generalizes the Ate pairing. For reduced Ate pairing, letλ= Ti=Ti= (t-1)i mod r(1< i< k). Atei can possibly shorten the Miller loop to be as small as r(?) on some special pairing-friendly curves with large value of Frobenius t. However, not all pairing-friendly curves have this property.In this paper, we generalize the Atei pairing further. According theory of Hess et al in [14], we define a new bilinear pairing called R-Ate; pairing by constructing a reasonable h(x). The precise proof is given, too. For R-Atei pairing, letλ=(?),aλnondegenerate if and only if mkTk-1≠((qk-1)/r)·(?) mod r. i=0 By our method, we can shorten the the Miller loop to be nearly r(?) on some pairing-friendly curves in [6], while the Ate; pairing can not reach. For all the curves in [6], we have all reached the ideal lower bound r(?).This paper is organized as follows. Chapter 1 recalls some basic facts about elliptic curves, variants of pairings. Miller algorithm and pairing lat-tice. Chapter 2 generalizes the Ate; pairing further, proposes a new variant of Ate pairing which is called R-Ate; pairing, and gives its precise proof, then shows how to choose the optimal parameter of the R-Ate; pairing for fast pairing computation. In chapter 3, we apply our method on some pairing-friendly curves. And for these curves, the shortest Miller loop of the new constructed pairing can reach the lower bound r(?). Furthermore, compar-isons of the optimal T; of Atei pairing and the optimal T* of R-Atei pairing for these curves are given.