基于格的非交互式密鑰交換協(xié)議

鄒小花

摘要： 當(dāng)前網(wǎng)絡(luò)中廣泛使用的交互式密鑰交換協(xié)議，如SSL協(xié)議和TLS協(xié)議，由于密鑰建立過程的通信量較大，不適合物聯(lián)網(wǎng)中傳感器等資源有限的輕型網(wǎng)絡(luò)設(shè)備使用，因此提出一種基于格的非交互式密鑰交換協(xié)議。文章基于格理論的環(huán)上帶誤差學(xué)習(xí)困難性問題，使用Freire等人給出的非交互式密鑰交換協(xié)議形式化定義和安全模型對協(xié)議的安全性進行分析，通過攻擊者與挑戰(zhàn)者之間的博弈證明了協(xié)議的安全性。該協(xié)議具有抗量子攻擊安全性，能夠有效地提升物聯(lián)網(wǎng)的通信安全。

關(guān)鍵詞： 密碼學(xué); 密鑰; 格; 非交互式密鑰交換

中圖分類號：TP309? ? ? ? ? 文獻標(biāo)識碼：A? ? ? 文章編號：1006-8228（2021）10-01-04

Non-interactive key exchange based on lattice

Zou Xiaohua

（Science and Technology College of Nanchang Hangkong university， Nanchang， Jiangxi 332020， China）

Abstract： Currently， the interactive key exchange protocols widely used in the network， such as SSL and TLS， are not suitable for the light network equipment with limited resources such as sensors in the Internet of Things because of the large traffic in the key generation process. Therefore， a lattice based non-interactive key exchange protocol is proposed. In this paper， based on the hard problems of R-LWE from lattice theory， the security of the protocol is analyzed by using the formal definition and security model of non-interactive key exchange protocol proposed by Freire et al. And the security of the protocol is proved by the game between the attacker and the challenger. The protocol has anti-quantum attack security and can effectively improve the communication security of the Internet of Things.

Key words： cryptography; key; lattice; non-interactive key exchange

0 引言

保證數(shù)據(jù)通信安全性最常見同時也是最基本的方法是使用數(shù)據(jù)加密技術(shù)對傳輸數(shù)據(jù)進行加密以保證數(shù)據(jù)傳輸?shù)臋C密性。為實現(xiàn)數(shù)據(jù)加解密，通信雙方必須先進行密鑰的協(xié)商，通常借助于密鑰交換協(xié)議來實現(xiàn)。大多數(shù)存在的密鑰交換協(xié)議都是基于交互方式，比如SSL協(xié)議和TLS協(xié)議。這種類型的協(xié)議需要在二者之間進行一輪或多輪的通信交互。對于帶寬、電量、計算資源受限的輕型網(wǎng)絡(luò)設(shè)備（例如某些物聯(lián)網(wǎng)結(jié)點）而言，使用交互式密鑰交換來協(xié)商會話密鑰代價太大，難以實現(xiàn)長期、多次的協(xié)議執(zhí)行[4]。

為解決上述問題，采用非交互式的密鑰交換協(xié)議[5]用于計算和產(chǎn)生一個共享的密鑰，僅使用私有秘密信息和其他方的公開信息，通信雙方不進行交互。它具備了顯著的優(yōu)點，比如節(jié)省通信量和帶寬。同時，由于此類協(xié)議不需要消息交互，降低了攻擊者勝利的可能性，有效的加強了密鑰建立過程的安全性。

非交互式密鑰交換協(xié)議來源于Diffie-Hellman協(xié)議[6]，協(xié)議雙方的gx和gy值分別作為公鑰，x和y為相對應(yīng)私鑰，然后Diffie-Hellman協(xié)議是一個非交互式密鑰交換協(xié)議。Bernstein提供了一個非交換式密鑰交換協(xié)議[7]，基于橢圓曲線，并且設(shè)計了安全模型。還有進一步的工作是結(jié)合基于身份密碼學(xué)，提供一個基于身份分級的非交互式密鑰協(xié)商協(xié)議[8-10]。在基于身份的密碼體系中，私鑰產(chǎn)生于密鑰生成中心，用戶的公鑰是它的識別信息，目的是為了解決在PKI體制中管理證書和存儲問題。

上述方案的一個嚴(yán)重問題在于未經(jīng)過嚴(yán)格的安全性模型分析安全性，因此可能存在潛在的安全風(fēng)險點。Freire和Hofheins等人對非交互協(xié)議的安全性進行了系統(tǒng)分析，并給出了嚴(yán)格的形式化定義和安全模型[11]。

上述方案的安全性是基于大整數(shù)分解的難點或者離散對數(shù)問題。在量子計算機產(chǎn)生后，這些方法將遭到非常大的安全隱患[12]。它是當(dāng)前的迫切需求?；诟竦拿艽a體制是后量子時代密碼安全體制的最佳方案[13]。在當(dāng)前密碼學(xué)研究領(lǐng)域已經(jīng)出現(xiàn)了基于格的公鑰密碼方案[14-15]、密鑰交換協(xié)議[16]、數(shù)字簽名方案[17]等密碼學(xué)本原，但是仍未出現(xiàn)基于格的非交互式密鑰交換協(xié)議。目前密碼學(xué)領(lǐng)域的緊迫目標(biāo)是研究抵抗量子攻擊的密碼學(xué)方案，后量子時代安全密碼體制的最重要的方案之一就是基于格的密碼體制。

格理論的帶誤差學(xué)習(xí)（Learning with Error）困難性問題作為本文使用的底層數(shù)學(xué)基礎(chǔ)，設(shè)計一個基于格的非交互式密鑰交換協(xié)議，并使用Freire等人[11]的安全模型證明協(xié)議的安全性。

1 非交互式密鑰交換協(xié)議的形式化定義和安全模型

使用Freire等人[11]的形式化定義和安全模型對協(xié)議進行設(shè)計和分析。

1.1 形式化定義

一個非交互式密鑰交換協(xié)議包括三個算法： CommonSetup，NIKE.KeyGen和SharedKey。同時還包含一個身份標(biāo)識空間IDS以及一個共享密鑰空間SHK。上述各算法的形式化定義為：

- Common Setup：輸入安全參數(shù)1k，輸出系統(tǒng)參數(shù)params;

- NIKE.KeyGen：輸入params和一個身份標(biāo)識 [ID∈IDS]， 輸出該ID對應(yīng)用戶的密鑰對（pk， sk）， 該算法是概率性的，任何用戶都可以執(zhí)行該算法;不失一般性，假設(shè)params包含在pk之中;

- SharedKey：輸入[ID1∈IDS]和對應(yīng)的公鑰pk1以及[ID2∈IDS]和對應(yīng)的私鑰sk2，輸出屬于集合SHK的共享密鑰，或者輸出一個失敗符號。

上述非交互式密鑰交換協(xié)議必須滿足參與雙方計算出相同共享密鑰的正確性要求，即SharedKey（ID1，pk1，ID2，sk2）=SharedKey（ID2，pk2，ID1，sk1）。

1.2 安全模型

非交互密鑰交換協(xié)議的安全性是通過攻擊者A和挑戰(zhàn)者C之間的博弈來產(chǎn)生。輸入 是以安全參數(shù)1k的C，使用CommonSetup算法， 將算法輸出的params傳遞給A。C進一步選擇一個隨機比特b，并回答A的查詢，直到A輸出對b的猜測[b]，A可以執(zhí)行以下查詢。

⑴ 注冊誠實用戶ID 此時C應(yīng)該注冊一個身份標(biāo)識為ID的誠實用戶，并將該用戶的pk返回給A。

⑵ 注冊被攻陷用戶ID A向C提供一個身份標(biāo)識ID和對應(yīng)公鑰pk，C記錄（corrupt， ID， pk）。

⑶ 用戶私鑰查詢 A向C提供一個誠實用戶的身份標(biāo)識ID，C向A返回該用戶的sk。

⑷ 共享密鑰揭示查詢 A向C提供兩個身份標(biāo)識ID1和ID2， 其中至少有一個是誠實用戶，另一個可以為被攻陷用戶;此時C應(yīng)用使用一個誠實用戶的私鑰和另一個用戶的公鑰執(zhí)行共享密鑰生成算法，并將結(jié)果返回給A;此查詢中如果兩個用戶均為誠實用戶，則稱為誠實揭示，如果一個用戶是誠實用戶，另一個用戶為攻陷用戶，則稱為攻陷揭示。

⑸ 測試查詢 A向C提供兩個誠實用戶的身份標(biāo)識ID1和ID2，C根據(jù)b的值向A返回ID1和ID2的共享密鑰或者一個同等長度的隨機值。A輸出對b的猜測值[b]。稱攻擊者A贏得該博弈，若b=[b]，定義攻擊者A在該博弈中的優(yōu)勢為。

[AdvAk=Prb=b-12]

若攻擊者A贏得的概率和1/2沒有顯著區(qū)別，則認(rèn)為非交互式密鑰交換協(xié)議是安全的。

2 格密碼學(xué)基礎(chǔ)

2.1 格

定義1（格） 格是空間Rm上n個線性無關(guān)向量，整數(shù)線性組合構(gòu)成的集合為{b1，b2，…，bn}，記為[LB={i=1nxibi|xi∈Z， i=1，2，…， n}]，{b1，b2，…，bn}稱為L（B）的基。

定義2（q-元格） 令[q∈Z]，且q為素數(shù)，[A∈Zn×mq]為矩陣，[u∈Znq] ，如下格稱為q-元格：

[ΛqA=y∈Zm ?s∈Znq， ATs=y （mod q）}];

[Λ⊥qA=y∈ZmA?y=0 （mod q）}];

[ΛuqA=y∈ZmA?y=u （mod q）}].

定義3（離散高斯分布） 格Λ是以c為中心，以σ為參數(shù)的離散高斯分布：

[DΛ， σ， （x）=ρσ，c（x）ρσ，c（Λ）=ρσ，c（x）x∈Λρσ，c（x）]

[ρσ，cx=exp （-π|x-c|2σ2）]

定義4（理想格） 令f（x）為不可約多項式，則定義環(huán)[Z[x]]為理想格。

2.2 困難問題

格密碼學(xué)方案的安全性建立在格困難問題上。

定義5（LWE問題） 令q為整數(shù)，[s∈Znq]為向量，[Χ=Χ（n）]為[Zq]上的誤差分布，隨機選擇[a∈Znq]，根據(jù)分布選擇[x←Χ]，并輸出[（a，? +x）∈Znq×Zq]，其分布記為[As，Χ]，帶誤差學(xué)習(xí)（LWE）問題定義為：以不可忽略的優(yōu)勢區(qū)分[As，Χ]和[Znq×Zq]上的隨機均勻分布。

定義6（R-LWE問題） 令[fx=xn+1∈Z[x]]，[d， q∈Z]為整數(shù)，定義[Rq=Zq[x]f（x）]為模f（x）模q的整數(shù)多項式環(huán)，[Χ=Χ（n）]為[Rq]上的誤差分布，均勻隨機選擇Rq上的多項式w，并計算ws+e，其中[s∈Rq]是隨機均勻選取的秘密值，[e←Χ]是根據(jù)誤差分布選取的噪聲值，ws+e的分布記為[Rq，s，Χ]環(huán)上帶誤差學(xué)習(xí)（R-LWE） 問題定義為：以不可忽略的優(yōu)勢區(qū)分[Rq，s，Χ]和[Rq×Rq]上的隨機均勻分布。

2.3 困難假設(shè)

基于R-LWE的密碼學(xué)方案通常都建立在如下的假設(shè)基礎(chǔ)上：不存在多項式時間（甚至允許攻擊者有量子計算能力）的算法解決n維格中的R-LWE問題。

3 基于格的非交互密鑰交換協(xié)議

3.1 CommonSetup算法

設(shè)定R-LWE參數(shù)q， n和誤差分布[Χ]，其中q和n均為正整數(shù)，且n為2的冪，[Rq=Zq[x]f（x）]為模f（x）模q的整數(shù)多項式環(huán)，[Χ=Χ（n）]為[Zq]上的高斯分布;同時均勻選擇[a∈Rq]。

3.2 KeyGen算法

將所有用戶根據(jù)用戶ID按照先后順序排序為U1，U2，…，Un，…，此算法通過如下步驟為用戶Ui生成密鑰：

選擇[si， ei， e'i←Χ]，計算[bi=asi+ei ∈Rq]，對于每個[j>i]，用戶Ui計算

[vij=bjsi+e'i ∈Rq];

[vij=dbl（vij） ∈R2q];

[cij=2q， 2∈{0， 1}n]。

函數(shù)[dbl（?）]：ZqàZ2q定義為 dbl（x）=2x-e，e的值按照Pr（e=0）=0.5，Pr（e=1）= Pr（e=-1）=0.5的概率從{0，1，-1}中抽樣。此處將[dbl（?）]函數(shù)應(yīng)用在多項式的系數(shù)上，每個系數(shù)獨立使用該函數(shù)。

函數(shù)[2q， 2]：Z2qàZ2定義為[2q， 2=2xq mod 2]，此處[2q， 2]函數(shù)應(yīng)用在多項式的系數(shù)上，每個系數(shù)獨立使用該函數(shù)。

以[si， ei， e'i]作為用戶Ui的私鑰，bi 和cij序列Ui作為用戶的公鑰。

3.3 SharedKey算法

假設(shè)用戶Ui和用戶Uj之間要建立共享密鑰，不失一般性，假設(shè)[j>i]。

Ui按照如下規(guī)則進行計算，并以Keyi作為和Uj的共享密鑰：

[vij=bjsi+e'i ∈Rq];

[vij=dblvij∈R2q];

Keyi = [vij2q， 2∈{0， 1}n]。

其中函數(shù)[?2q， 2]：Z2qàZ2定義為[x2q， 2=xq mod 2]，此處[?2q， 2]函數(shù)應(yīng)用在多項式的系數(shù)上，每個系數(shù)獨立使用該函數(shù)。

Uj按照如下規(guī)則計算，并以此作為和Ui之間共享的會話密鑰。

Keyj = [Re（2bisj， cij）∈{0，1}n]。

其中函數(shù)[Re（?， ?）]是這樣定義的，先定義集合[I0={0， 1， …， q2-1}]和[I1={-q2， -q2+1， …， -1}]，令[E=-q4， q4]，則

[Rew，b=0， 如果w∈Ib+E mod 2q1，其他情況]

此處[Re（?， ?）]函數(shù)應(yīng)用在多項式的系數(shù)上，將n比特串[cij]分拆，每個系數(shù)通過[cij]的一個比特獨立使用該函數(shù)。

4 協(xié)議分析

4.1 協(xié)議的正確性

為保證密鑰協(xié)商的正確，要求協(xié)議中Keyi = Keyj。

定理1 上述協(xié)議SharedKey算法中計算的兩個密鑰值相等，即Keyi = Keyj 。

證明 首先考慮單比特的情況，令[b=2∈{0，1}]，則必有[v∈Ib∪（q2+Ib）]，因此[v2=0]當(dāng)且僅當(dāng)[v∈Ib]，令[e∈E]，w=v+e mod q，根據(jù)[Re（?， ?）]函數(shù)的定義，必然有Re（w， 2） = [v 2]。

再推廣到本方案的多比特情況，由于函數(shù)計算是逐系數(shù)進行的，因此每個系數(shù)之間互相不干擾，且每個系數(shù)生成單個密鑰比特，因此必然有[Re2bisj， cij=vij2q， 2]。

（證畢）

4.2 協(xié)議的安全性

協(xié)議的安全性體現(xiàn)在上述攻擊者A和挑戰(zhàn)者C的博弈中。

定理2 在前述博弈中，若攻擊者A取勝的概率和1/2沒有顯著區(qū)別。

證明 要證明本定理，需要證明攻擊者無法區(qū)分依據(jù)協(xié)議生成的密鑰和一個相同長度的隨機值。通過如下一系列博弈變形，對此予以證明。

⑴ 定義博弈1為將測試查詢中用戶Uj的公鑰[bj]設(shè)置為從[Rq]內(nèi)隨即均勻選擇，而不是通過[bj=asj+ej]計算得出。此博弈中，挑戰(zhàn)者C誠實回答攻擊者A的查詢。由于[bj]是R-LWE值，因此根據(jù)R-LWE困難性假設(shè)，A無法區(qū)分是進行博弈1還是在原博弈中運行。

⑵ 定義博弈2是在博弈1的基礎(chǔ)上，進一步令[bi]在[Rq]內(nèi)隨即均勻選擇，而不是通過[bi=asi+ei]計算得出，且[vij]在[Rq]內(nèi)隨即均勻選擇，而不是通過[vij=bjsi+e'i]計算得出。由于[bi]和[vij]均為R-LWE值，因此根據(jù)R-LWE困難性假設(shè)，A無法區(qū)分是進行博弈2還是原博弈1。

綜上所述，A無法區(qū)分是在原博弈中運行還是在博弈2中運行，在博弈2中，由于[bi]和[vij]均為隨機值，因此所得的密鑰也是密鑰空間[{0， 1}n]內(nèi)均勻選取的隨機值。故A無法分辨依據(jù)協(xié)議生成的密鑰和一個相同長度的隨機值。

（證畢）

5 結(jié)束語

目前流行的密鑰交換協(xié)議在一些輕型網(wǎng)絡(luò)節(jié)點中應(yīng)用面臨的最大的問題是交互過于復(fù)雜，這可能會導(dǎo)致大量的通信開銷和電量消耗。同時，隨著量子計算技術(shù)的不斷發(fā)展，未來量子計算機攻破現(xiàn)有協(xié)議安全性的可能性越來越大。因此設(shè)計非交互式的抗量子攻擊密鑰交換協(xié)議是十分必要的。

提出一個基于格理論的非交互密鑰交換協(xié)議，該協(xié)議的安全性基于格理論的帶誤差學(xué)習(xí)困難性問題，在Freire等人提出的形式化定義以及安全模型中得以證明。該協(xié)議具有抗量子攻擊安全性，在網(wǎng)絡(luò)中應(yīng)用能夠有效提升物聯(lián)網(wǎng)的通信安全性。

參考文獻（References）：

[1] Krawczyk H. HMQV： A high-performance secure Diffie-

Hellman protocol[C]//Annual International Cryptology Conference.Springer， Berlin， Heidelberg，2005：546-566

[2] Wagner D， Schneier B. Analysis of the SSL 3.0 protocol

[C]//The Second USENIX Workshop on Electronic Commerce Proceedings，1996.1：29-40

[3] Krawczyk H， Paterson K G， Wee H. On the security of the

TLS protocol： A systematic analysis[M]//Advances in Cryptology-CRYPTO 2013.Springer，Berlin， Heidelberg， 2013：429-448

[4] ?apar， ?.， Goeckel， D.， Paterson， K. G.， Quaglia， E. A.，

Towsley， D.， & Zafer， M. Signal-flow-based 2013. Springer， Berlin， Heidelberg，2013：254-271

[5] 項順伯，徐兵，柯文德.一種貢獻型的動態(tài)群密鑰交換協(xié)議[J].

安徽大學(xué)學(xué)報（自然科學(xué)版），2017.3.

[6] Diffie W.and Hellman M.， New directions in cryptography

[J].IEEE Transactions on Information Theory，1976.22（6）：644-654

[7] Bernstein D J. Cruve 25519： new Diffie-Hellman speed

records [C].//9th International Conference on Theory and Practice in Public Key Cryptography. New York，2006：207-228

[8] Gennaro R， Halevi S， Krawczyk H， et al. Strongly-resilient

and non-interactive hierarchical key-agreement in MANETs[C]. //Computer Security： ESORICS 2008. Springer Berlin Heidelberg，2008：49-65

[9] Guo H， Mu Y， Li Z， et al. An efficient and non-interactive

hierarchical key agreement protocol[J].Computers & Security，2011.30（1）：28-34

[10] Kim H. Non-interactive hierarchical key agreement

protocol over hierarchical wireless sensor networks[C]. In： Computer Applications for Security， Control and System Engineering. Springer Berlin Heidelberg， 2012：86-93

[11] Freire E S V， Hofheinz D， Kiltz E， et al. Non-interactive

key exchange[M]//Public-Key.Cryptography-PKC 2013. Springer， Berlin， Heidelberg，2013：254-271

[12] Lo H K， Spiller T， Popescu S. Introduction to quantum

computation and information[M].World Scientific，1998.

[13] Bernstein D J. Introduction to post-quantum cryptogra-

phy[M]//Post-quantum cryptography.Springer， Berlin， Heidelberg，2009：1-14

[14] Regev O. On lattices， learning with errors， random linear

codes， and cryptography[J]. Journal of the ACM （JACM），2009.56（6）：34

[15] Lyubashevsky V， Peikert C， Regev O. On ideal lattices

and learning with errors over rings[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer， Berlin， Heidelberg，2010：1-23

[16]? Bai S， Galbraith S D. An improved compression

technique for signatures based on learning with errors[C]//Cryptographers' Track at the RSA Conference. Springer， Cham，2014：28-47

[17]? Ding J， Xie X， Lin X. A Simple Provably Secure Key

Exchange Scheme Based on the Learning with ErrorsProblem[J]. IACR Cryptology EPrint Archive，2012：688