一類新的最優(yōu)雙線性對.pdf

1、自從Koblitz[1]和Miller[2]分別提出橢圓曲線加密技術(shù)(ECC)之后,它逐漸成為密碼學(xué)一個重要的研究方向。同其它公鑰密碼技術(shù)相比,例如RSA以及離散對數(shù),在相同安全強(qiáng)度的條件下,橢圓曲線所要求的密鑰長度更短。2000年,Sakai等[3]提出了一種利用雙線性對的基于身份的密鑰協(xié)商協(xié)議。自此,基于雙線性對的密碼系統(tǒng)迅速成為橢圓曲線密碼學(xué)的熱門研究領(lǐng)域。著名的例子還有Baneh和Franklin[4提出的基于身份的加密認(rèn)證方案

2、和Joux在[5]中提出的三方密鑰協(xié)議等。
　　 基于雙線性對的密碼系統(tǒng)的實(shí)現(xiàn)需要解決兩個問題。問題一是:在給定的應(yīng)用要求和安全強(qiáng)度要求下,如何能有效快速地找劍滿足適用條件的橢圓曲線。這種密碼系統(tǒng)需要一類特殊的橢圓曲線,稱之為對友好橢圓曲線,及擁有大的素數(shù)階了群和小的嵌入次數(shù)的曲線,而隨機(jī)構(gòu)造出的曲線不一定具有該特殊性質(zhì)。近年來,大量的研究致力于在給定的嵌入次數(shù)k時如何有效地構(gòu)造對友好橢圓曲線。Freeman在[6]中給出了對友

3、好橢圓曲線這一概念的明確定義,并對現(xiàn)存的對友好橢圓曲線的構(gòu)造方法進(jìn)行了總結(jié),將其區(qū)分為單個對友好橢圓曲線的構(gòu)造和參數(shù)化對友好橢圓曲線族的構(gòu)造兩類。
　　 問題二是如何更加快速而有效地計算雙線性對。一般的雙線性對為Well對和Tate對。兩者相比較而言,由于Tare對的效率較高,實(shí)際中應(yīng)用得較多。Tate對可利用Miller算法在多項(xiàng)式時間內(nèi)計算得出。有許多技術(shù)可以提高M(jìn)iller算法的計算效率,包括利用曲線定義域的特殊性質(zhì)來簡化

4、擴(kuò)域Fqk上點(diǎn)的運(yùn)算,改變Miller算法的群展開的基(一般選擇基為2),用曲線的點(diǎn)來代替除子,選擇漢明重量低的素數(shù)階子群,利用扭映射來消除v(Q)項(xiàng)等。其中一個重要的研究方向是縮短Miller算法的迭代次數(shù)。Duursma-Lee技術(shù)[8]可有效提高形如y2=xp-x+d的橢圓曲線上雙線性對的計算效率,Barreto[9]引入了Eta對,將該技術(shù)擴(kuò)展到超奇異橢圓曲線中,可將Alillcr迭代次數(shù)縮短近一半。不久,Hess[10]等提出

5、了Ate對,在普通橢圓曲線上可有效縮短Miller算法的迭代次數(shù)。Matsuda等[11]優(yōu)化了Ate對和扭Ate對,指出其計算效率至少和Tate對相同。Ate對的Miller迭代次數(shù)取決于曲線的跡t在模素數(shù)階子群r后的大小。Zhao等[12]提出了Atei對,進(jìn)一步推廣了Ate對,Atei對是目前計算效率最高的雙線性對之一。Vercauteren[13]引入了最優(yōu)對的觀點(diǎn),其定義為迭代次數(shù)達(dá)到下界r1/ψ(k)的雙線性對,并猜想:如果

6、橢圓曲線除Frobcnius映射外無其它可有效訃算的自同態(tài)映射,則任意非退化的雙線性對至少需要r1/ψ(k)南次Miller迭代。Hess[14]證明了這個猜想,進(jìn)而也證明了最優(yōu)對觀點(diǎn)的合理性。
　　 令πq代表Frobenius自同態(tài),及πq:E→E:(x,y)→(xq,yq).令G1=E[r]∩Ker(πq-[1])=E(Fq)[r],G2=E[r]∩ Ker(πq-[g]).
　　 考慮G2×G1上的Tate對的m

7、(m∈Z)次冪,t(Q,p)m=fr,Q(P)m(qk-1)/r=fmr,Q(P)qk-1/r.
　　 由于Tate對是非退化的,則當(dāng)m∈Z且r(|)m時,等式右邊也是非退化的。對雙線性對的改進(jìn)的一種思想是使fmr,Q(P)的計算可以轉(zhuǎn)化為較簡單函數(shù)fλ,Q(P)的冪次來計算。對于Ate對而言,令λ=T≡q≡(t-1)mod r,m=λk-1/r,則當(dāng)且僅當(dāng)r(|)m時,約化的Atc對aλ:G2×G1→μr:(Q,P)H→fλ,

8、Q(P)qk-1/r定義了一個非退化的雙線性對。Zhao等[12]提出了Atci對,對Ate對進(jìn)行了推廣,對于約化的Atei對而言,則相當(dāng)于令λ=Ti=(t-1)imod r,(1≤I＜k).Atei對在一些特殊的對友好橢圓曲線上達(dá)到了最優(yōu)的復(fù)雜度r1/ψ(k),但并非所有的曲線上都能達(dá)到。
　　 本文根據(jù)Hess理論[14],通過構(gòu)造滿足要求的多項(xiàng)式h(x),構(gòu)造了一類新的雙線性對,稱之為R-Atei對,并給出了具體的證明。對

9、于R-Atei對而言,相當(dāng)于λ=∑li=0ciTi,(1≤l＜k),當(dāng)且僅當(dāng)mkTk-1≠((qk-1)/r)·∑iciTi-1i=0 mod r時,R-Atei對是非退化的。R-Atei對是對Atei對的進(jìn)一步推廣。并且我們將R-Atei對應(yīng)用到[6]中的一些經(jīng)典的對友好橢圓曲線族上,對所有的實(shí)例,R-Atei對均達(dá)到了最優(yōu)的復(fù)雜度r1/ψ(k).
　　 本文章節(jié)安排如下,第一章介紹橢圓曲線的基礎(chǔ)知識,包括除予理論,幾類主要的