格上基于KEM的認證密鑰交換協(xié)議

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

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

0 概述

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

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

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

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

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

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

1 相關(guān)知識

1.1 密文壓縮算法

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

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

1)壓縮函數(shù):

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

2)解壓縮函數(shù):

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

1.2 帶消息恢復(fù)的簽名算法

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

定義21個帶消息恢復(fù)的簽名算法包括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函數(shù)與Decode函數(shù)

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

Encode(v∈{0,1}n)

輸入k

對于i從0到n-1循環(huán)執(zhí)行:

ki←vi·?q/2」;

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

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

輸出k

輸入k′,對于i從0到n-1循環(huán)執(zhí)行:

若t

否則k′i←0;

輸出k′

1.4 AKE協(xié)議安全模型

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

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

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

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

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

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

2 算法設(shè)計及方案構(gòu)造

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

2.1 系統(tǒng)建立階段

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

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

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

2.2 會話密鑰的協(xié)商階段

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

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

圖1 格上基于KEM的AKE協(xié)議交換過程

3 安全性分析

3.1 正確性證明

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

3.2 安全性證明

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

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

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

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

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

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

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

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

4 性能分析

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

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

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

表1 AKE協(xié)議效率分析與對比

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

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

5 結(jié)束語

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