一種新型基于Binary-LWE的認證密鑰交換協議

李子臣 張亞澤 張峰娟

1(西安電子科技大學通信工程學院 陜西 西安 710071) 2(北京印刷學院 北京 102600) 3(北京電子科技學院 北京 100070)

一種新型基于Binary-LWE的認證密鑰交換協議

李子臣1,2張亞澤1,3張峰娟1,3

1(西安電子科技大學通信工程學院 陜西 西安 710071)2(北京印刷學院 北京 102600)3(北京電子科技學院 北京 100070)

為了設計一種基于格困難問題的強安全認證密鑰交換協議，分析了DXL12和DXL14方案中缺少認證功能導致容易遭受中間人攻擊等缺陷，提出一種基于Binary-LWE的認證密鑰交換協議。該協議具有兩輪消息交互，不依賴于數字簽名提供隱式密鑰認證，并采用2012年Micciancio和Peikert在歐密會上提出的陷門函數來提供雙方認證功能。在隨機語言機模型下將安全性直接建立在Binary-LWE問題的困難性假設上，具有前向安全性、抗中間人攻擊、抗冒充攻擊等安全屬性。由于該方案的安全性是基于格上困難問題，所以可以抵抗量子攻擊。

格 認證密鑰交換 Binary-LWE 抗量子攻擊

0 引 言

密鑰交換協議KE(Key Exchange Protocol)是密碼學的基本原語，允許通信雙方在不安全的信道上協商出共同的會話密鑰，并借助該會話密鑰及相應的密碼算法進行保密通信，是保證網絡通信安全的重要密碼學組件。Diffie-Hellman(DH)[1]提出了第一個密鑰交換協議，該協議也拉開了公鑰密碼學的序幕。自從DH密鑰交換協議提出以來，由于它構造結構簡單并且實用，不少密碼學者設計了很多基于DH的密鑰交換協議。認證密鑰交換協議AKE(Authenticated Key Exchange)是在密鑰交換的基礎上擁有了通信雙方的認證功能，目前AKE協議已經被廣泛應用于電子商務系統和電子政務系統等安全需求較高的系統中，因此對AKE協議的研究和設計具有很大的理論意義和實用價值。

后量子時代，由于基于大整數分解和離散對數問題的傳統公鑰密碼體制容易受到量子計算機攻擊，因此尋找抗量子攻擊的AKE協議非常具有研究價值。后量子密鑰交換協議已經被美國國家標準和技術研究院(NIST)作為一項重大科研項目。格理論(Lattice)是設計后量子安全公鑰密碼方案的重要理論?；诟窭碚撛O計的密碼方案具有抗量子計算機攻擊、計算效率高、可證明安全等優勢。因此，基于格理論的公鑰密碼方案是后量子時代最具有潛力替代傳統基于數論難題的密碼方案。2005年Regev等提出LWE(Learning With Errors)困難問題，并指出求解平均困難問題LWE的難度可以規約到求解格上最糟糕情況下困難問題[2]。自從Regev提出LWE困難問題以來，由于該困難問題的困難性和良好的代數結構，在密碼方案的構造方面已經得到了廣泛應用。基于格的公鑰加密方案[2-3]、數字簽名方案[4-5]已經得到了很好的發展，格理論也有可能成為設計后量子安全密碼方案的依據。

相比基于格的加密、數字簽名方案，基于格的認證密鑰交換協議LBAKE(Lattice-based AKE)發展起步較晚。目前，設計后量子安全的AKE主要存在兩方面思路：一方面是直接基于錯誤學習問題LWE和小整數解問題SIS(Small Integer Solution)的不同形式來直接構造認證密鑰交換協議。2009年Katz等提出基于LWE假設的基于口令的認證密鑰交換協議[6]，2012年Ding首次提出一種基于LWE變體SLWE的密鑰交換協議[7]，并將該方案擴展到Ring LWE(RLWE)上，不過該方案并沒有給出協議的認證功能。2014年Ding等根據矩陣乘法滿足結合律，使用LWE困難問題構造了密鑰交換協議[8]。2014年Wang等根據SIS的變種問題Bi-ISIS提出基于SIS困難問題的密鑰交換協議[9]。2015年歐密會，Zhang等首次提出基于理想格上認證密鑰交換協議[10]。另一方面是基于密鑰封裝機制KEM(Key Encapsulation Mechanism)和調和機制RM(Reconciliation Mechanism)構造協議，2014年，Peikert利用該技術構造了認證密鑰交換協議[11]。

本文主要在Ding等首次提出的基于LWE的密鑰交換方案DXL12[7]和DXL14[8]的基礎上，改進原方案的缺陷，提出一種新型基于Binary-LWE困難問題的認證密鑰交換方案。

1 預備知識

1.1 帶誤差學習問題LWE

Binary-LWE問題是LWE的一種變種問題，其核心內容就是LWE問題的秘密向量s可以從{0,1}n和{-1,0,1}n中隨機均勻地選取，這就意味著密鑰長度可以縮短。和LWE一樣Binary-LWE也分為Binary-LWE搜索問題和Binary-LWE判定問題，并且如果LWE(n,q,χ)是困難的，則Binary-LWE(nlog(logn),q,χ)也是困難的。

1.2 單項陷門函數OWTF

單項陷門函數是在一個方向容易計算，而反方向計算困難的一種單項函數，在反方向上如果知道函數的秘密陷門，那么反方向上的計算也是容易的。單項陷門函數廣泛應用于密碼學中構造加密方案、簽名方案等，是密碼學中的一個重要工具，在基于格的密碼學中，常見的單項陷門函數主要分為基于LWE問題和基于ISIS問題兩類。

2008年Gentry等在文獻[4]中提出一種陷門函數生成算法，該陷門函數后來被廣泛應用于設計基于格的簽名方案中。2012年歐密會上Micciancio等[12]提出了更簡單、緊致并且快速的輕量級陷門函數。由于該陷門函數可以將特殊格的格基進行隨機化，所以可以在公開加密中使用，在解密操作中需要知道陷門才可以進行反向操作。此外，還提出了在這種陷門函數中的求逆LWE問題以及隨機采樣SIS原像的方法。

1.3 DXL12密鑰交換協議

該協議的主要思想是將錯誤學習困難問題(LWE)應用于構建D-H型密鑰交換協議，利用了雙線性對形式下矩陣乘法的結合性和交換性的數學結構來構造密鑰交換協議。協議方案如下：

首先A和B分別獨立從高斯分布Dzn,αq中選取秘密向量sA和sB。A計算pA=MsA+teAmodq，其中錯誤向量eA選取于高斯分布。然后A將pA發給B。

(1)

最后B計算pB=MTsB+teBmodq，其中錯誤向量eB選自于高斯分布Dzn,αq，并將(pB,Signal)發送給A。

(2)

上述協議中錯誤向量的產生是采用GPV08陷門生成方案中的高斯抽樣算法，并且引用了文獻[13]中的重要結論[13]。文獻[13]中指出對于任意的t∈+，并且滿足gcd(t,q)=1，將傳統的LWE變型為b=〈a,s〉+te的形式后，LWE的困難性假設仍然可以成立。雖然該形式的LWE困難性依然成立，但是直接用于構造密鑰交換協議在一定情況下會存在一定的安全性漏洞。下面是對上述協議的安全性進行分析：

假設在公開信道上存在敵手Eve可以截獲A與B之間發送的消息，首先Eve會得到A發給B的pA，由于pA=MsA+teAmodq，當Eve對pA進行模運算會得到：

pA(modt)=MsA+teA(modt)=MsA(modt)

(3)

2 基于Binary-LWE密鑰交換協議的構造

2.1 方案描述

使用“單位”樣式。方案采用Binary-LWE[14]問題，該問題是LWE問題的變種問題。在Binary-LWE中的密鑰可以從{0,1}n或{-1,0,1}n中選取，這意味著密鑰長度可以縮小。2013年Micciancio等和Brakerski等分別在美密會[14]和STOC上[13]證明了Binary-LWE的問題是困難的，并且還指出需要將原LWE中的參數n增長到logn才能保證困難性。2014年Bai和Galbraith提出即使當維數增加到nlog(logn)，Binary-LWE問題仍然是困難的，而且這增長的維數對于大多數應用的影響可以是忽略不計的。因此，使用基于Binary-LWE困難問題來構造方案是具有可行性的。方案采用2012年歐密會上文獻[12]中提出的陷門函數來實現通信雙方認證功能。

2.2 方案設計

2.2.1 協議描述

本節給出一個基于LWE變種問題Binary-LWE的認證密鑰交換協議，根據文獻[2]、文獻[13]、文獻[14]中給出的格上最壞情況困難問題到LWE、Binary-LWE困難問題的規約結論，基于Binary-LWE困難問題構造認證密鑰交換協議的安全性最終可以規約到格上最壞情況下困難假設難題。本節給出的認證密鑰交換協議的構造，如圖1所示。

圖1 認證密鑰交換方案

2) A計算bA=BsA+eA發送給B。

2.2.2 陷門函數生成算法和求逆算法

本文協議中用到的陷門函數生成算法和求逆算法[12]見算法1、算法2。

算法2InvertO(R,A,b)

輸出：向量s和e

2.3 方案正確性

由上述定理1可知(定理的詳細證明過程見文獻[12])，根據陷門可以成功恢復出相應校驗矩陣A的秘密向量s和噪聲向量e，因此方案正確性得到保障。

2.4 協議的安全屬性

認證密鑰交換協議最基本的安全目標是實現通信雙方的隱式認證的密鑰協商。協議的隱式認證是指參與協議的用戶可以確定其他用戶的身份或者消息是合法的。本方案在達到隱式認證的同時通信雙方還可以進行密鑰確認，即通信雙方可以確認對方已經計算出了與自己進行通信的會話密鑰。因此，本方案達到了顯示認證。

除了上述的安全目標外，本文設計的認證密鑰交換協議還具有如下一些基本的良好安全屬性。

1) 抗中間人攻擊分析

2) 抗冒充攻擊

假設在A和B通信的信道上出現敵手Eve，Eve冒充A與B通信，冒充B與A通信，下面我們證明在此情況下Eve不能與用戶A和B協商出任何A、B之間會話密鑰的信息。

3) 抗未知密鑰共享攻擊UK-S

當通信方A與另一通信方B共同協商生成一個會話密鑰時，由于雙方執行協議交互過程中通過判斷各自秘密信息s來確認對方為通信方。因此通信雙方不會錯誤地認為該會話密鑰是同另外的實體(如Eve)協商出來的，因此可以抵抗位置密鑰共享攻擊。

4) 完美前向安全PFS

當敵手獲得參與者的長期私鑰后，不能根據該私鑰求出私鑰泄露之前通信雙方協商獲得的會話密鑰，并且也不能獲得此次會話的會話密鑰，那么該協議具有完美前向安全。本文協議中，由于通信雙方每次會話密鑰都是由雙方的臨時公私鑰對生成，所以即使敵手獲得當前會話的長期私鑰也不能推斷出之前的會話密鑰。另一方面，由于該協議在通信過程中用單項陷門函數作用于一方的臨時私鑰，即使敵手截獲到參與者發送的消息也不能獲得參與者的私鑰，即不能得到此次會話的會話密鑰。因此，綜上所述，該協議達到了完美前向安全。

5) 抗重放攻擊

所謂重放攻擊就是指攻擊者利用在信道中截獲的會話信息來獲取新的會話的密鑰信息的一種攻擊方式。在本文的協議中，通信雙方每次會話中都要通過陷門函數生成算法生成相應的陷門和公鑰，并在每次會話中選取新的臨時私鑰。由于，每次會話的生成會話密鑰信息不同，所以協議有效地防止了重放攻擊。

3 協議的安全性分析

本節我們在eCK模型下[15]證明該協議的安全性，根據上文困難問題的定義，設攻擊者M解決LWE問題的優勢為AdvLWE(S)。根據文獻[13]中定理4.1可以看出，如果攻擊者M攻擊該協議的優勢是不可忽略的，則攻擊者S解決LWE問題的概率是不可忽略的。下面證明這一點。

證明設M(Mallory)是協議的一個主動攻擊者，M擁有eCK模型中定義的所有查詢能力，設協議的最終Test會話的會話密鑰是SK=H(K,sA,sB)，其中H為隨機預言機。如果攻擊者M能夠在多項式時間內以不可忽略的概率贏得游戲，則M只能通過兩種方式區分真實會話密鑰SK和隨機值。

Case1偽造攻擊。某一時刻，M通過詢問隨機預言機H查詢得到SK。

Case2密鑰復制攻擊。M迫使參與者發起另一個會話，成功構造了一個會話，該會話和Test會話擁有相同的會話密鑰SK。

對于Case2，由于H為隨機預言機，因此發生沖突的概率可以忽略。一旦出現密鑰復制攻擊SK1=H(θ1)=H(θ2)=SK2(θi為生成會話密鑰的參數)，則必然會有θ1=θ2，但是每一次會話都會有不同的θ，因此Case2中的密鑰復制攻擊不會發生，即攻擊者只能進行Case1中的偽造攻擊。下面證明，如果攻擊者M能夠成功地進行偽造攻擊，則可以構造挑戰者S能夠成功地解決LWE問題。

Case1.1Test會話存在匹配會話

(4)

Case1.2Test會話不存在匹配會話

當Test會話不存在匹配會話時，S隨機選取一個參與方IDi記為B，注意S沒有B的長期私鑰sB。S設置誠實用戶的長期私鑰和公鑰，當回答攻擊者的查詢時，只要不涉及到B，S都可以正常輸出，返回給攻擊者。

首先S隨機選取秘密向量s作為B的臨時私鑰，并計算bB=As+e，將SK設置為隨機值。在這種情況下，模型允許S獲取或者計算出B的會話密鑰和臨時私鑰。

上述情景模擬器S和敵手M之間的優勢關系為：

(5)

4 結 語

本文提出了一種新的基于Binary-LWE困難問題的認證密鑰交換，并證明了該協議擁有eCK模型下的安全性質。相對于現有的基于LWE的密鑰交換方案來說，本文的協議是基于Binary-LWE困難問題的，這意味著密鑰長度可以變短，提高協議效率。另一方面，協議采用陷門函數提供通信雙方認證功能，雙方認證后利用一方的臨時私鑰和對方發過來的臨時公鑰來生成會話密鑰。協議的安全性規約到Binary-LWE困難假設，進一步，Binary-LWE問題可以規約到格上最壞情況困難假設，因此該協議抵抗量子攻擊。下一步工作考慮基于環上(Ring)LWE構造強安全的認證密鑰交換方案。

[1] Diffie W,Hellman M.New directions in cryptography[J].IEEE Transactions on Information Theory,1976,22(6):644-654.

[2] Regev O.On lattices,learning with errors,random linear codes,and cryptography[J].Journal of the Acm,2005,56(6):84-93.

[3] Peikert C.Public-key cryptosystems from the worst-case shortest vector problem:extended abstract[C]//ACM Symposium on Theory of Computing.ACM,2009:333-342.

[4] Gentry C,Peikert C,Vaikuntanathan V.Trapdoors for hard lattices and new cryptographic constructions[C]//STOC’08 Proceedings of the fortieth annual ACM symposium on Theory of computing,2008:197-206.

[5] Boyen X.Lattice Mixing and Vanishing Trapdoors:A Framework for Fully Secure Short Signatures and More[M]//Public Key Cryptography-PKC 2010.Springer Berlin Heidelberg,2010:499-517.

[6] Katz J,Vaikuntanathan V.Smooth Projective Hashing and Password Based Authenticated Key Exchange from Lattices[C]//Advances in Cryptology-ASIACRYPT 2009,International Conference on the Theory and Application of Cryptology and Information Security,Tokyo,Japan,December 6-10,2009.Proceedings,2009:636-652.

[7] Ding J T.A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem[EB].Iacr Cryptology Eprint Archive,2012.

[8] Ding J T,Xie X,Lin X D.A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem[EB].Iacr Cryptology Eprint Archive,2014.

[9] Wang S B,Zhu Y,Di M A,et al.Lattice-based key exchange on small integer solution problem[J].Sciece China Information Sciences,2014,57(11):1-12.

[10] Zhang J,Zhang Z,Ding J,et al.Authenticated Key Exchange from Ideal Lattices[M]//Advances in Cryptology EUROCR- YPT 2015.Springer Berlin Heidelberg,2015:719-751.

[11] Peikert C.Lattice Cryptography for the Internet[M]//Post- Quantum Cryptography.Springer international Publishing,2014:197-219.

[12] Micciancio D,Peikert C.Trapdoors for Lattices:Simpler,Ti- ghter,Faster,Smaller[M]//Advances in Cryptology EURO- CRYPT 2012.Springer Berlin Heidelberg,2011:700-718.

[13] Brakerski Z,Langlois A,Peikert C,et al.Classical hardness of learning with errors[C]//ACM Symposium on Theory of Computing.ACM,2013:575-584.

[14] Micciancio D,Peikert C.Hardness of SIS and LWE with Small Parameters[M]//Advances in Cryptology-CRYPTO 2013.Springer Berlin Heidelberg,2013:21-39.

[15] Lamacchia B,Lauter K,Mityagin A.Stronger Security of Authenticated Key Exchange[C]//International Conference on Provable Security.Springer-Verlag,2007:1-16.

ANEWAUTHENTICATEDKEYEXCHANGEPROTOCOLBASEDONBINARY-LWE

Li Zichen1,2Zhang Yaze1,3Zhang Fengjuan1,3

1(SchoolofTelecommunicationsEngineering,XidianUniversity,Xi’an710071,Shaanxi,China)2(BeijingInstituteofGraphicCommunication,Beijing102600,China)3(BeijingElectronicScienceandTechnologyInstitute,Beijing100070,China)

The purpose of this paper is to design a strong secure authenticated key exchange protocol based on lattice problem. Because of the lack of authentication function in DXL12 and DXL14 schemes, it is easy to suffer from man-in-the-middle attacks. Therefore, we propose an authentication key exchange protocol based on Binary-LWE. There is a 2-round message exchange in the protocol that is independent on the implicit authentication from digital signature, and the protocol supply the authentication by the trapdoor function which proposed by Micciancio and Peikert on EUROCRYPT 2012.Under the random oracle model, the security of this protocol is based on the hard assumption on Binary-LWE problem. The protocol can resist man-in-the-middle attack, impersonation attack and also has the forward secrecy. Finally the proposed protocol can resist quantum attacks because of the hard assumption on lattice problem.

Lattice Authenticated key exchange (AKE) Binary-LWE Resist quantum attacks

2016-11-22。國家自然科學基金項目(61370188)；北京市支持中央高校共建項目—青年英才計劃；中央高校基本科研業務費專項資金資助課題。李子臣，教授，主研領域：公鑰密碼學，信息安全，后量子簽名理論。張亞澤，碩士生。張峰娟，碩士生。

TP301.4

A

10.3969/j.issn.1000-386x.2017.11.052