一類(lèi)新的最優(yōu)雙線性對(duì).pdf

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

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

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

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

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

6、橢圓曲線除Frobcnius映射外無(wú)其它可有效訃算的自同態(tài)映射,則任意非退化的雙線性對(duì)至少需要r1/ψ(k)南次Miller迭代。Hess[14]證明了這個(gè)猜想,進(jìn)而也證明了最優(yōu)對(duì)觀點(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對(duì)的m

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

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

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