格上基于KEM的認證密鑰交換協議

趙宗渠,黃鸝娟,范 濤,馬少提

(河南理工大學 計算機科學與技術學院,河南 焦作 454000)

0 概述

認證密鑰交換(Authenticated Key Exchange,AKE)協議可使通信方在有主動敵手的信道上建立安全的共享會話密鑰,同時實現彼此身份的相互認證,在后續的對稱密碼中能夠保證數據的完整性和真實性。目前多數AKE協議的安全性依賴于大整數分解和離散對數的Diffie-Hellman[1]困難問題,隨著量子計算技術的發展,此類問題在多項式時間算法下是可解的,這將給現有協議帶來安全威脅。格上構造的公鑰密碼體制因其運算簡單、可并行性和抗量子攻擊的優點,將在后量子時代成為最有效的解決方案之一,基于格的AKE協議因此成為學術界的研究熱點。

基于格的AKE協議[2-4]可以抵抗量子攻擊,解決經典困難問題下協議的安全性問題,但不能降低通信復雜度并實現認證。文獻[5]在標準模型下構造高效的口令認證密鑰交換協議,但該協議不能抵抗量子攻擊。文獻[6]基于LWE構造了無環密鑰交換協議,雖然該協議可以抵抗量子攻擊,但無法實現客戶和服務器的相互認證。文獻[7]提出一個基于理想格的密鑰交換協議,使通信方以顯著概率計算得到一個相同的會話密鑰,然而該協議提取的會話密鑰只具有高熵,并不是均勻分布的,雖然通信方可以利用隨機提取器得到均勻分布的共同比特,但這會降低協議的效率。文獻[8]提出一種基于理想格的密鑰封裝機制(Key Encapsulation Mechanism,KEM),文獻[9]在此基礎上結合一種簡單的低帶寬協調技術提出一種變形的錯誤協調機制,結合環LWE困難問題構造密鑰交換協議,使加密方案的密文長度縮短了近兩倍,通信方可以直接得到均勻的共同比特。

文獻[10]結合Peikert式錯誤協調機制構造了適用于TLS協議的Diffie-Hellman式密鑰交換協議,并給出具體的實現參數,其中會話密鑰能達到較高的量子安全級別,但錯誤協調機制模數較大,使得通信量較大,降低了協議的效率。文獻[11]基于R-LWE困難問題,利用格解碼算法結合中心二項分布提出了NewHope密鑰交換協議,優化了文獻[10]的密鑰交換協議,擴大了可容忍的錯誤范圍,減少了模數,節省了通信量。文獻[12]提出的NewHopeSimple方案,使用加密的構造方法代替調和技術,降低了協議的計算復雜度。文獻[13]基于加密的構造方法提出抗選擇密文攻擊安全的Kyber系列密鑰封裝算法,其采用密鑰壓縮技術對需要發送的公鑰和密文進行壓縮,降低了通信量。

隨著格密碼的快速發展,密鑰交換協議的效率已得到大幅提高,但目前多數協議都是Diffie-Hellman式密鑰交換協議[7,10,14-16],只能提供被動安全性,不能實現相互認證,也不能抵抗中間人攻擊,而實際應用中必須要考慮網絡上的主動攻擊者。因此,構造認證密鑰交換協議來抵御主動攻擊是研究趨勢所向,而基于KEM方案構造認證密鑰交換協議是一種可行的方法。

文獻[17]在NTRU格Diffie-Hellman式密鑰交換協議的基礎上,結合帶消息恢復功能的簽名算法與KEM方案實現協議的認證性。與傳統簽名算法相比,該方案既增加了安全性又提高了通信效率。文獻[18]將具有CCA安全和CPA安全的KEM方案相結合,提出了適用于格的可認證密鑰交換協議的通用架構,即GC協議,其將KEM方案作為基本的設計原語,在CK+模型下是可證明安全的。文獻[19]提出的CCA安全的密鑰封裝機制,可由基本的CPA安全的密鑰封裝機制獲得,使用這一方法,Kyber構造了具有認證性的密鑰交換協議Kyber.AKE。文獻[20]設計了格上基于R-LWE的三方PAKE協議,實現了通信方的顯式認證,可避免兩方認證密鑰交換協議的局限性,但該協議存在會話密鑰的不一致性問題。

為實現Diffie-Hellman式密鑰交換協議的認證性并使其能夠抵抗量子攻擊,本文結合帶消息恢復功能的簽名算法,基于R-LWE構造一個KEM方案。在協議執行時采樣隨機種子生成協議雙方的公共參數,防止攻擊者利用固定公共參數攻擊協議,以保證前向安全性。發送方選擇定比特長的隨機字符串,每4個元素使用Encode函數[12]編碼其中的一個比特,編碼后的環元素可容忍更大的錯誤,從而降低模數,縮減通信量。此外,在保證密文恢復完整性的前提下對密文元素使用Compress壓縮函數進行壓縮,減輕服務器的傳輸負荷,同時利用帶有消息恢復功能的簽名算法實現協議的認證性。

1 相關知識

1.1 密文壓縮算法

密文壓縮技術是減少用戶通信量的有效方法,其對密文元素進行壓縮,丟掉密文元素的低位比特,即部分噪音信息。在保證密文恢復完整性的前提下,有效減少通信量,減輕服務器的傳輸負荷。將密文元素從q映射到2d上,其中d

定義1一個密文壓縮算法包括2個多項式時間算法,即壓縮算法Compressq(x,d)和解壓縮算法Decompressq(x,d)。

1)壓縮函數:

Compressq(x,d)=?(2d/q)·x」mod+2d

2)解壓縮函數:

Decompressq(c,d)=「(q/2d)·c?

1.2 帶消息恢復的簽名算法

文獻[14]提出帶消息恢復的簽名算法,其中每一個用戶都有一對密鑰,即一個需要公開的公鑰和一個需要秘密保存的私鑰。當用戶需要對某個消息m進行簽名產生對應的數字簽名Sig時,即需要使用自己的私鑰和消息m=(m1‖m2)進行簽名運算,運算結果就是簽名值。簽名值只需要消息m中的部分消息m2表示。任何人都可以使用該用戶的公鑰來恢復消息和驗證簽名是否正確,并且沒有人能夠在用戶私鑰未知的前提下偽造出一個合法的消息簽名對。此算法可解決簽名消息過長的問題。

定義21個帶消息恢復的簽名算法包括3個多項式時間算法,即簽名密鑰生成算法SigKeyGen(1λ)、簽名算法Sig((f,g),m=(m1‖m2))和驗證算法Ver(h,σ=(s1,s2,m2))。

1)簽名密鑰生成算法SigKeyGen(1λ):{f,g←Df,h←f/gmodq}得到(Ks,Kv)=(g,h)。

2)簽名算法Sig((f,g),m=(m1‖m2)):{t=(m1+F(H′(m)) modq‖H′(m))s1,s2←Ds滿足(f/g)s1+s2=tmodq,得到σ=(s1,s2,m2)。

3)驗證算法Ver(h,σ=(s1,s2,m2)):(t1‖t2)←hs1+s2modq,m1←t1-F(t2)modq,若(s1,s2)‖

1.3 Encode函數與Decode函數

定義3[10]用戶A選取v∈{0,1}n環元素k,即每4個q元素中編碼v的一個比特,用戶B根據收到的k′,取在{0,1,…,q-1}范圍中的4個系數減去?q/2」,累積它們的絕對值,若得到的結果小于q則vi取1,否則取0。可容忍更大的錯誤,從而降低了模數,縮減了通信量。Encode函數和Decode函數的具體描述如下:

Encode(v∈{0,1}n)

輸入k

對于i從0到n-1循環執行:

ki←vi·?q/2」;

ki+n←vi·?q/2」;

ki+2n←vi·?q/2」;

輸出k

輸入k′,對于i從0到n-1循環執行:

若t

否則k′i←0;

輸出k′

1.4 AKE協議安全模型

模型中會話密鑰的安全性通過模擬者和攻擊者之間的游戲定義。首先攻擊者A選擇一定數量的誠實參與者,通過提供攻擊者以下查詢來建模攻擊者的能力:

3)Corrupt(i)。攻擊者A通過此查詢來腐化參與者i。要求被詢問的協議參與者返回參與者i的長期私鑰,同時稱參與者i被腐化(Corrupted)。

通過模擬一個挑戰者與攻擊者之間的游戲定義AKE協議的安全性。游戲分為以下4個階段:

第1階段攻擊者A可以進行任意除Test以外的查詢,預言機并給出相應答案。

第4階段攻擊者A結束游戲,輸出猜測值b′。

對于任意攻擊者A,如果A贏得上述游戲的優勢AdvA=|2Pr[b′=b]-1|是可忽略的,則稱該認證密鑰協商協議是安全的。

2 算法設計及方案構造

認證密鑰交換協議包括2個階段,即系統建立階段Setup和會話密鑰的協商階段KeyExchange。

2.1 系統建立階段

H1和H2分別是在{0,1}l1和{0,1}l2上的抗碰撞哈希函數,通信雙方分別使用帶消息恢復功能的簽名算法,選取{f,g←Df,h←f/gmodq},生成自己的簽名密鑰對:

SigKeyGen(1λ)→(KSA,KVA)=(gA,hA)

SigKeyGen(1λ)→(KSB,KVB)=(gB,hB)

2.2 會話密鑰的協商階段

用戶UA和用戶UB通過交換公共信息來協商出一個共享的會話密鑰,具體過程如下:

若按照上述協議執行,最終交易雙方得到相同的會話密鑰,即SKA=SKB,具體的交換過程如圖1所示。

圖1 格上基于KEM的AKE協議交換過程

3 安全性分析

3.1 正確性證明

若用戶UA和用戶UB誠實地運行協議,那么雙方獲得相同的密鑰SKA=SKB成立。

3.2 安全性證明

證明:通過一系列得模擬游戲,證明通信內容不會泄露秘密的信息,并證明通信雙方交換的密鑰與隨機數不可區分。設sid*表示測試會話標示符,攻擊者A嘗試區分會話密鑰SK和均勻隨機密鑰SK′,定義攻擊者A贏得游戲的優勢為:

Adv(A)=|Pr[b′=1|b=1]-Pr[b′=1|b=0]|

在簽名方案的強不可偽造性下,此修改不會改變攻擊者A的優勢。一旦偽造文件被發現,不需要運行完整個協議,簽名方案立即被破壞。同時,c的分布與其他一般分布不可區分,所以,猜測出c=bs′b+e″b+a×k的概率可以忽略。因為c=a(sas′b+k)+e″b+ea,根據引理2可知,sas′b+k的分布與χα的分布小于4ε,基本可以忽略,則游戲G1中c的分布接近游戲G0中c的分布,即A無法區分。若RLWEq,χ是困難問題,則:

|AdvG1(A)-AdvG0(A)|≤negl(n)

定義標記CorrectGuess來表示是否sk→⊥解密失敗或者sk1←sk2解密成功,模擬器P不會顯式地計算CorrectGuess的值。有:

標記CorrectGuess對游戲G5的比特b′無影響,這兩個事件是獨立的:AdvG5(A)=AdvG4(A)/2。

在最后的游戲中,測試會話的會話密鑰是真實隨機的,因此與隨機的情況沒有區別:AdvG7(A)=0。

通過以上游戲,可知攻擊者A的優勢是可忽略的。證畢。

4 性能分析

本節對所提出的格上基于KEM的認證密鑰交換協議方案進行性能分析,性能主要體現在3個方面:

1)發送方選擇定比特長的隨機字符串,將這個隨機字符串中每4個元素使用Encode函數編碼其中的一個比特,編碼后的環元素可容忍更大的錯誤,從而降低了模數,縮減了通信量。

2)使用Compress壓縮函數,對密文元素進行壓縮,在保證密文恢復完整性的前提下,有效減少通信量,減輕服務器的傳輸負荷。 3)利用帶消息恢復功能的簽名算法,對方案中發送消息進行簽名,在發送的過程中,用戶雙方只需要發送消息的部分值,有效降低了傳輸過程中的通信量。

表1 AKE協議效率分析與對比

本文方案和所對比的方案均為標準模型下構造。由表1可以看出,在通信量方面,本文方案采用Encode函數和Compress壓縮函數,大幅縮短了密文的尺寸,有效降低了通信代價,同時使用帶消息恢復功能的簽名算法,在保證協議認證性的同時,也降低了通信量,與文獻[10]方案相比,本文協議不但可實現相互認證,降低了通信量同時避免使用計算復雜的調和機制而使用計算簡單的加密機制,方案計算更加簡潔高效。本文協議的封裝和解封裝采用R-LWE困難假設,與文獻[6]相比,解決了密文尺寸過長的問題。

綜上可知,與同類方案相比,本文方案具有較低的通信量,計算復雜度也在可接受范圍內。因此,從方案的效率參數和計算效率分析,本文協議更具有實際應用價值。

5 結束語

認證密鑰交換協議被廣泛應用于互聯網安全協議和傳輸層安全協議中,可有效提高實體間的通信效率。本文基于R-LWE困難假設,以加密的構造方法代替Peikert錯誤協調機制,提出一種基于KEM的認證密鑰交換協議。將KEM和帶消息恢復功能的數字簽名相結合,實現協議的認證性,同時降低需要發送的簽名密文長度,大幅減少通信量。利用格上基于R-LWE問題構造的密碼系統具有密鑰、密文尺寸小的優點,可提高AKE協議效率,并且有效抵抗量子攻擊。本文方案基于R-LWE困難假設構造,而LWE的安全性較R-LWE更為穩健,下一步將考慮在維持較低通信量的情況下,基于LWE構造強安全的認證密鑰交換方案。