標準模型下格上的密鑰封裝機制*

趙宗渠，范 濤，彭婷婷，葉 青，秦攀科

河南理工大學 計算機科學與技術學院，河南 焦作 454150

1 引言

近幾年，網絡信息技術飛速發展，人們在享受便利的同時，存在著信息泄露的風險，信息安全的發展要遠遠滯后于信息產業的發展，人們的財產和安全面臨嚴重的威脅。如何保證數據傳輸時的機密性和完整性等重要性質是我們要面臨的重要問題。密碼技術在保障信息安全方面起著至關重要的作用，其中密鑰可以對信息進行加密、簽名、認證等，保證密鑰的安全性是密碼技術的關鍵環節。密鑰封裝機制（key encapsulation mechanism，KEM）使得發送者和接受者能夠安全地共享會話密鑰，這個會話密鑰使得通信雙方可以通過密碼技術實現一個安全的通信信道。

絕大多數密鑰封裝機制采用非對稱的加密方法。在密鑰封裝機制中，發起方運行一個封裝算法產生一個會話密鑰以及與之對應的密文，也稱為會話密鑰的封裝，隨后將會話密鑰封裝發送給接收方；接收方運行解封裝算法得到與發起方相同的會話密鑰。在這個過程中，要保證雙方獲得的會話密鑰必須是一致和新鮮的，同時不會泄露會話密鑰的相關信息。

Shoup[1]最先在2000年提出密鑰封裝機制方案，并在2004年和Cramer[2]提出了混合加密理論。這種加密理論分為密鑰封裝機制和數據封裝機制（data encapsulation mechanism，DEM），把這兩部分相結合進行數據傳輸和加密，稱為KEM-DEM模式。單純的KEM-DEM模式有效地解決了密鑰分發困難、用戶管理密鑰困難、傳輸明文信息過大等問題，但是這種模式也存在著問題，無法為用戶提供認證性，同時存在各種攻擊，使密鑰有泄漏的風險。這就需要設計一個安全高效的認證密鑰交換協議（authenticated key exchange，AKE），由于密鑰封裝機制的簡潔性和高效性，因而采用這種模塊化的方法來構造密鑰交換協議是非常方便的。

Shoup[1]在提出密鑰封裝機制概念的同時，給出了幾個密鑰封裝機制方案，包括基于RSA公鑰密碼算法的KEM和基于ECC（elliptic curve cryptography）公鑰密碼算法的KEM等。這些方案都是基于大整數分解和離散對數等困難問題。2003年，Dent[3]給出了密鑰封裝機制的一般構造法：由公鑰加密方案構造密鑰封裝機制，并給出了相應的安全性證明。Kiltz[4]在2007年設計了一個新的密鑰封裝機制并用它構造了一種KEM-DEM方案，與之前存在的密鑰封裝機制相比，此方案具有公鑰、私鑰和封裝的密文更短等優點。2010年，Kiltz與Jager等人[5]基于DH假設提出了一個安全高效的密鑰封裝機制，此方案是第一個在標準模型下可證明安全性為選擇密文安全的（chosen-ciphertext security，CCA-secure）。

雖然新的協議不斷涌現[6]，大多數都具備可證明安全性，但是基于格的可證明安全的方案還很少。格密碼作為后量子安全公鑰密碼體制的重要基礎理論，可以抵抗量子攻擊，同時具有較低的計算復雜性，構造格上的密鑰封裝機制還需進一步研究。2014年，Peikert[7]提出一種基于理想格的密鑰封裝機制，將加密方案與一個新的和解機制相結合，從而構造出一種選擇明文安全的（chosen-plaintext security，CPA-secure）高效密鑰封裝機制體制，借助環上LWE（learning with errors）問題，得到了更短的密鑰長度，封裝的密文膨脹率也得到了很大的優化，并以此作為AKE協議的設計原語。這為格上密鑰交換協議（lattice based authenticated key exchange，LBAKE）的設計與發展做出了重要貢獻。在此之后，格上密鑰封裝機制不斷發展，在效率、明密文長度和安全性等方面都有了進一步的優化[8-11]。2017年，Albrecht等人[12]提出了基于環上帶誤差學習問題的選擇密文安全的密鑰封裝機制，并指出方案是緊致和安全的。Bos等人[13]推出了Kyber系列算法，其中包括具有抗選擇密文攻擊（chosen ciphertext attacks）安全性的密鑰封裝方案Kyber。Kyber系列算法在模格上基于模LWE問題設計，這使得算法既具有基于環LWE的方案的高效率，而且其安全性更為可靠。基于NTRU（number theory research unit）格構造密鑰封裝機制是一個新的思路[14-15]，在方案通訊量方面有了很大的提高。

2012年，Fujioka等人[16]利用密鑰封裝機制提出了認證密鑰交換協議的一個通用構造，稱為GC協議。GC協議需要同時使用選擇明文安全的密鑰封裝機制和選擇密文安全的密鑰封裝機制，通過構造格上滿足要求的密鑰封裝機制，可得到基于格的密鑰交換協議。這種構造將密鑰封裝機制作為基本的設計原語，在CK+模型下是可證明安全的。2013年，Ye等人[17]指出GC協議是不安全的，并給出了一個具體攻擊方法，最后指出改進的方法是及時刪除私密信息，使得攻擊者無法獲得會話消息。這種改進雖然可以預防GC協議中某種特定攻擊，但并沒有解決部分消息缺乏認證的現象。本文提出的密鑰封裝機制在封裝的密鑰中引入發送者的身份信息，使密鑰封裝機制具有可認證性，可以抵抗消息重放和信息重組等假冒攻擊。

為使格上密鑰封裝機制適用于多種類型的密鑰交換協議方案，需要解決密鑰封裝機制中密鑰生成困難和缺乏消息認證的問題，本文提出一種格上密鑰封裝機制。主要貢獻有以下幾方面：（1）將一個新型陷門函數[18]與帶誤差學習算法[19]相結合，直接對會話密鑰進行加密，降低了算法的復雜度；（2）在封裝的密鑰中引入參與者的身份信息，使接收方能夠驗證信息的來源，解決密鑰交換協議中存在的冒充攻擊；（3）采用密文壓縮技術[13]，將密文元素從?q映射到上，其中d＜lbq。由于密文元素的低位比特主要是噪音信息,丟掉這些信息，對恢復其所加密的密鑰影響不大。在標準模型下，其安全性為可證明的選擇密文安全，適用于多種類型基于格的密鑰交換協議方案。

2 基礎知識

2.1 格的相關定義

定義1設b1,b2,…,bm是空間Rn上m個線性無關向量，定義格，向量組b1,b2,…,bm為一組格基。

定義2（q元格） 設，且滿足Ax=umodq，定義：

定義3（高斯離散分布） 定義以向量c為中心，σ＞0為參數的格Λ上離散高斯分布為，其中。

定義4[20]（帶誤差學習問題（learning with errors））給定一個實數記為[0,1)上的一個實數群，定義ψα為?上的中心為0，標準差為并且模1的正態分布；定義為q?上的中心為0，標準差為并且模q的正態分布。

任取一個高斯分布χ和一個向量，給出在上的變量(a,aTs+x)，其中是均勻分布而x∈?q是從χ中抽樣得到。給定整數q=q(n)和?q上的一個高斯誤差分布χ，帶誤差學習問題LWEq,χ的目的是以不可忽略的概率區分分布Aq,χ=(a,aTs+x)和分布A'=(a,b)，其中b為隨機選取的，在?q上是統計均勻的。關于某個隨機的秘密和均勻分布，也稱判斷性LWE問題，該問題的難解性不低于格上GapSVP難題。

2.2 困難問題與假設

引理1[18]設整數n≥1，q≥2和充分大的，可逆的編碼函數。公開的本原矩陣。存在高效陷門生成算法，輸出矩陣和陷門矩陣，陷門尺寸，其中，A在上是統計均勻的。

引理2[18]令為一個帶有參數s的δ-亞高斯隨機矩陣。存在一個常數C＞0對于任何t≥0，有。

引理3[18]設Λ??n是一個格，對于ε∈(0,1)令r≥ηε(Λ)，對于任何c∈span(Λ)，得到。

引理4[20]設Λ是一個格，令u∈?n為任意向量，r,s＞0為兩個實數，令。假設對于滿足。通過從DΛ+u,r中采樣并加上一個從vs中選取的噪聲向量可以得到一個在?n上的連續分布Y。則Y和vt的統計距離不超過 4ε。

引理5[20]設Λ是一個格，令z,u∈?n為任意向量，r,α＞0為兩個實數，令。假設對于滿足。存在分布，其中v的分布取決于，e是一個正態變量并且標準差為，分布是在統計上距離小于4ε的正態變量并且標準差為。在高斯分布上的統計距離小于 4ε。

引理6[21]（剩余散列） 設H是一個2-universal的，從定義域X到值域Y的哈希函數簇。則對于均勻獨立選取的h←H和X←X，(h,h(X))在H×Y上是均勻分布的。

2.3 密文壓縮技術

定義5（壓縮函數[13]） 設，滿足。

定義6（解壓縮函數[13]） 設，滿足。

引理7[20]x'=Decompressq(Compressq(x,d),d)，滿足，其中 |x'-xmod±q|在Bq上服從均勻分布，且在Bq-1上此分布整數大小相等。

2.4 密鑰封裝機制模型

設n=n(λ)是一個多項式，引入發送者的身份信息，定義一個算法三元組(Gen,Enc,Dec)（密鑰空間為{0,1}n）：

（1）(pk,sk)←Gen(1λ)：密鑰生成算法，生成安全參數為λ∈?的公鑰pk和私鑰sk。

（2）(C,(K||ID))←Enc(pk,ID)：密鑰封裝算法，發送者選取確定身份信息ID∈{0,1}n1生成密文C及服從均勻分布的對稱密鑰K∈{0,1}n。

（3）(K||ID)←Dec(sk,C)：密鑰解封算法，私鑰sk的持有者解密密文C得到密鑰K和身份信息ID或錯誤標標志符⊥。密文的一致性，要求對所有K∈{0,1}n和 (C,(K||ID))←Enc(pk)，有 Pr[Dec(sk,C)=(K||ID)]=1。

2.5 KEM的安全性定義

允許敵手自適應地訪問解封裝oracle得到與密文C對應的會話密鑰K。執行如下游戲：

（1）挑戰者運行密鑰生成算法Gen(1λ)獲得公、私鑰(pk,sk)，并把公鑰pk給攻擊者。

（2）攻擊者可以自適應地選擇一些密文C進行解封裝詢問，挑戰者用Dec(sk,C)進行應答，并把解封裝會話密鑰K給攻擊者。

（3）在進行一系列的解封裝查詢后，攻擊者準備接受挑戰，挑戰者利用封裝算法Enc(pk,ID)獲得密文C*和會話密鑰K，選取比特值b∈{0,1}，如果b=1則取K*為K，否則取K*為一個隨機選取的等長的會話密鑰，挑戰者將C*和K*給攻擊者。

（4）進行步驟（2）中的操作，唯一的限制是不能用C*直接詢問。

（5）詢問結束后，攻擊者A輸出b'。

攻擊者的優勢被定義為：

密鑰封裝機制的選擇密文安全性是指任何多項式時間攻擊者在上述游戲中的優勢是可忽略的。

3 方案構造

3.1 密鑰封裝機制

本文根據文獻[18]提出的算法，在封裝的密鑰中引入身份信息，并對封裝后的密文進行壓縮處理，構造出格上密鑰封裝機制。

KEM：KeyGen(1n)：選取均勻隨機矩陣，，滿足。輸出矩陣和其陷門矩陣，輸出pk=A,sk=R。

KEM：DeCap(sk=R,CT=(u,b'))，其中，計 算。

（1）若CT沒有解析出來或者u=0，則輸出⊥。否則，通過訪問來獲得值和滿足，如果訪問失敗，則輸出⊥。

（3）v=b-emod2q，其中，若，則輸出 ⊥ 。

3.2 正確性證明

證明本方案的解密是正確的，對于任意的(pk,sk)←KeyGen(1n)和封裝密鑰K∈{0,1}w1，有Pr[Dec(sk,Enc(pk,ID))=K||ID]=1。

(A,R)←Gen(1n)。通過引理2，得到。考慮對于任意K∈{0,1}w1由Enc(A,ID)生成。通過引理3，得到和。令，得到，對于足夠大的得到。訪問 Invert通過Dec(R,(u,b'))返回e。通過引理7，b″=Decompressq(Compressq(b',d),d)，經計算滿足。對于，得到所需的。

2(sTAumodq)是格中的一個元素，SK∈Λ(GT)/2Λ(GT)是其中的一個陪集，因此。從而得到封裝密鑰并驗證發送者身份。 □

4 安全性證明

首先開始一系列的混合游戲。

游戲H0：真實的適應性選擇密文攻擊游戲。

游戲H1：重新生成公鑰A并構造了挑戰密文，通過解密詢問，解封得到相應的明文，和游戲H0相比在統計上是不可區分的。在實驗的開始選取了非零值u?← U 并令公鑰為，其中的A和R和游戲H0中的選取方法一樣（其中。對于任意選擇的u*，矩陣仍然滿足均勻分布，因此不論矩陣A為何值，u*的值在統計上對攻擊者都是隱藏的。為了幫助解密查詢，隨機選取了使得。

使用解封裝算法DeCap和陷門R來對密文(u,b')執行解密詢問。在測試后（如果u=0，則輸出⊥），訪問得到，其中（如果訪問失敗，則輸出⊥）。

按照3.1節中密鑰封裝機制方案的解密算法DeCap(sk=R,CT=(u,b'))，執行其第（2）步和第（3）步，其中e∈?m，v=b-emod2q，并在第（3）步中用代替R。

因為u*在統計上是被隱藏的，可以得到u≠u*。通過集合U滿足的性質，得到是可逆的。根據需求訪問Invert，若不存在e，則游戲H1和H2都會返回⊥；若存在e，則滿足（其中的值可能不同）。在e的約束條件下，游戲H0,H1都得到。

最后在游戲H1中選取并生成消息K∈{0,1}w1和挑戰密文(u,b)。令u=u*，選取，不 選 取e1。 令，其 中，輸出。證明攻擊者在擁有公鑰pk和解密詢問Invert的情況下，在統計上不可區分輸出(u,b)的分布和游戲H0中(u,b)的分布。首先，因為u的值和公鑰pk無關，且通過的構造，得到u、和游戲H0中有著相同的分布。接著通過替換，得到，根據引理 4和引理5，對于固定值，通過隨機選擇ri（來自公鑰取決于值）和，每個ri在格的陪集上是一種獨立的離散高斯分布，在滿足的情況下，任意在D?,s上的分布是不可區分的。

游戲H2：只改變了挑戰密文中的構建方法，使其在中滿足均勻分布。在構造公鑰pk、應答解密查詢Invert和構造b1的方法上，和游戲H1完全相同。首先在（離散化）LWE困難問題的假設下，是不可區分的，其中滿足均勻分布，（其中）或者兩者之一滿足均勻分布，因此游戲H和1游戲H2在計算上是不可區分的。除了在構建公鑰和挑戰密文時使用給定的和，可以執行和這兩個游戲完全一樣的操作來分別有效地模擬任意游戲H1或者游戲H2。

現在通過引理6，在游戲H2中當私鑰R被選取時，是均勻不可區分的。因此，挑戰密文對于任何加密過的明文信息有著相同的分布。

由文獻[18]可知，當明文空間為{0,1}w時，方案是CCA安全的。本文設置封裝密鑰空間為，其中w1＜w。假設本文方案中攻擊者的優勢為，即攻擊者可以構造與明文對應的密文，并且能夠以不可忽略的優勢區分明文，那么挑戰者可以構造與M(M1||ID)相對應的密文，并且以不可忽略的優勢區分明文，與文獻[18]方案中的CCA安全矛盾。因此，顯然當安全參數w1滿足條件時，攻擊者的優勢是可以忽略的。

5 性能分析

下面從計算時間復雜度和通信量兩方面來評價本文方案的性能。根據文獻[18]提供的參數，對方案的計算成本和通信代價進行分析。設置安全參數n=284，q=224，則w1=6 816，明文、密文、會話密鑰空間滿足安全長度，格的維數為m=13 632且足夠大，滿足格上困難問題，矩陣點乘運算表示為s，加法運算表示為p。方案性能如表1所示。

Table 1 Performance of KEM表1 方案性能

由表1看出，在通信量方面，因為消除了運算密鑰，所以公私鑰尺寸明顯縮小，采用密文壓縮技術，大大縮短了密文的尺寸，有效降低了通信代價。本文方案的封裝和解封裝采用對偶LWE算法，在陷門生成部分采用的是更為高效的陷門函數，所需格的維數更低。另外，該陷門函數的原像采樣算法，利用sub-Gaussian分布的相關性質[18]優化了以往的原像采樣技術，且采樣過程可以并行進行，使時間復雜度更低。因此，本文密鑰封裝機制具有實際應用可行性。

6 應用分析

文獻[16]利用密鑰封裝機制提出了認證密鑰交換協議的一個通用構造，稱為GC協議，本文構造的選擇密文安全的密鑰封裝機制適用于此協議，同時在封裝的密鑰中引入參與者的身份信息，可以抵抗來自外部攻擊者的冒充攻擊。具體協議如下：

設k是安全參數，(KeyGen,EnCap,DeCap)是本文構造的CCA安全的密鑰封裝機制，(wKeyGen,wEnCap,wDeCap)是一個CPA安全的密鑰封裝機制。

利用本文構造的密鑰生成算法KeyGen生成用戶UA的密鑰對(skA,1,pkA,1)←KeyGen(1k)，同時為用戶UB生成密鑰對(skB,1,pkB,1)←KeyGen(1k)，用戶UA作為發送方與接收方用戶UB進行密鑰交換，GC協議的具體步驟如下：

（1）用戶UA隨機地選擇臨時密鑰rA，利用本文構造的密鑰封裝算法EnCap生成(CTA,1,KA,1)←EnCap(pkB,1,idA)，運用wKeyGen由隨機選取的rA獲得臨時密鑰對(pkA,2,skA,2)←wKeyGen(1k,rA)，然后發送消息(UA,UB,CTA,1,pkA,2)給用戶UB。

（2）用戶UB收到消息(UA,UB,CTA,1,pkA,2)后，隨機地選擇臨時密鑰rB，計算(CTB,1,KB,1)←EnCap(pkA,1,idB)和 (CTB,2,KB,2)←wEnCap(pkA,2,rB)，并發送消息(UA,UB,CTB,1,CTB,2)給用戶UA；用戶UB還依據所接收到的消息利用解封算法DeCap解封裝得到密鑰KA,1←DeCap(skB,1,CTA,1)，用戶UB通過驗證KA,1中的身份信息，可以判斷消息的來源是否為合法方，驗證成功后，利用隨機性提取器計算,，設定會話記錄為，基于偽隨機函數簇計算得到與用戶UA共享的會話密鑰。最后，用戶UB標識該會話為已完成并擦除所有會話狀態。

（3）用戶UA收到消息后，利用私鑰skA,1、skA,2解封裝得到密鑰，同樣的，通過驗證KB,1中是否包含用戶UB的身份信息，來確定信息的來源是否合法，若驗證成功，則進一步計算得到，設定會話記錄為，計算與用戶UB共享的會話密鑰。最后，標識該會話為已完成并擦除所有會話狀態。

對于GC協議，文獻[17]給出具體的攻擊方法。首先攻擊者UE在步驟（1）中，冒充用戶UA生成會話信息，并發送給用戶UB，用戶UB接收到消息后，完全按照步驟（2）進行操作，攻擊者UE截取用戶UB發送的會話信息。接著，攻擊者UE令用戶UA與另外一個誠實用戶UC進行密鑰協商，用戶UA按照步驟（1）把信息發送給用戶UC，用戶UC執行步驟（2），攻擊者UE截取用戶UC發送的消息并把之前截取用戶UB的信息與之重組替換，通過用戶UA運行解封裝算法，最終可以得到會話密鑰。

本文構造的密鑰封裝機制具備可認證性，在步驟（2）中，用戶UB收到消息后，運行解封裝算法得到KA,1，因為在KA,1中引入了發送者的身份信息，用戶UB可以通過驗證來判斷收到的密文消息是否和會話用戶UA身份一致，若發現不是用戶UA，則終止協議，從而抵抗來自外部攻擊者的冒充攻擊。

7 結束語

密鑰封裝機制可以有效地保證會話密鑰的機密性，使其在公開信道上能夠被安全地傳輸。利用陷門生成算法生成一個陷門函數，并與帶誤差學習算法相結合，提出一個標準模型下的格上密鑰封裝機制方案，解決了格上密鑰封裝機制陷門生成困難的問題，同時可以抵抗量子攻擊。在封裝的消息中引入參與者的身份信息，保證密鑰封裝機制機密性和可認證性。采用密文壓縮技術，減少通信代價，提高傳輸效率。在標準模型下，方案的安全性為選擇密文安全，并包含嚴格的安全性證明。

密鑰封裝機制適用于密鑰交換協議。本文設計的密鑰封裝機制在效率和安全性方面較以往方案均有提高，但是利用密鑰封裝機制構造可認證的密鑰交換協議存在運行次數較多的問題。因此，如何優化密鑰封裝機制的運行次數，進一步提高協議的效率將是下一步的研究重點。

《計算機工程與應用》投稿須知

中國科學引文數據庫（CSCD）來源期刊、北大中文核心期刊、中國科技核心期刊、RCCSE中國核心學術期刊、《中國學術期刊文摘》首批收錄源期刊、《中國學術期刊綜合評價數據庫》來源期刊，被收錄在《中國期刊網》、《中國學術期刊（光盤版）》、英國《科學文摘》（SA/INSPEC）、俄羅斯《文摘雜志》（AJ）、美國《劍橋科學文摘》（CSA）、美國《烏利希期刊指南》（Ulrich’s PD）、《日本科學技術振興機構中國文獻數據庫》（JST）、波蘭《哥白尼索引》（IC），中國計算機學會會刊

《計算機工程與應用》是由中國電子科技集團公司主管，華北計算技術研究所主辦的面向計算機全行業的綜合性學術刊物。

辦刊方針堅持走學術與實踐相結合的道路，注重理論的先進性和實用技術的廣泛性，在促進學術交流的同時，推進科技成果的轉化。覆蓋面寬、信息量大、報道及時是本刊的服務宗旨。

報導范圍行業最新研究成果與學術領域最新發展動態；具有先進性和推廣價值的工程方案；有獨立和創新見解的學術報告；先進、廣泛、實用的開發成果。

主要欄目理論與研發，大數據與云計算，網絡、通信與安全，模式識別與人工智能，圖形圖像處理，工程與應用，以及其他熱門專欄。

注意事項為保護知識產權和國家機密，在校學生投稿必須事先征得導師的同意，所有稿件應保證不涉及侵犯他人知識產權和泄密問題，否則由此引起的一切后果應由作者本人負責。

論文要求學術研究：報道最新研究成果，以及國家重點攻關項目和基礎理論研究報告。要求觀點新穎，創新明確，論據充實。技術報告：有獨立和創新學術見解的學術報告或先進實用的開發成果，要求有方法、觀點、比較和實驗分析。工程應用：方案采用的技術應具有先進性和推廣價值，對科研成果轉化為生產力有較大的推動作用。

投稿格式1.采用學術論文標準格式書寫，要求文筆簡練、流暢，文章結構嚴謹完整、層次清晰（包括標題、作者、單位、摘要、關鍵詞、基金資助情況、所有作者簡介（含通訊作者電子信箱）、中圖分類號、正文、參考文獻等，其中前6項應有中、英文）。中文標題必須限制在20字內（可采用副標題形式）。正文中的圖、表必須附有圖題、表題，公式要求用MathType編排。論文字數根據論文內容需要，不做嚴格限制，對于一般論文建議7 500字以上為宜。2.請通過網站（http://www.ceaj.org）“作者投稿系統”一欄投稿（首次投稿須注冊）。