自从Koblitz [1]和Miller [2]分别提出椭圆曲线加密技术(ECC)之后,它逐渐成为密码学一个重要的研究方向。同其它公钥密码技术相比,例如RSA以及离散对数,在相同安全强度的条件下,椭圆曲线所要求的密钥长度更短。2000年,Sakai等[3]提出了一种利用双线性对的基于身份的密钥协商协议。自此,基于双线性对的密码系统迅速成为椭圆曲线密码学的热门研究领域。著名的例子还有Baneh和Franklin[4]提出的基于身份的加密认证方案和Joux在[5]中提出的三方密钥协议等。基于双线性对的密码系统的实现需要解决两个问题。问题一是：在给定的应用要求和安全强度要求下,如何能有效快速地找到满足适用条件的椭圆曲线。这种密码系统需要一类特殊的椭圆曲线,称之为对友好椭圆曲线,及拥有大的素数阶子群和小的嵌入次数的曲线,而随机构造出的曲线不一定具有该特殊性质。近年来,大量的研究致力于在给定的嵌入次数k时如何有效地构造对友好椭圆曲线。Freeman在[6]中给出了对友好椭圆曲线这一概念的明确定义,并对现存的对友好椭圆曲线的构造方法进行了总结,将其区分为单个对友好椭圆曲线的构造和参数化对友好椭圆曲线族的构造两类。问题二是如何更加快速而有效地计算双线性对。一般的双线性对为Weil对和Tate对。两者相比较而言,由于Tate对的效率较高,实际中应用得较多。Tate对可利用Miller算法在多项式时间内计算得出。有许多技术可以提高Miller算法的计算效率,包括利用曲线定义域的特殊性质来简化扩域Fqk上点的运算,改变Miller算法的群展开的基(一般选择基为2),用曲线的点来代替除子,选择汉明重量低的素数阶子群,利用扭映射来消除v(Q)项等。其中一个重要的研究方向是缩短Miller算法的迭代次数。Duursma-Lee技术[8]可有效提高形如y2=xp-x+d的椭圆曲线上双线性对的计算效率,Barreto[9]引入了Eta对,将该技术扩展到超奇异椭圆曲线中,可将Miller迭代次数缩短近一半。不久,Hess[10]等提出了Ate对,在普通椭圆曲线上可有效缩短Miller算法的迭代次数。Matsuda等[11]优化了Ate对和扭Ate对,指出其计算效率至少和Tate对相同。Ate对的Miller迭代次数取决于曲线的迹t在模素数阶子群r后的大小。Zhao等[12]提出了Atei对,进一步推广了Ate对,Atei对是目前计算效率最高的双线性对之一。Vercauteren [13]引入了最优对的观点,其定义为迭代次数达到下界r1/(φ(k))的双线性对,并猜想：如果椭圆曲线除Frobenius I映射外无其它可有效计算的自同态映射,则任意非退化的双线性对至少需要r(1/φ(k))次Miller迭代。Hess[14]证明了这个猜想,进而也证明了最优对观点的合理性。令πq代表Frobenius自同态,及πq：E→E：(x,y)→(xq,yq).令G1=E[r]∩Ker(πq-[1])=E(Fq)[r],G2=E[r]∩Ker(πq-[q]).考虑G2×G1上的Tate对的m(m∈Z)次幂,t(Q,P)m=fr,Q(P)(m(qk-1))/r=fmr,Q(P)(qk-1)/r.由于Tate对是非退化的,则当m∈Z且r(?)m时,等式右边也是非退化的。对双线性对的改进的一种思想是使fmr,Q(P)的计算可以转化为较简单函数fλ,Q(P)的幂次来计算。对于Ate对而言,令λ=T≡q≡(t-1)mod r,m=(λk-1)/r,则当且仅当r(?)m时,约化的Ate对aλ：G2×G1→μr：(Q,P)→fλ,Q(P)(qk-1)/r定义了一个非退化的双线性对。Zhao等[12]提出了Atei对,对Ate对进行了推广,对于约化的Atei对而言,则相当于令λ=Ti=Ti(t-1)imod r,(1≤i<k).Atei对在一些特殊的对友好椭圆曲线上达到了最优的复杂度r(1/φ(k))，但并非所有的曲线上都能达到。本文根据Hess理论[14],通过构造满足要求的多项式h(x),构造了一类新的双线性对,称之为R-Atei对,并给出了具体的证明。对于R-Atei对而言,相当于λ=∑il=0ciTi,(1≤l<k),当且仅当mkTk-1≠((qk-1)/r)·(?)iciTi-1 mod(?)时,R-Atei对是非退化的。R-Atei对是对Atei对的进一步推广。并且我们将R-Atei对应用到[6]中的一些经典的对友好椭圆曲线族上,对所有的实例,R-Atei对均达到了最优的复杂度r1/(φ(k))本文章节安排如下,第一章介绍椭圆曲线的基础知识,包括除子理论,几类主要的双线性对,Miller算法介绍和对格。第二章介绍新构造的最优双线性对R-Atei对及其严格的理论证明。第三章将R-Atei对运用到[6]中经典的对友好椭圆曲线族中,并给出了复杂度分析。