基于同源的抗量子群密鑰交換協議

樊雪君，王龍，徐秀，宋寧寧，范晶，王怡

(1.華北計算機系統工程研究所，北京 100083；2.中國信息通信研究院，北京 100191)

0 引言

基于同源的密碼協議是抗量子密碼中的重要組成部分，它依賴于計算給定橢圓曲線之間同源的困難性，該困難問題在量子算法攻擊下的時間復雜度是(亞)指數級別的。目前基于同源的密鑰交換協議有三類：OIDH(基于常曲線同源的密鑰交換協議)、SIDH(基于超奇異同源的密鑰交換協議)和CSIDH(基于可交換的超奇異同源的密鑰交換協議)。相比于其他抗量子密碼協議，基于同源的密碼體制的優勢是密鑰長度短，劣勢是協議效率低。本文主要考慮了基于同源的群密鑰交換協議，從調整協議的模型的角度來討論基于同源的密鑰交換協議的加速。

1 研究背景及研究內容

1.1 研究背景

群密鑰交換(GKE)協議允許多個參與方在公共網絡上協商共享密鑰，現已被廣泛地應用于現實世界的交互網絡中，比如Ad-hoc網絡和無線傳感網絡等。目前大部分的群密鑰交換方案[1-3]都是從兩方的密鑰交換協議擴展而來的。

但是目前針對抗量子的群密鑰交換方案還比較少。Apon等人[4]將BD協議推廣到環LWE問題上，得到了格上的群密鑰交換協議。基于同源的群密鑰交換協議也逐漸得到關注，Furukawa等人[5]提出了兩個基于超奇異同源的多方密鑰交換協議。第一個是SIDH協議的變形，域的特征變為參與方的數量會影響p的選取。第二個是傳統BD協議[1]的變形，但其乘法運算的數量較多，降低了協議的效率。Azarderakhsh等人[6]構造了n方群密鑰交換協議，每個用戶在發送下一條信息之前都必須使用自己的私鑰信息進行計算，即提供了隱式認證，但是該方案也有很多缺陷：第一，如果參與方的數量n發生了變化，則有限域的特征也需要更改；第二，方案每個用戶需要計算n-1個同源和(n-1)n個點的像，單個用戶傳輸的比特數可達到O(λn2)(λ是安全參數)量級，故方案的計算復雜度和通信量較高；第三，該方案沒有安全性證明。因此，研究基于超奇異同源的群密鑰交換協議是非常有意義的。

1.2 本文工作及結構

本文提出了兩個2輪的基于超奇異同源的抗量子群密鑰交換協議。第一個是對基于超奇異同源的BD協議—SIBD協議[5]的加速。由于BD協議中單個用戶的通信量較高，研究者們便考慮了樹形的BDII模型[7]，故本文的第二個方案便是SIDH和BDII協議[3]的結合。在這兩個GKE協議中，本文都更換了會話密鑰的計算方式，使用有限域中的加減法而不是乘除法來進行計算，從而提高了整個協議的計算效率，使其可以被微型處理器接受。此外本文還給出了兩個方案針對被動攻擊者的安全性證明，最后對協議的輪數、通信量以及計算復雜度進行了分析。與現有的基于超奇異同源的GKE協議[5]比較，本文所提協議具有較小的計算復雜度和較高的通信效率。

2 基礎知識

2.1 SIDH協議

2.1.1 SIDH協議形式

De Feo等人[8]利用Fp2上的超奇異橢圓曲線構造了SIDH協議。由于Fp2上的超奇異橢圓曲線的自同態環是非交換的，故SIDH協議的量子攻擊復雜度為指數時間[9]。

SIDH協議[6]使用了有理點的個數有很多小素數做因子的超奇異曲線，這樣曲線有很多小次數的同源，從而可提高計算效率。特別地，取超奇異橢圓曲線E/Fp2，其中是 素 數，lA和lB是 小素數，f是使得p是素數的調節因數，則#E/(Fp2)=(或是Fp2有理的，且包含個階為的循環子群，這些循環子群對應了不同構的同源。令是 公共參數，SIDH協議的具體執行過程如圖1所示。

圖1 基于Fp2上的超奇異橢圓曲線的密鑰交換協議(SIDH)

Alice和Bob通過密鑰交換分別獲得曲線EAB和EBA， 且因此協議雙方可共享EAB和EBA的j-不變量。

值得注意的是，Alice的私鑰mA、nA不能同時被lA整 除，以 保 證對Bob的 私 鑰mB、nB也 有類似要求。在具體執行過程中，一般取lA=2，lB=3。且為了減少標量乘的計算、提高協議的效率，會不失一般性地取mA=mB=1，且nA和nB分別在和中隨機均勻選取。

圖2給出了更直觀的協議雙方進行的操作。

圖2 SIDH協議的直觀執行圖

值得一提的是，基于SIDH協議構造的密鑰封裝協議SIKE[10]已經被提交到NIST算法競賽中，并成為第三輪候選算法。

2.1.2 SIDH協議的基本困難問題

首先利用DH語言來描述一下SIDH協議，以便后續安全性證明中使用。

設{t，s}={0，1}，記公鑰參數為g=(E0；P0，Q0，P1，Q1)和e=(l0；l1，e0，e1)。 定義超奇異橢圓曲線的集合及曲線和點構成三元組的集合：

SSECp={定義在Fp2上超奇異橢圓曲線

SSECA=是的基}

SSECB=是的基}

記a=ka且b=kb，則可以定義：

其 中RA=Ps+[ka]Qs，φA：E0→EA=E0/〈RA〉。

其 中RB=Pt+[kb]Qt，φB：E0→EB=E0/〈RB〉。

其中RBA=φB(Ps)+[ka]φB(Qs)，φBA：EB→EBA=EB/〈RBA〉。

其中RAB=φA(Pt)+[kb]φA(Qt)，φAB：EA→EAB=EA/〈RAB〉。

值得注意的是，本文定義ga和gb是群，而定義(gb)a和(ga)b是j-不變量。這并不是出現了錯誤，只是將SIDH協議的形式與傳統的Diffie-Hellman(DH)密鑰交換協議的形式結合起來。利用上述符號，便可發現SIDH協議的形式與DH協議形式幾乎完全相同。公共參數為g和e，Alice選擇私鑰a并發送ga給Bob，Bob選擇私鑰b并發送gb給Alice，最終共享密鑰為j=(gb)a=(ga)b。基于符號定義，本文描述兩個關于超奇異同源的標準假設:

定義1(SI-DDH假設[7])給定公共參數g和e，定義兩個分布D0和D1：

SI-DDH問題指的是，隨機給定一個分布Db，其中b←{0，1}，猜測b的值。對于多項式時間的算法A，定義其解決SI-DDH問題的優勢為：

則SI-DDH假設指的是，對于任意多項式時間的算法A，解決SI-DDH問題的優勢都是可忽略的。

2.2 SIBD協議的安全模型

針對群密鑰交換協議的安全性，由于本文是以SIDH協議為基礎構造的群密鑰交換協議，因此本文考慮文獻[11]中的認證鏈接攻擊者模型。在證明過程中假設所有協議的參與方都是誠實的。

假設協議中共有n個參與方U={U1，U1，…，Un}，每個參與者都可以同時運行多個事件。記參與者U的第i個事件為，會話標識為sid，會話參與者標識為pid。

GKE模型的安全性是由一系列挑戰者和攻擊者A之間的游戲定義的。在游戲過程中，敵手A可以通過詢問下列問題解決某個挑戰：：返回誠實執行過程中的交互信息。這是被動攻擊所執行的。

Corrupt(Ui)：該詢問泄露Ui的靜態密鑰。如果敵手未進行Corrupt詢問，則參與者是誠實的。：在接受事件中進行該詢問，該詢問在整個執行過程中只能出現一次。

在安全性證明的過程中，允許敵手A執行Test詢問。令κ是當前會話過程中的會話密鑰，挑戰者隨機選取b∈{1，0}，若b=1則向敵手發送當前的會話密鑰；否則便向敵手發送密鑰空間中的隨機元素。如果敵手在會話s過期之前就向相應的oracle詢問了s或者，則稱參與方的會話都是本地公開的。如果s在過期之前，s或者其匹配會話s′是本地公開的，則稱s被暴露；否則，證s是新鮮的會話。

在Test詢問的前后，攻擊者都可以進行自適應的查詢，即詢問挑戰者關于測試會話以外的其他問題。最后，攻擊者A猜測比特b′，令SuccA(λ)是挑戰者A猜對b=b′的概率，其中λ是安全參數，則定義：

定義2(Session-Key安全)設密鑰交換協議的安全參數為λ，若對于任意多項式時間的敵手A，均滿足：若未被Corrupt詢問的兩方完成了匹配會話，則會話便輸出相同的密鑰，且AdvA(λ)是可忽略的。則稱該密鑰交換協議是Session-Key安全的。

3 改進的基于超奇異同源的群密鑰交換協議

本節將SIDH協議分別與BD協議和BDII協議結合，并利用加法運算代替會話密鑰計算過程中的乘法運算，從而得到了更高效的2輪群密鑰交換協議。

3.1 改進的SIBD協議

Furukawa等人[5]以SIDH協議為基礎推廣BDI協議，從而得到了SIBD協議。本文將其會話密鑰計算過程中的乘除法更換為加減法，從而優化了SIBD協議，還給出了抵抗被動攻擊的安全性證明。

群密鑰交換協議中的公共參數與SIDH協議的公共參數相同，設協議中共有n個參與方，依次標號為1，2，…，n，記Un+1=U1，則n個參與方可構成一個環形。當n是奇數時，可以使其中某個參與者虛擬地扮演兩個角色。因此可只考慮n是偶數的情況。下面為改進的SIBD協議流程。

第1輪：每個用戶Ui隨機選取作為私鑰，計算Ri=Ps+kiQs，其中s=i(mod 2)。然后計算同源φi：E→Ei=E/〈Ri〉，令，將廣播給Ui-1和Ui+1。

第2輪：每個用戶Ui收到相鄰兩方發送來的公鑰和，利用收到的公鑰和自己的私鑰執行SIDH協議，可得和，其中ji-1，i和ji，i+1分 別 代 表 了Ei-1/〈φi-1(Ps)+kiφi-1(Qs)〉和Ei+1/〈φi+1(Ps)+kiφi+1(Qs)〉的j-不變量。最后，用戶Ui向所有參與方廣播。

計算會話密鑰：每個用戶Ui利用哈希函數H:{0，1}*→{0，1}λ，其 中λ是 安 全 參 數，計 算 會 話 密鑰Ki=H(nji-1，i+(n-1)ui+(n-2)ui+1+…+2ui-3+ui-2)，可以驗證，對于任意i，均有：

需要強調，相比于有限域中的乘法，加法計算的復雜度可以被忽略，這便是改進的SIBD協議效率提高的主要原因。關于安全強度，GKE協議中最基本的安全性要求便是SK-安全(SK-security)，即對被動攻擊者來說會話密鑰不可區分。

定理1在SI-DDH的假設下，改進的SIBD協議在隨機諭言機模型下是安全的，并且可以達到前向安全性。即如果存在n個用戶，敵手A詢問qE次Execute，該協議滿足。

證明：由于協議中沒有靜態密鑰，故敵手可以忽略Corrupt詢問，因此該協議滿足前向安全性。

現假設存在敵手A可以攻擊改進的SIBD協議，證明可以構造區分器D以不可忽略的優勢解決SI-DDH問題。敵手A可以詢問Execute、RevealKey和Test。設是一次執行過程的記錄，K是該過程得到的會話密鑰，則可定義兩個分布Real和Fake。其中Real是真實協議執行產生的分布，而Fake中的是在Fp2中隨機選取且滿足記，φi：E→Ei=E/〈Ps+liQs〉，則：

斷言1對于任意敵手A，有|Pr[(T，K)←Real：A(T，K)=1]-Pr[(T，K)←Fake′：A(T，K)=1]|≤，其中：

證明：設存在一個針對SI-DDH問題的區分器D。D調用敵手A，輸入與SIDH協議中相同的(ga，gb，gc)，根據分布Dist′生成(T，K)，然后輸出敵手A的輸出結果。其中：

如果li是隨機的，則分布Real與分布{a，b∈；(T，K)←Dist′：(T，K)}在統計意義下是等價的。此外，除了一個的因子，分布Fake′與分布{a，b∈在統計意義下是等價的。因此通過SI-DDH問題的歸約可以得到分布Real和Fake′在統計意義下是等價的。

斷言2對于任意敵手A，均有|Pr[(T，K)←Fake′：A(T，K)=1]-Pr[(T，K)←Fake：A(T，K)=1]|≤。

證明：仿照斷言1中的結論，定義分布

便可得：

|Pr[(T，K)←Fake：A(T，K)=1]-Pr[(T，K)←Fake(1)：A(T，K)=1]|≤

然后利用hybrid方法可以得到：

|Pr[(T，K)←Fake′：A(T，K)=1]-Pr[(T，K)←Fake：A(T，K)=1]|≤(n-1)

斷言3對于任意敵手A，均有|Pr[(T，K0)←Fake；K1←Fp2；b←{0，1}：A(T，Kb)=b]|=。

綜合以上三個斷言可知：

qE次詢問的過程都是類似的，因此2|Pr[T，K0]←Real，K1←Fp2，b←{0，1}：A(T，Kb)=b]-Pr[T，K0]←Fake，K1←Fp2，b←{0，1}：A(T，Kb)=。

定理1證畢。

3.2 改進的SIBDII協議

由于BD協議的通信量較高，故考慮使用樹形結構的BDII協議。在廣播版本中，BDII協議的每個用戶的通信量和計算復雜度均為O(log(n))，故本節結合SIDH協議給出優化的SIBDII協議。協議中n個用戶被標識為1，2，…，n(n為偶數)，且用戶按照其標識被依次放置于樹形結構上(如圖3所示)。

圖3 BDII協議中的二元樹

從圖3中可以發現，用戶Ui位于樹的第■log2(i+1)」層。記用戶Ui的父母、左孩子和右孩子的標識分別為parent(i)、lchild(i)和rchild(i)，U1和U2分別是對方的父母。則樹上所有除葉子節點之外的節點均有一個父母和兩個孩子。令ancestors(i)為用戶Ui的所有祖先的標識構成的集合，其中i∈ancestors(i)但1，2?ancestors(i)。為了保證用戶Ui和Uparent(i)在公共曲線E的兩個不同子集中進行計算，令s(1)=0，s=s(i)=s(parent(i))+1(mod 2)用于標識兩個不同的子集。改進的SIBDII協議的公共參數與SIDH的參數相同，其具體執行過程如下：

第1輪：用戶Ui隨機選擇私鑰并計算Ri=Ps+kiQs，以〈Ri〉為 核 計 算 同 源φi：E→Ei=E/〈Ri〉，令，并將廣播給父母和兩個孩子。

第2輪：用戶Ui收到父母及其兩個孩子的公鑰和，并利用這些公鑰和自己的私鑰執行SIDH密鑰交換協議，可得。 然 后 用 戶Ui計 算(jparent(i)，i-ji，lchild(i)，jparent(i)，i-ji，rchild(i))，并 將 結 果 廣 播 給 其后代。

會話密鑰計算：用戶Ui利用哈希函數H:{0，1}*→{0，1}λ，其 中λ為 安 全 參 數， 計 算 會 話 密 鑰Ki=其中Xm=jparent(parent(m))，parent(m)-jparent(m)，m。

容易驗證，對于任意i均有Ki=H(j1，2)=K。值得注意的是，在改進的SIBDII協議中，仍使用加法運算來計算會話密鑰，從而提高了整個協議的效率。

定理2在SI-DDH假設下，改進的SIBDII群密鑰交換協議在隨機諭言機模型下可抵抗被動攻擊，并且滿足前向安全性。即如果有n個參與者，敵手攻擊k次會話過程，詢問qE次Execute，則該方案滿足。

證明：由于協議中沒有靜態密鑰，敵手可以忽略Corrupt詢問，故該協議滿足前向安全性。

假設改進的SIBDII群密鑰交換協議存在敵手A，可以構造區分器D調用A，以不可忽略的概率解決SI-DDH問題。敵手A可以詢問Execute、RevealKey和Test。設是一次執行過程的記錄，K是該過程得到的會話密鑰，則可定義兩個分布Real和Fake。其中Real是真實協議執行產生的 分 布，而Fake中 的是 在Fp2中 隨 機 選 取 的。記。

使用hybrid方 法計算|Pr[T，K0]←Real，K1←Fp2，b←{0，1}：A(T，Kb)=b]-Pr[T，K0]←Fake，K1←Fp2，b←{0，1}：A(T，Kb)=b]|

需要定義分布：

斷言4對于任意敵手A，均有|Pr[(T，K0)←Fake；K1←Fp2；b←{0，1}：A(T，Kb)=b]|=。

斷言5對于任意敵手A′，均有|Pr[(T，K)←Real：A′(T，K)=1]-Pr[(T，K)←Fake1：A′(T，K)=，其中k是敵手攻擊會話過程數目的上界。

斷言6對于任意敵手A，均有|Pr[(T，K)←Fake：A′(T，K)=1]-Pr[(T，K)←Fake1：A′(T，K)=1]|=。

總結上述三個斷言，可得：

定理2證畢。

4 協議比較

4.1 復雜度分析

改進的SIBD協議是BD協議的變形，本文更換了會話密鑰的計算方式，將j-不變量之間的乘法變為加法。原SIBD協議[5]中需要次乘法，而改進的SIBD協議中只需要(n-1)次乘法和n次加法。改進的SIBDII協議是BDII協議的變形，其計算復雜度為O(log(n))。

一個群密鑰交換協議的通信復雜度是由協議的輪數及各用戶每次交互信息的大小決定的。選擇參考文獻[9]中的參數，在λ比特安全強度下，p的比特長度應為6λ，則Fp2中元素的比特長度為12λ。由于曲線是定義在Fp2上的，故曲線和點的表示都需要12λ bit(見表1)。

表1 群密鑰交換協議的比較

表1中結果是以一個用戶為單位來計算通信復雜度和計算復雜度的。而對于一次密鑰交換過程中所有用戶交互的總信息量來說，改進的SIBD協議中所有 用 戶 交 互 信 息 的 總 和 為(12■log2(n+1)」+96)nλ bit，改進的SIBDII協議中所有用戶交互信息的總和為。

4.2 環形結構和樹形結構的比較

通過兩類群密鑰交換協議的通信復雜度和計算復雜度的比較可以發現：在樹形結構的群密鑰交換協議中，每個用戶的通信復雜度和計算復雜度都是O(log(n))級別的；而在環形結構的群密鑰交換協議中，通信復雜度和計算復雜度都是O(n)級別的(其中n為用戶數量)。這是否意味著基于樹形結構的群密鑰交換協議更好呢？本小節主要比較了環形結構和樹形結構在應用場景和計算性能等方面的表現。

首先假定協議的各個參與方的計算能力相當。否則，若存在一個可信用戶Ui，其計算能力遠大于其他用戶的計算能力，則可以使用環形結構的變形：用戶Ui與其他n-1個用戶分別交互獲得密鑰，進行計算后再統一廣播給其他參與方。此時用戶Ui的計算復雜度是其他用戶的n-1倍。在通信復雜度方面，記B是廣播所需通信量，P是點對點交互所需的通信量，則用戶Ui的通信量是2B+(n-1)P，其他用戶的通信量為2P。

在計算復雜度方面，如果各個參與方的計算能力相當，環形結構的計算復雜度為O(n)量級，而樹形結構的計算復雜度為O(log(n))量級，因此樹形結構更優。在通信復雜度上，環形結構中用到了廣播的通信模式，而樹形結構中用到的是多方傳播的通信模式。由于協議的參與方數量有限，因此此處不區分廣播和多方傳播的通信復雜度，則有如下比較(見表2)。

表2 樹形結構和環形結構中單用戶通信量比較

總之，盡管使用了環形結構的BD協議具有很好的代數結構，但是由于其總體的通信復雜度高，故很少被應用于實際場景中[12]。

5 結論

本文主要利用SIDH協議構造了兩個改進的群密鑰交換協議。通過安全性證明，本文所提出的協議可以歸約到SI-DDH問題，因此在量子攻擊下是安全的，此外，通過與現有的基于超奇異同源的群密鑰交換協議比較，所提協議的計算復雜度和通信量都更低。