SIDH 公鑰壓縮中雙線性對的有效計算*

朱屹霖 李夢東 王 穎

北京電子科技學院，北京市 100070

引言

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

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

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

1 預備知識

1.1 橢圓曲線

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

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

1.2 超奇異橢圓曲線

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

1.3 同源

設E1和E2是有限域Fq上的橢圓曲線。 同源φ:E1→E2是定義在Fq上的一個非平凡的保持基點的有理映射，也是從E1(Fq) 到E2(Fq) 的群同態(tài)。 如果存在這樣的映射，就稱E1和E2是同源的，兩條曲線E1和E2在Fq上是同源的當且僅當＃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) 也是如此。 同源的次數deg(φ) 定義為max{deg(p(x))，deg(q(x))}，其中p(x) 和q(x) 分別是f和g的分子與分母多項式。 僅用同源結構的f(x) 分量進行同源計算通常是很方便的。 給定同源φ:E1→E2，我們定義φ的核如下:ker(φ)={P∈E1:φ(P)=O}。

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

1.4 SIDH 協(xié)議

SIDH 協(xié)議過程為:Alice 隨機選擇mA∈Z/2e2Z，計算同源2e2-φA:E6→EA， 核為KA∶= ＜PA+ [mA]QA ＞， 并計算出φA(PB)，φA(QB) 和像曲線參數A，將(φA(PB)、φA(QB)、A) 發(fā)給Bob。 同樣Bob 隨機選擇mB∈Z/3e3Z，計算同源3e3-φB:E6→EB，核為KB∶= ＜PB+[mB]QB ＞， 并計算出φB(PA)，φB(QA) 和圖像參數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 坐標和她的密鑰來完成密鑰生成的整個過程。 在這種情況下，Alice 應該向Bob 發(fā)送三元組(xφA(PB)，xφA(QB)，xφA(RB))。 同樣方式也適用于Bob。 R. Azarderakhsh 等人[1]在2016 年提出將φA(PB)、φA(QB) 展開為撓基的表示，用其系數表示相應的點，從而實現了公鑰的進一步壓縮。

2 已有算法分析

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

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

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

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

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

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

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

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

3 改進的算法

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

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

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

算法1:點P 的二倍運算輸入:(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))).

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

算法2:點P 的三倍運算輸入:(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中的乘法運算和平方運算，定義一個二次擴域元素大小為log pbit。

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

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

4 結束語

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