王 輩, 胡紅鋼

中國科學(xué)技術(shù)大學(xué)信息科學(xué)技術(shù)學(xué)院中國科學(xué)院電磁空間信息重點實驗室, 合肥 230027

1 引言

橢圓曲線理論在數(shù)論發(fā)展史上占有濃墨重彩的一筆, 如懷爾斯利用橢圓曲線給出了費馬大定理的證明. 其在應(yīng)用學(xué)科—密碼學(xué), 也是一個將抽象數(shù)學(xué)應(yīng)用到實際中的最閃亮的范例, 如橢圓曲線密碼體制. 此后, 橢圓曲線在密碼學(xué)上的應(yīng)用便開始層出不窮. 從學(xué)術(shù)的角度說, 橢圓曲線對密碼學(xué)的一大貢獻(xiàn)在于它提供了一個用途廣泛的數(shù)學(xué)工具, 也就是具有一定安全屬性的雙線性映射—配對. 1993 年, Menezes 等人[1]利用Weil 對將橢圓曲線離散對數(shù)問題轉(zhuǎn)化到有限域上的離散對數(shù)問題, 也就是MOV 攻擊. 1999年, Frey[2]等人利用Tate 對給出了橢圓曲線離散對數(shù)的另一種約化, 即FR 約化. 除了配對在密碼分析的應(yīng)用外, Joux[3]利用雙線性對給出一輪三方密鑰交換協(xié)議. 然而, 正式將配對發(fā)揮重大作用的還要歸功于Shamir[4], 他在1984 年提出公鑰是否可以為任一字符串, 試圖構(gòu)造基于身份的公鑰密碼體制, 并提出了兩個公開問題: (1) 如何向眾多的可信第三方證明自己的身份; (2) 可信第三方如何安全地將用戶的私鑰送到用戶手中. 直到2001 年,Boneh 等人[5]利用Weil 對構(gòu)造出基于身份的密碼體制,才很好地解決了這兩個公開問題. 隨后, 其他基于身份的密碼體制也隨之產(chǎn)生, 如數(shù)字簽名[6,7]、(已認(rèn)證) 密鑰交換協(xié)議[8]、變色龍哈希[9]及其在或者不在隨機(jī)預(yù)言機(jī)下的層次擴(kuò)展[10,11]. 其他一些基于配對的方案不是基于身份的, 而是具有特殊功能, 例如秘密握手[12]、短/聚合/可驗證地加密/組/環(huán)/盲簽名[13–17]和簽密[18–20].

目前, 計算配對的算法主要有Miller 算法[21]和橢圓網(wǎng)算法[22], 相比之下, Miller 算法的計算效率較高且適應(yīng)范圍更廣泛. Miller 算法的主要過程就是計算Miller 函數(shù)fr,P, 其中r影響著算法的迭代次數(shù).由于配對的廣泛應(yīng)用, 配對的計算效率需要不斷地提高. 研究者們開始從各個角度對此展開研究, 主要分為兩大方向: 一是利用理論與算法的工具來改善Miller 算法, 如分母約化技術(shù)、選定梅森素數(shù)作為r等;二是構(gòu)造新的更快速的配對, 如構(gòu)造迭代次數(shù)更少的配對. 本文第2 節(jié)按時間順序給出了配對的原始定義與改進(jìn)方案, 結(jié)合研究者們的研究成果介紹近二十年來配對的發(fā)展歷程. 第4 節(jié)簡單介紹了Miller 算法的改進(jìn)算法以及計算多重配對的最新改進(jìn)算法.

配對友好型曲線的構(gòu)造也是近些年的一大研究熱點, 其構(gòu)造思想需權(quán)衡配對的計算效率與安全性. 本文第四部分簡要地介紹了近些年配對友好型曲線的種類, 重點介紹幾類最流行的配對友好型曲線—BN 曲線、BLS 曲線和KSS 曲線. 一些國際標(biāo)準(zhǔn)組織在制定基于配對的密碼體制相關(guān)標(biāo)準(zhǔn)中[23–25], 這三類曲線總是占據(jù)主導(dǎo)位置. 我國國家密碼管理局在2016 年發(fā)布的SM9 標(biāo)識密碼算法, 其中使用的曲線是BN曲線. 目前實現(xiàn)雙線性對的一些代碼庫, 有miracl 庫[26]、mcl 庫、amcl 庫[27]、PBC 庫[28], relic 庫等.根據(jù)最新的文獻(xiàn)資料和構(gòu)造密碼方案期望達(dá)到的安全級別, 我們總結(jié)了以上三類曲線相應(yīng)參數(shù)的選取與參數(shù)長度, 以便底層實現(xiàn)的研究者們快速掌握相關(guān)數(shù)據(jù).

基于身份的密碼體制[5]是建立在雙線性Diffie-Hellman 假設(shè)之下, 此假設(shè)包括兩大困難問題—雙線性Diffie-Hellman 問題與雙線性Diffie-Hellman 判定性問題. 雙線性Diffie-Hellman 判定性問題強(qiáng)于Diffie-Hellman 計算性問題, 而Diffie-Hellman 計算性問題又強(qiáng)于離散對數(shù)問題. 由此可見, 解決這些問題是當(dāng)前數(shù)學(xué)界與密碼學(xué)界的研究熱點. 除這些問題外, 還有其他困難問題, 第5 節(jié)會具體給出它們的定義, 并簡要地介紹其困難程度和配對的安全性研究.

下面我們介紹配對相關(guān)理論中一些基本的符號:

2 橢圓曲線中的配對

橢圓曲線是一類虧格為1 的包含一個無窮遠(yuǎn)點∞的光滑曲線. 設(shè)定義在K上的橢圓曲線E滿足Weierstrass 方程

密碼學(xué)者們利用配對設(shè)計密碼體制時需要考慮使用哪一類配對以及配對的安全性參數(shù)等問題, Galbraith[31]給出了此三類配對的安全性比較. Abe 等人[32–34]就此三類配對給出了不同類型的結(jié)構(gòu)保存簽名算法. 下面,我們具體介紹橢圓曲線上的各種配對.

2.1 Weil 對

命題3E/K,f,g如命題1,2 所述,設(shè)S ∈E[r]是另一個r-扭點,那么對任意點X ∈E,g(X+S)r=f([r]X+[r]S)=f([m]X)=g(X)r. 從而,g(X+S)/g(X)∈μr.

由以上三個命題, 下面我們來給出Weil 對的一種定義.

定義2 設(shè)映射

這里選取X ∈E使得g(X+S) 和g(X) 都有定義且非零.

定理1[30]設(shè)E/K是橢圓曲線, 存在S,T ∈E[r] 使得er(S,T) 為r-次本原單位根. 特別地, 當(dāng)E[r]?E(K) 時, 有μr ?K.

在實際應(yīng)用中, 為方便Weil 對的計算, 我們一般采用下面的等價定義.

當(dāng)分母出現(xiàn)零時, 再重新選擇R,S, 重復(fù)操作直至計算出結(jié)果. 這里分母為零的可能性很小(發(fā)生的概率至多為O(logp/p)). 因此, 此表達(dá)式(4) 在很大的概率上是合理定義的.

命題4[30]設(shè)P,Q ∈E[r], 則ˉer(P,Q)=er(P,Q).

命題5[29]Weil 對具有如下性質(zhì):

· 雙線性, 非退化, 見定義1;

· 交互性:P ∈E[r], 滿足er(P,P)=1. 利用雙線性, 則有er(P,Q)=er(Q,P)-1;

· 相容性: 若P ∈E[rr′],Q ∈E[r], 則err′(P,Q)=er(r′P,Q);

· Galois 作用:P,Q ∈E[r],σ ∈Gal(ˉK/K), 則有er(P,Q)σ=er(Pσ,Qσ).

根據(jù)Weil 對的交互性, 當(dāng)Q=kP時, 總有ˉer(P,Q)=1, 從而在實用中并不安全. 密碼學(xué)上使用的Weil 對一般為改進(jìn)的Weil 對,具體定義為?er(P,Q)= ˉer(P,φ(Q)),可見文獻(xiàn)[5,35]. 其中φ ∈End(E)滿足φ(Q)∈＜P ＞,φ稱為distorsion 映射. 對于distorsion 映射的存在性, 可參見文獻(xiàn)[36,37]. Cheol[38]給出了Weil 對的一種改進(jìn)辦法: 對于改進(jìn)的Weil 對?er(P,Q), 當(dāng)φ為單射且可分時, 可以將擴(kuò)域上運(yùn)算約化到基域上處理, 從而加快了配對的計算. 特別地, 當(dāng)P=Q, ?er(P,P) 的計算可約化成Tate 對的形式(僅需一個Miller 函數(shù)fr,P) 且沒有指數(shù)步的計算.

2.2 Tate 對

Tate 對是另一類經(jīng)典的雙線性非退化的映射. 最早在1958 年由Tate 提出, 之后Lichtenbaum 做了進(jìn)一步的擴(kuò)充. 1994 年, Frey 和Rück[39]首先分析了任意阿貝爾簇的除子類群上的離散對數(shù), 利用Tate對將其約化到有限域或者局部域的剩余類域上的離散對數(shù). 1998 年, 他們[2]又給出了有限域上的橢圓曲線離散對數(shù)的約化. 下面我們僅給出橢圓曲線上Tate 對的定義與結(jié)論, 從它與Weil 對的關(guān)系出發(fā), 結(jié)合研究者的改進(jìn)方法一步步給出它的改進(jìn)定義.

一些研究者給出了Tate 對在其他曲線形式下的計算, 比如Jacobi Quadratic 曲線[42]、Edwards 曲線[43,44]、超橢圓曲線[45,46]. Duursma 和Lee 等人[45]在超橢圓曲線上提出了Tate 對的改進(jìn)辦法—減少迭代次數(shù), Barreto 等人[46]正是根據(jù)這個思想在超奇異橢圓曲線上構(gòu)造了新的配對—Eta 對, 它的計算效率比Tate 對的快. 在這之后, 新的配對大量涌現(xiàn), 但是總體上, 這些新的配對均是將Tate 對限制到某些特定子群上構(gòu)造的.

2.3 Eta 對與Ate 對

這里, 我們主要介紹兩個特殊的Tate 對, 現(xiàn)已被廣泛應(yīng)用與研究.

這里T=t-1,P,Q ∈E(Fq)[r]. 在一定的條件下, 此配對是非退化雙線性的. 當(dāng)r ≈#E(Fq) 時, Eta 對的迭代次數(shù)幾乎比Tate 對的的迭代次數(shù)少一半.

Eta 對的定義在一般橢圓曲線上并不適用, Hess 等人[47]進(jìn)一步將Eta 對擴(kuò)充到一般橢圓曲線上, 構(gòu)造了Ate 對與Twisted Ate 對. 下面, 我們分別給出它們的定義.

引理1[30]設(shè)E/Fq是橢圓曲線,r為大素數(shù)且滿足r| #E(Fq),k為與r對應(yīng)的嵌入次數(shù). 則E[r]?E(Fqk).

設(shè)πq是橢圓曲線E上的Frobenius 自同態(tài).πq的特征多項式為h(u) =u2-tu+q,h(u)≡(u-1)(u-q)modr, 則0≡(πq-1)(πq-q)modr.

引理2[40]πq在E[r] 上形成兩個特征子空間, 分別是1-特征子空間G1=E[r]∩ker(πq-[1]) =E(Fq)[r] 和q-特征子空間G2=E[r]∩ker(πq-[q])?E(Fqk)[r]. 很顯然,G1,G2是加法群且有E[r] =G1⊕G2.

Wang 等人[53]根據(jù)αtwist的定義, 通過Weierstrass 型曲線和Edwards 型曲線之間的映射關(guān)系在高次扭Weierstrass 曲線上定義了一個新的配對T-Ate 配對, 結(jié)合了Edwards 型曲線的快速點加倍點運(yùn)算和Weierstrass 型曲線的Miller 快速計算公式.

顯然, 當(dāng)t比較小時, Ate 對和扭Ate 對比Tate 對的計算要快. 但是, 并不是所有的配對友好型曲線都具有較小的跡t. 已知T ≡qmodr且r‖qk-1, 則r|Φk(T)(其中Φk為分圓多項式), 那么T的極小值為r1/φ(k)(φ為歐拉函數(shù)). 所以Ate 對的Miller 迭代次數(shù)的下界是log(r1/φ(k)). 對于一些配對友好型曲線, 這個下界是可以達(dá)到的, 如分圓類橢圓曲線[54,55]. Duan 等人[56]改進(jìn)了文獻(xiàn)[54] 中的方法, 當(dāng)k=2i·3 時, 構(gòu)造一類橢圓曲線滿足t ≈r1/φ(k). Lin[57]進(jìn)一步分析k=3i的情況, 構(gòu)造了t ≈r1/φ(k)的一類橢圓曲線并給出了k=9 時Ate 對的快速計算. 所以改進(jìn)Ate 對與扭Ate 對的主要研究方向就是使Miller 迭代次數(shù)盡量達(dá)到下界, 下面§2.4 節(jié)我們會給出這一研究方向的具體進(jìn)展. 由于改進(jìn)Ate 對的方法對扭Ate 對同樣適用, 下面我們僅針對Ate 對的研究作分析.

2.4 其它配對

Matsuda 等人[58]構(gòu)造了優(yōu)化Ate 對, 他們把T=t-1(≡qmodr) 換成任意的整數(shù)S ≡qmodr.這樣構(gòu)造的新的配對比Tate 對至少快兩倍. 文獻(xiàn)[59] 給出了優(yōu)化Ate 對在分圓類橢圓曲線上的計算, 文獻(xiàn)[60] 給出了優(yōu)化Ate 對的在BN 曲線上的快速實現(xiàn)算法. Zhao 等人[61]延續(xù)了Matsuda 等人的思想,繼續(xù)減少Miller 的迭代次數(shù), 構(gòu)造了廣義的Ate 對Atei, 定義如下.

定義9 設(shè)E/Fq是橢圓曲線,r為大素數(shù)且滿足r|#E(Fq). 設(shè)k為嵌入次數(shù)且T=t-1, 我們令Ti=Ti ≡qimodr,1≤i ≤k-1. Q ∈G2?E[r]∩ker(πq-[q]),P ∈G1=E[r]∩ker(πq-[1]). 廣義的Ate 對(Atei對) 定義如下:

同樣, 我們可以給出定義在G2×G1上的R-Ate 對RA,B(Q′,P′), 其中Q′∈G2,P′∈G1. 當(dāng)(A,B) =(qi,r) 時,RA,B(Q′,P′)=fTi,Q′(P′), 從而Atei對是特殊的R-Ate 對.

對一些之前不能達(dá)到下界的配對友好型曲線, 若在其上計算R-Ate 對, 它的迭代次數(shù)卻能達(dá)到下界log(r1/φ(k)). 而且文獻(xiàn)[64] 表明計算R-Ate 對比計算Atei對的整體消耗節(jié)省29%-69%. 結(jié)合Ate 對與幾類改進(jìn)的Ate 對, 在一些曲線上, 他們的迭代次數(shù)均可以達(dá)到下界. Vercauteren[63]將這些Miller迭代次數(shù)可以達(dá)到下界的配對命名為最優(yōu)配對(optimal pairing), 定義如下.

定義11 設(shè)e:G1×G2→GT是一個非退化雙線性配對, 并且|G1|=|G2|=|GT|=r, 其中GT定義在域Fqk上. 若配對的Miller 迭代次數(shù)≈log(r1/φ(k))+ε(k),ε(k)≤log(k), 則稱此配對e(·,·) 為最優(yōu)配對.

這個定義并不僅僅對于配對中只有一個Miller 函數(shù)的配對滿足要求, 例如Ate 對, 對于配對中有幾個Miller 函數(shù)的乘積或者線性組合, 其計算的總Miller 迭代次數(shù)也滿足要求, 例如R-Ate 對. 以上分析可知Ate 對及其改進(jìn)Ate 對在特定情形下可以成為最優(yōu)配對. 那么, Weil 對或者扭Ate 對, 他們會是最優(yōu)配對嗎? Vercauteren[63]給出了一個假設(shè): 除具有有效可計算自同態(tài)(Frobenius 自同態(tài)除外) 的橢圓曲線, 其上的任意非退化配對, 迭代次數(shù)均可達(dá)到下界log(r1/φ(k)). Hess 等人[65]證明了這個猜想, 證明的主要思想是將配對的Miller 函數(shù)表示為一系列次數(shù)較小的函數(shù)的乘積, 并利用格的相關(guān)工具證明了配對的迭代次數(shù)在理論上可以達(dá)到下界log(r1/φ(k)). 他們的結(jié)論對Weil 對、Ate 對和扭Ate 對均成立. 到目前為止, 最快的配對是最優(yōu)Ate 對(optimal Ate pairing), 而且在實際中被廣泛應(yīng)用.

自配對的定義首先由Lee[66]提出, 他在秩為2 的自由模上定義了自配對A×A →A, 并將其推廣到橢圓曲線上, 定義了E[r]×E[r]→E[r]. 這一類橢圓曲線上的自配對與Weil 對有很多相似的性質(zhì), 并且可以建立密鑰協(xié)商與數(shù)字簽名算法. 然而, 更常用的自配對是橢圓曲線上對于同一點的自配對es(P,P).事實上, 自配對就是在以往配對的基礎(chǔ)上再定義的配對, 如es(P,P) =e(P,φ(P))(自配對與Weil 對的關(guān)系). 文獻(xiàn)[67-69] 給出了自配對在橢圓曲線與超橢圓曲線上的快速計算. 值得一提的是, 相比Tate 對或者Ate 對的最終指數(shù)步計算, 自配對的指數(shù)步計算更快速. 這一類的自配對es(P,P) 目前在密碼學(xué)上應(yīng)用廣泛, 如短簽名[17]、在線/離線的簽名體制[70]、基于身份的Chameleon 的哈希方案[71].

本文所有配對的定義均是在橢圓曲線上討論的, 文獻(xiàn)[64,73-75] 給出了一些配對在超橢圓曲線上的定義. 相比較于橢圓曲線, 超橢圓曲線具有更豐富的自同態(tài)環(huán)結(jié)構(gòu), 能否利用其自同態(tài)環(huán)中的某些特別元素加快超橢圓曲線上的雙線性對有效計算或構(gòu)造具有更短Miller 鏈的雙線性對? 目前, 適于雙線性對的超橢圓曲線并不多, 如何構(gòu)造更多配對友好型超橢圓曲線值得進(jìn)一步研究.

3 配對友好型曲線及參數(shù)選取

關(guān)于求解變量(u,y) 的整數(shù)解. 參數(shù)化的配對友好型曲線更具體的定義如下:

定義13 設(shè)t(u),r(u),q(u)∈Q[u]. 給定正整數(shù)k和非平方正整數(shù)D, 若以下條件滿足

(1)q(u)=p(u)d,d ≥1,p(u) 代表素數(shù);

(2)r(u) 是非常量的、不可約的、表示整數(shù)值的且首項系數(shù)大于0;

(3)r(u) 整除p(u)+1-t(u);

(4)r(x) 整除Φk(t(u)-1), 其中Φk表示k次分圓多項式;

(5) 方程Dy2(u)=4q2(u)-t2(u) 有無數(shù)整數(shù)解(u,y).則稱三元組(t(u),r(u),q(u)) 表示具有嵌入次數(shù)k和判別式D的一類橢圓曲線. 同樣, 對于某一類橢圓曲線, 其ρ的定義如下:

注2 對于有理系數(shù)多項式g(u) 滿足四個條件, 則可表示為素數(shù): (1) 非常量的不可約多項式; (2) 首項系數(shù)大于0; (3) 對于某些u ∈Z,g(u) 表示整數(shù); (4) 對于某些u1,u2∈Z, 有g(shù)cd(g(u1),g(u2))=1.

某一類橢圓曲線構(gòu)成集合的基數(shù)取決于變量(u,y) 的整數(shù)解的個數(shù). 在某些情況下, 若解(u,y) 組成的集合呈指數(shù)增長, 我們稱這樣的類為稀疏的. 在其他情況下, 若解(u,y) 組成的集合相當(dāng)稠密, 我們稱這樣的類為完備的.

Freeman 等人[76]對近些年配對友好型曲線作了詳細(xì)綜述, 主要分為非參數(shù)化的配對友好型曲線和參數(shù)化的配對友好型曲線. 非參數(shù)化的配對友好型曲線主要包括: 超奇異橢圓曲線伴隨嵌入次數(shù)k ∈{1,2,3,4,6}, 見文獻(xiàn)[76, §3]; Cocks–Pinch 曲線[77]; DEM 曲線[78]. 參數(shù)化的配對友好型曲線包括: 稀疏的類和完備的類. 目前稀疏的類有: MNT 曲線類伴隨嵌入次數(shù)k ∈{3,4,6}[79]; GMV 曲線類—擴(kuò)展的MNT 曲線類[80]; Freeman 曲線類伴隨嵌入次數(shù)為k= 10[81]. 目前完備的類有: 分圓域類—包括BLS 曲線[55]和BW 曲線[54]; 零星類—包括BN 曲線[82]; Scott–Barreto 類[83,84]. 目前在實際應(yīng)用中(如NIST 或者國密算法SM9 中) 較廣泛被使用的曲線有BN 曲線、BLS 曲線、KSS 曲線[85](BW 曲線的一些特例). 下面我們重點介紹這三類曲線相關(guān)參數(shù)的選取.

3.1 BN 曲線

BN 曲線是定義在有限域Fp,p ≥5 上的橢圓曲線E, 它的階r和特征p均是參數(shù)化的素數(shù)

其中u是精心挑選的整數(shù).E的曲線形式為y2=x3+b, 其中b ∈F*p. BN 曲線的嵌入次數(shù)k=12.

注意, BN 曲線總是有6 階扭曲線: 若ξ ∈Fp2既不是二次剩余也不是三次剩余, 則定義E的扭曲線E′/Fp2滿足y2=x3+b′, 其中b′=b/ξ或b′=bξ. 為了簡化計算, 元素ξ可用Fp12在Fp2上的六次擴(kuò)張的本原元來表示, i.e., Fp12= Fp2[γ],γ6=ξ. 順便說一下, BN 曲線已成為許多近期出版物的熱點, 比如文獻(xiàn)[52,86-90].

3.2 BLS 曲線

BLS 曲線和BN 曲線的定義很相似, 也是定義在參數(shù)化的特征p上且滿足方程y2=x3+b′的曲線.與BN 曲線不同的是, BLS 曲線的階不是素數(shù)階的, 其階可被一個很大的參數(shù)化的素數(shù)r整除, 從而可以在r階扭子群上定義配對. 它們可使用不同的嵌入次數(shù), 但研究者們關(guān)注最多的是BLS12 和BLS24, 其相對于r的嵌入次數(shù)k分別為12 和24. 具體參數(shù)由下式給出.

其中u是精心挑選的整數(shù).

3.3 KSS 曲線

KSS 曲線也可用于不同的嵌入度. 若嵌入次數(shù)k= 18, 其與BLS 曲線非常相似(曲線方程表達(dá)式,同樣有6 次扭曲線, 參數(shù)化素數(shù)p和r|#E(Fp)). 在這種情況下, 參數(shù)表示如下:

4 計算配對的算法總結(jié)

本節(jié)我們總結(jié)計算配對的一些算法,主要有Miller 算法[21]和橢圓網(wǎng)算法[22]. Stange[22]于2007 年利用橢圓網(wǎng)(橢圓除序列) 的性質(zhì)給出了一種計算Tate 對的多項式時間算法, 該算法也適用于Weil 對的計算. 但與Miller 算法相比, 該算法的效率仍然較低. 而且Miller 算法的適用范圍要比Stange 算法廣泛.但是Stange 算法的優(yōu)勢在于計算過程中無需求逆操作, 因此該算法依然值得進(jìn)一步優(yōu)化. 本節(jié), 我們著重介紹Miller 算法及其改進(jìn)算法, 它的算法的基本步驟包括Miller 迭代步(MLP) 和最后的指數(shù)步(FE),其中關(guān)鍵步驟是計算Miller 函數(shù)fT,Q(這里假設(shè)計算Ate 對,Q ∈G2). 由于Miller 函數(shù)fT,Q滿足迭代關(guān)系:

算法1 Miller 算法計算Miller 函數(shù)fT,Q Input: r ∈N, P ∈G1,Q ∈G2 Output: fr,Q(P)1 T = ∑l j=0 tj2j, tj ∈{0,1} 且tl = 1.2 R ←Q, f ←1 3 for j = l-1 →0 do 4f ←f2gR,R(P), R ←[2]Q;5if tj = 1 then f ←fgR,Q(P), R ←R+Q;7end 8 end 9 Return f.6

(2) 在一些特殊的橢圓曲線上改進(jìn)配對的計算, 如MNT 曲線[41,79,95], BN 曲線[52,96];

(3) Miller 迭代包括點的加法與倍乘運(yùn)算, 分析在不同的坐標(biāo)系下加快點的運(yùn)算[97];

(4) 當(dāng)嵌入次數(shù)為偶數(shù)時, 可采用分母約化的技術(shù)加快運(yùn)算[41];

(5) 從算法的角度對r分析, 如選取r為梅森素數(shù)減少Miller 迭代的次數(shù), 將r做NAF 或者NAFw展開[98]等;

(6) 利用distorsion 映射在超奇異橢圓曲線上改進(jìn)Tate 對[46].

(7) 將橢圓曲線密碼體制中的點壓縮技術(shù)應(yīng)用到配對計算中, 加快配對的計算, 這一思想, 首次由Scott 和Barreto 實現(xiàn)并提出壓縮雙線性對的概念[99].

(8) 對于具有高次扭曲線的曲線, 利用高次扭將點加與倍點運(yùn)算降到更小的域上計算, 從而加快配對的加算效率, 主要針對Ate 對或者optimal Ate 對[48,49].

國際標(biāo)準(zhǔn)中大多使用BN 曲線或者BLS 曲線上的optimal Ate 對, 主要這兩類曲線上的配對計算效率較快, 而且都具有六次扭曲線. 所以上面的第八種改進(jìn)方法可以被采用. 結(jié)合Ate 對的定義(§2.3) 和注1 中的具體分析, 我們給出計算optimal Ate 對的改進(jìn)算法, 見算法2. 算法2 只是表達(dá)了具體改進(jìn)的思想, 對于BN 曲線上optimal Ate 對利用扭曲線改進(jìn)的精確表達(dá), 可參見文獻(xiàn)[96, Alg 1].

算法2 利用扭曲線改進(jìn)的Miller 算法計算optimal Ate 對Input: T ∈N, Q′ ∈G′2, P ∈G1, Q′ 與P 線性無關(guān)Output: αopt(Q,P) = fT,φ(Q′)(P)qk-1 1 T = ∑l j=0 tj2j, tj ∈{0,1} 且tl = 1.r 2 R′ ←Q′, f ←1 3 for j = l-1 →0 do 4f ←f2gφ(R′),φ(R′)(P), R′ ←[2]R′;5if tj = 1 then f ←fgφ(R′),φ(Q′)(P), R′ ←R′ +Q′;7end 8 end 9 f ←f(qk-1)/r 10 Return f.6

由于多重配對越來越高的關(guān)注度, 加快多重配對的計算效率也是一研究要點. 研究者們發(fā)現(xiàn)調(diào)整單個配對實現(xiàn)可以在多重配對實現(xiàn)中有效工作, 這絕不是微不足道的發(fā)現(xiàn). 因而一些在單個配對計算上的優(yōu)化在多重配對計算上變得可用, 而且研究者們[100–102]得到—兩個配對乘積的聯(lián)合計算比計算兩個單獨配對的乘積更快. 最近, Scott[103]對傳統(tǒng)的Miller 算法拆分成兩個算法, 一個算法計算和存儲g函數(shù), 另一個算法計算Miller 函數(shù)f. 注意到他的算法主要針對BLS12 曲線上的Ate 對的實現(xiàn), 根據(jù)有限域Fp12的特殊表示, 垂直方程υ的計算在Ate 對的計算中不產(chǎn)生影響, 所以Miller 函數(shù)fT,Q的計算只與線性函數(shù)l有關(guān), 從而Miller 算法可以拆成兩個算法. 具體見算法3 和4.

算法3 計算和存儲BLS12 曲線上Ate 對的g 函數(shù)Input: T ∈N, Q ∈G2, P ∈G1 Output: 在Fp12 上的長度為■log T」 的數(shù)組g,1 T = ∑l j=0 tj2j, tj ∈{0,1} 且tl = 1.2 R ←Q, f ←1 3 for j = l-1 →0 do 6 4g[i] ←lR,R(P), R ←[2]R;5if tj = 1 then g[i] ←g[i]lR,Q(P), R ←R+Q;7end 8 end 9 Return g.

正如Scott[103]所說, 這種拆分的Miller 算法只有在計算多重配對時才能體現(xiàn)出它的優(yōu)勢, 他相繼也給出了計算多重Ate 對的數(shù)組g算法和計算Miller 函數(shù)f的算法, 相似于算法3 和4, 這些算法已在amcl 庫[27]中實現(xiàn). 更重要的, 針對BLS12-381 的多重Ate 對的計算消耗, 他給出進(jìn)一步分析, 計算單個Ate 對需要1556m, 計算雙重Ate 對需要1797m, 而計算高于雙重的Ate 對僅需要1856m, 其中m表示一個乘法操作. 由此可見, 此種拆分算法的優(yōu)勢所在.

算法4 計算BLS12 曲線上Ate 對Input: T, 在Fp12 上的長度為■log T」 的數(shù)組g Output: f ∈Fp12 1 f ←1 2 for j ←■log T」 to 0 do 3f ←f2gi 4 end 5 f ←f(p6-1)(p2+1)(p4-p2+1)/r 6 Return f.

5 與配對相關(guān)的計算困難問題與安全性研究

基于配對的密碼體制的安全性主要基于以下困難問題的假設(shè):

· 離散對數(shù)問題(discrete logrithm problem (DLP)): 這里給出有限域上離散對數(shù)的定義. 考慮Fq的乘法群F*q: 設(shè)x,y ∈F*q, 滿足xm=y, 求解mmod ord(x).

· 橢圓曲線離散對數(shù)問題(ECDLP): 設(shè)P,Q ∈E(Fq), 滿足Q=[m]P, 求解mmod ord(P).

· 判定性Diffe-Hellma 問題(DDHP):區(qū)分四元組{g,gx,gy,gxy|x,y為隨機(jī)數(shù)}與{g,gx,gy,gz|x,y,z為隨機(jī)數(shù)}的分布.

· 橢圓曲線的判定性Diffe-Hellma 問題(ECDDHP):區(qū)分兩個四元組{P,[a]P,[b]P,[ab]P}與{P,[a]P,[b]P,[c]P}的分布, 其中a,b,c ∈F*q且隨機(jī).

· 橢圓曲線的Diffe-Hellman 計算性問題(CDHP): 已知三個點P,[a]P,[b]P ∈E(Fq), 求解[ab]P.

· 雙線性Diffe-Hellma 問題(BDHP): 對于四元組{P,[a]P,[b]P,[c]P}, 計算e(P,P)abc.

· 判定性雙線性 Diffe-Hellma 問題 (DBDHP): 區(qū)分四元組{[a]P,[b]P,[c]P,habc}和{[a]P,[b]P,[c]P,hr}的分布, 其中h=e(g,g),a,b,c,r為隨機(jī)數(shù).

· 雙線性映射的逆問題(pairing inversion):

(1) FAPI (fixed argument pairing inversion): 在定義1 中, 給定a ∈G1和z ∈GT, 計算b ∈G2使得e(a,b)=z. 或者, 給定b ∈G2和z ∈GT, 計算a ∈G1使得e(a,b)=z.

(2) GPI(generalized pairing inversion): 對給定z ∈GT,計算a ∈G1和b ∈G2使得e(a,b)=z.

離散對數(shù)問題是建立公鑰密碼體制的基礎(chǔ), 所以如何找到快速攻擊DLP 的算法是當(dāng)前研究的熱點問題. 對于解有限域上離散對數(shù)問題(DLP) 的算法主要有次指數(shù)時間的指標(biāo)積(index calculus) 算法[104],在使用指標(biāo)積方法攻擊離散對數(shù)時主要用到兩種篩法收集線性關(guān)系: 數(shù)域篩法(NFS)[105,106]和函數(shù)域篩法(FFS)[107–109], 2014 年Joux[110]對DLP 研究的發(fā)展作了詳細(xì)的介紹. 這兩種篩法適用于不同特征的有限域, 一般地, 對于非小特征的有限域使用數(shù)域篩法, 對中間特征或小特征的有限域使用函數(shù)域篩法會得到更好的結(jié)果. 對于解ECDLP 的算法有大步小步算法[111]、Pollard-ρ算法[112]以及指標(biāo)積算法[113], 2016 年Galbraith 和Gaudry[114]對ECDLP 研究的發(fā)展作了詳細(xì)的介紹.

以上很多問題大都是建立在DLP 基礎(chǔ)上的, 如DDHP、CDHP、BDHP 等. 由于雙線性對的快速計算, 橢圓曲線的ECDDHP 是容易的. Dan Boneh 等人[5]利用Weil 對建立了基于身份的密碼體制, 其機(jī)制的安全性是建立于BDHP 與DBDHP 的困難性. Joux[115]提出了了兩類雙線性映射的逆問題FAPI與GPI, 并分析以上問題的強(qiáng)弱聯(lián)系. Cheon 等人[116]利用Lee[66]中的自配對也給出以上問題的強(qiáng)弱關(guān)系. 關(guān)于FAPI 與GPI 的相關(guān)研究可參見文獻(xiàn)[117-120]. Kanayama 等人[118]在廣義的Ate 對Atei上分析了FAPI 問題, Kim 等人[120]進(jìn)一步分析了FAPI 問題在Tate 對與Ate 對(及其改進(jìn)的Ate 對)的困難程度. 表面上, Ate 對比Tate 對的迭代次數(shù)小, 代數(shù)結(jié)構(gòu)好, 很容易認(rèn)為Ate 對上的FAPI 問題會弱于Tate 對上的. 然而, Kim 等人[120]發(fā)現(xiàn)它們的困難程度等價. 到目前為止, 還無法確定FAPI 問題的困難程度, 也沒有它的快速攻擊算法, 所以它的安全性依然值得研究.

5.1 配對的最新安全性參數(shù)

我們知道構(gòu)造配對友好型曲線需要權(quán)衡(trade-off) 配對的計算效率與安全性. 而定義在有限域Fq上具有嵌入次數(shù)k和r階扭子群的配對, 其配對的安全性由下面兩方面決定:

(1) 橢圓曲線E/Fq的r階扭子群或者商群的離散對數(shù)問題的時間消耗(曲線方面);

(2) 有限域Fqk乘法群的子群的離散對數(shù)問題的時間消耗(有限域方面).

有限域方面的安全級別評估就相對困難, 因為目前有限域上離散對數(shù)的最好攻擊算法是指標(biāo)積算法,然而它的時間復(fù)雜度很難精確表達(dá). 自2013 年以來, 一些更復(fù)雜的算法[121,122]取代了經(jīng)典的Coppersmith 算法[123]和函數(shù)域篩法[107–109], 它們對小特征域上的離散對數(shù)進(jìn)行了攻擊, 使得那些小特征域上的配對無效. ENISA 立即做出了反應(yīng), 并在其2013 年發(fā)布的標(biāo)準(zhǔn)文件中[124]表示該機(jī)構(gòu)禁止使用小特征的配對. 在非小特征的情況下, 最著名的算法是數(shù)域篩法, 自2013 年以來, 也出現(xiàn)了一系列新的變體和改進(jìn)[125–131]. 擴(kuò)展域塔的數(shù)域篩法[132,133](SexTNFS 算法) 顯著改變了攻擊的復(fù)雜性, 并在同一篇文章中對BN128 的安全性作了精確分析, 表明必須重新評估密鑰大小.

緊接著, Menezes 等人[134]和Barbulescu 等人[135]通過分析數(shù)域篩法(NFS) 的最新進(jìn)展對配對的安全性提出了新的估計, Barbulescu 等人[135]的估計更精確. 他們就是利用目前最好的SexTNFS 算法去攻擊最流行的配對(BN 曲線上的optimal Ate 對), 發(fā)現(xiàn)大多數(shù)現(xiàn)有實現(xiàn)中使用的BN128 曲線所能達(dá)到的安全級別最多100-bit 安全, 并不是之前所稱的128-bit 安全. 并且zk-SNARK[136–139]中被廣泛使用的曲線BLS12-381, 在zcash 的安全審計報告中指出其安全級別也未達(dá)到其所稱的128-bit 安全. 基于這些發(fā)現(xiàn), Barbulescu 等人[135]為幾類較流行的曲線在不同安全級別下重新配置了參數(shù), 如參數(shù)u的選取、域的大小、曲線的方程. 表1 僅給出曲線中參數(shù)u和域Fpk的長度. 對于192-bit 的情況, 表1 對比之前的參數(shù)長度[90], 明顯可見參數(shù)長度的變化. 對于192-bit 和256-bit 安全級別, 這里僅需考慮BLS24和KSS18 曲線, 因為毫無疑問, BN、BLS12 和KSS16 曲線對應(yīng)域的長度會變很大, 計算效率會降低.

表1 不同安全級別下的不同曲線的參數(shù)長度Table 1 Parameter length for different curves at different security levels

注3 在64-bit 多處理器的計算平臺上, BN128 曲線上的optimal Ate 對的計算效率最快. 在192-bit 安全級別下, 文獻(xiàn)[90,94] 給出了不同曲線上optimal Ate 對在實現(xiàn)上的計算效率, BLS12 曲線上的optimal Ate 對計算效率最快. 注意這些實現(xiàn)效率均是在之前的曲線參數(shù)下考慮的. 所以在Barbulescu 等人[135]重新配置的曲線參數(shù)之后, 研究者們需分析不同安全級別下的最新曲線參數(shù)的配對實現(xiàn)效率.

6 結(jié)論

本文從橢圓曲線的Weil 對開始, 結(jié)合配對在密碼學(xué)上的進(jìn)展, 給出了各類配對的詳細(xì)定義及其改進(jìn)方案. 對于初學(xué)者來說, 可以較快地了解這方面的工作. 其次, 針對最流行的幾類配對友好型曲線, 結(jié)合最新的攻擊算法, 我們總結(jié)了這幾類曲線不同安全級別下最新的參數(shù)選取, 方便底層實現(xiàn)的研究者們快速掌握. 對于配對上的計算困難問題, 日前研究進(jìn)展依然緩慢. 我們這里關(guān)注的配對只是橢圓曲線上的雙線性配對, 對于其他形式的配對并沒有作過多關(guān)注. 縱觀近三十年配對在密碼學(xué)上的應(yīng)用, 近二十年來, 研究者們更多地關(guān)注配對的快速計算及其改進(jìn), 目前理論上可以證明最優(yōu)配對的存在性, 但在實用中只有很少的配對友好型曲線可以構(gòu)造出最優(yōu)配對. 配對在密碼學(xué)上的應(yīng)用日益廣泛, 它的潛能還有待繼續(xù)挖掘.