朱屹霖 李夢東 王 穎

北京電子科技學(xué)院，北京市 100070

引言

后量子密碼是當(dāng)前公鑰密碼學(xué)研究的一個熱點。 自2011 年Jao 和De Feo[1]提出超奇異同源密碼交換協(xié)議(SIDH)以來，基于同源的密碼方案受到了關(guān)注。 由SIDH 改造的超奇異同源密鑰封裝(SIKE)協(xié)議，目前已成為NIST 后量子密碼算法評選的第三輪九種密鑰封裝機(jī)制之一。與其他后量子協(xié)議相比，基于同源的協(xié)議具有較小的公鑰。 而SIDH 還可以對公鑰進(jìn)行壓縮，使SIDH 協(xié)議更具競爭力。 SIDH 是同源密碼的基本類型之一，其他基于同源的身份認(rèn)證、加密和數(shù)字簽名等方案多是在其基礎(chǔ)上的構(gòu)造。 同源密碼的密鑰和密文(或簽名)是幾種后量子密碼類型中長度最短的，但是也存在計算時間長的弱點，約是其他后量子算法的幾倍時間。 因此如何提高計算速度，是SIDH 類型密碼的研究重點之一。

SIDH 公鑰壓縮是將公鑰的點表示為撓基分解，傳輸這一分解的系數(shù)，從而進(jìn)一步減少公鑰長度。 壓縮過程一般分為三步:撓基分解、雙線性對計算和求解離散對數(shù)。 SIDH 公鑰壓縮的思路由R. Azarderakhsh 等人[1]在2016 提出，將原來的公鑰長度由6log2p減小到4log2p左右(p 是工作域的特征)，但公鑰壓縮時間花費(fèi)是整個SIDH 計算時間的十倍；2017 年Costello 等人[2]進(jìn)一步改進(jìn)，通過將點P 和Q 進(jìn)行正規(guī)表示，將公鑰進(jìn)一步壓縮為3 個Zn元素，最終密鑰大小近似3.5log2p， 并使公鑰壓縮的時間減小為與SIDH 密鑰協(xié)商的時間相當(dāng)。 同年Zanon 等[3]提出糾纏基算法，進(jìn)一步提高了壓縮性能。

本文主要在之前學(xué)者的工作基礎(chǔ)上進(jìn)一步優(yōu)化，將重點放在雙線性對計算上，對Miller 算法中線函數(shù)的部分信息采取預(yù)計算，以減少M(fèi)iller 循環(huán)中消耗的計算成本。 與之前的工作相比，進(jìn)一步提高了雙線性對計算這一步的效率。

1 預(yù)備知識

1.1 橢圓曲線

令q=pn，橢圓曲線E/Fq是一個虧格為1的光滑射影代數(shù)曲線(至少有一個點)。 其仿射部分滿足Weierstrass 方程:

另外它還有一個無窮遠(yuǎn)點O。 如果p≠2，3，則上述方程可同構(gòu)為短的Weierstrass 方程y2=x3+a4x+a6。 判別式4a34+ 27a26 ≠0 且在Fq內(nèi)。

1.2 超奇異橢圓曲線

如果橢圓曲線EFpm(p為素數(shù)) 滿足以下等價的任何一個條件，就稱它為超奇異橢圓曲線，否則就稱之普通的橢圓曲線。

1.3 同源

設(shè)E1和E2是有限域Fq上的橢圓曲線。 同源φ:E1→E2是定義在Fq上的一個非平凡的保持基點的有理映射，也是從E1(Fq) 到E2(Fq) 的群同態(tài)。 如果存在這樣的映射，就稱E1和E2是同源的，兩條曲線E1和E2在Fq上是同源的當(dāng)且僅當(dāng)＃E1(Fq)= ＃E2(Fq)。

同源φ可以用兩個Fq上的有理映射f和g表示，即φ((x，y))= (f(x)，y·g(x))， 其中f(x)=p(x)/q(x)，多項式p(x) 和q(x) 在Fq上沒有公因式，g(x) 也是如此。 同源的次數(shù)deg(φ) 定義為max{deg(p(x))，deg(q(x))}，其中p(x) 和q(x) 分別是f和g的分子與分母多項式。 僅用同源結(jié)構(gòu)的f(x) 分量進(jìn)行同源計算通常是很方便的。 給定同源φ:E1→E2，我們定義φ的核如下:ker(φ)={P∈E1:φ(P)=O}。

對于E(Fp) 的任意有限子群H， 存在唯一的同源φ:E→E′，使得ker(φ)=H，deg(φ)=|H|，其中|H| 表示H的基數(shù)。 在這種情況下，我們用E/H表示曲線E′。 給定一個子群H?E(Fp) 為例，利用Vélu 公式可以求出同源φ和同源的曲線E/H。

1.4 SIDH 協(xié)議

SIDH 協(xié)議過程為:Alice 隨機(jī)選擇mA∈Z/2e2Z，計算同源2e2-φA:E6→EA， 核為KA∶= ＜PA+ [mA]QA ＞， 并計算出φA(PB)，φA(QB) 和像曲線參數(shù)A，將(φA(PB)、φA(QB)、A) 發(fā)給Bob。 同樣Bob 隨機(jī)選擇mB∈Z/3e3Z，計算同源3e3-φB:E6→EB，核為KB∶= ＜PB+[mB]QB ＞， 并計算出φB(PA)，φB(QA) 和圖像參數(shù)B，將(φB(PA)、φB(QA)、B) 發(fā)給Alice。

Alice 收到消息后，計算同源φ′A:EB→EAB，核為＜φB(PA)+[mA]φB(QA)＞；B 也相同，計算同源φ′B:EA→EBA， 核為＜ φA(PB)+[mB]φA(QB)＞。 至此，由于EBA?EAB，A 和B可用EBA和EAB的j-不變量得到共享密鑰。

1.5 SIDH 的公鑰壓縮

以Alice 端為例，所謂的公鑰壓縮即壓縮上述的(φA(PB)、φA(QB)、A)。 實際在SIDH 協(xié)議中，Alice 利用PA、QA、RA=PA-QA、RB=PB-QB的x 坐標(biāo)和她的密鑰來完成密鑰生成的整個過程。 在這種情況下，Alice 應(yīng)該向Bob 發(fā)送三元組(xφA(PB)，xφA(QB)，xφA(RB))。 同樣方式也適用于Bob。 R. Azarderakhsh 等人[1]在2016 年提出將φA(PB)、φA(QB) 展開為撓基的表示，用其系數(shù)表示相應(yīng)的點，從而實現(xiàn)了公鑰的進(jìn)一步壓縮。

2 已有算法分析

R. Azarderakhsh 等人[1]的具體方法如下，以Alice 端為例。 其主要思想是實現(xiàn)一個確定性偽隨機(jī)數(shù)發(fā)生器，找出一個3e3-撓基(UA，VA)，將φA(PB)、φA(QB) 表示為:

這時，Alice 可以通過用Pohligh-Hellman 算法求解階為3e3的乘法子群中的離散對數(shù)來恢復(fù)a0，b0，a1，b1。 那么Alice 可以將(a0，b0，a1，b1，A) 作為自己的公鑰分發(fā)給Bob，而不是(xφA(PB)，xφA(QB)，xφA(RB))。

同年Zanon 等人[3]提出糾纏基技術(shù)，加快了撓基的生成，并在雙線性對計算這一步利用糾纏基產(chǎn)生的點對的特殊形狀優(yōu)化Tate 對，并在最后提出計算離散對數(shù)的高效方法，進(jìn)一步減少了SIDH 壓縮和解壓縮的運(yùn)行時間。

具體方法即在線性表示的基礎(chǔ)上進(jìn)一步優(yōu)化。 由于＜ φA(PB)，φA(QB)＞=EA[3e3]，即φA(PB)，φA(QB) 也能構(gòu)成EA[3e3] 中的一組基。 可以看出上述矩陣是可逆的，因此

這樣做的好處是可以預(yù)先計算出h0的值，從而提高求解四個離散對數(shù)的效率。

2019 年M. Naehrig 和J.Renes[5]采用了對偶同源技術(shù)，顯著降低了壓縮的成本。 具體操作為，利用同源和其對偶的關(guān)系式，將上述除h0以外的四個對變換成如下形式:

在后面的計算就可以通過預(yù)存儲第一個參數(shù)的所有信息以便加快后面的計算，但此方法需要對固定的系統(tǒng)參數(shù)進(jìn)行大量的預(yù)計算，盡管它在速度上有了顯著的提升，而存儲雙線性對計算和離散對數(shù)解的表需要很大的存儲空間，對內(nèi)存造成一定的影響。

2021 年Kaizhan Lin 等學(xué)者[6]也采用了對偶同源技術(shù)，提出了新的改進(jìn)，從函數(shù)除子之間的迭代關(guān)系進(jìn)行優(yōu)化，推導(dǎo)出許多關(guān)系式，提出了幾種提高雙線性對計算效率的算法，不僅減少了計算成本，而且節(jié)省了近四分之一的內(nèi)存來存儲預(yù)計算。

3 改進(jìn)的算法

雙線性對計算是公鑰壓縮的計算瓶頸。 雙線性對計算過程就是線方程的迭代。 對于公鑰壓縮中這一步的改進(jìn)，許多方法大多延續(xù)和修改線方程的公式，而預(yù)計算通過提前計算和存儲相關(guān)結(jié)果可提高計算效率。 因此本文在Costello等人[2]的工作基礎(chǔ)上進(jìn)一步改進(jìn)，預(yù)先存儲相應(yīng)的Miller 算法中P 的倍點及線函數(shù)的部分信息，以提高后續(xù)Miller 迭代的效率。

Costello 等人[2]在仔細(xì)檢查了二倍線函數(shù)和三重拋物線運(yùn)算的顯式公式之后，選擇使用坐標(biāo)元組(X2:XZ:Z2:YZ) 代表中間射影點P=(X:Y:Z) 以提高域算術(shù)的運(yùn)算效率。 在本文使用這種表示且滿足XYZ≠0，因為它們的階數(shù)嚴(yán)格大于2，這確保了下列公式不包含例外情況。

那么我們觀察可得，上述5 個系數(shù)的顯式公式中出現(xiàn)許多相同的項，如果每次Miller 迭達(dá)都重復(fù)計算，會大大降低計算效率，因此可以預(yù)先計算以下所有值:

算法1:點P 的二倍運(yùn)算輸入:(U1，U2，U3，U4)輸出:(V1，V2，V3，V4)1 V1 ←t22，2 V2 ←4t3·t2，3 V3 ←16t32，4 V4 ←2t5·(t2 + 2U2·(4U2 + A(U1 + U3))).

同樣觀察可得，如果預(yù)先計算以下所有值，線函數(shù)的計算效率會有所提高:

算法2:點P 的三倍運(yùn)算輸入:(U1，U2，U3，U4)輸出:(V1，V2，V3，V4)1 V1 ←U1·t0·t52，2 V2 ←t6，3 V3 ←t7，4 V4 ←8U3·t1·t8·(16A2s1s3 + 28As0s4+ 28As3s4 + 4As2s4 + 4As0s5 + 6s32 + 28s0s3+ s22 + 28s2s3 + s02)·(U3 + U1 + AU2)2

通常情況下，我們用M，S 分別表示Fp2中的乘法運(yùn)算和平方運(yùn)算，定義一個二次擴(kuò)域元素大小為log pbit。

未改進(jìn)之前，Costello 等人[2]的方法在計算上述階為2eA的Tate 對的情況下，在二次擴(kuò)域中每次計算二倍-線函數(shù)的成本為9M+5S； 階為3eB的Tate 對的情況下，在二次擴(kuò)域中每次計算三倍-拋物線函數(shù)的成本為19M+6S。

改進(jìn)之后，本文方法在計算階為2eA的Tate對的情況下，每次需要預(yù)計算5 個元素，約需存儲空間大小為5log pbit，在二次擴(kuò)域中二倍-線函數(shù)相應(yīng)的計算成本為7M+2S， 相對節(jié)省2M+3S；階為3eB的Tate 對的情況下，每次需要預(yù)計算15 個元素，約需存儲空間大小約為15log pbit，在二次擴(kuò)域中三倍-拋物線函數(shù)相應(yīng)的計算成本為14M+5S，相對節(jié)省5M+S。

4 結(jié)束語

SIDH 公鑰壓縮是進(jìn)一步減少公鑰長度的措施，如何減少公鑰壓縮帶來的負(fù)面影響(即計算代價大)是同源密碼研究的熱點問題。 值得注意的是Miller 算法中線函數(shù)的計算不僅是配對計算的主要瓶頸，也是整個公鑰壓縮的瓶頸。 本文主要針對SIDH 中公鑰壓縮過程中的Miller 計算，提出了有效提高配對計算的方法，從而減少整個公鑰壓縮過程的計算時間。