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

李子臣 張亞澤 張峰娟

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

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

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

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

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

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

0 引 言

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

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

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

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

1 預(yù)備知識

1.1 帶誤差學(xué)習問題LWE

Binary-LWE問題是LWE的一種變種問題，其核心內(nèi)容就是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 單項陷門函數(shù)OWTF

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

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

1.3 DXL12密鑰交換協(xié)議

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

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

(1)

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

(2)

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

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

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

(3)

2 基于Binary-LWE密鑰交換協(xié)議的構(gòu)造

2.1 方案描述

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

2.2 方案設(shè)計

2.2.1 協(xié)議描述

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

圖1 認證密鑰交換方案

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

2.2.2 陷門函數(shù)生成算法和求逆算法

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

算法2InvertO(R,A,b)

輸出：向量s和e

2.3 方案正確性

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

2.4 協(xié)議的安全屬性

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

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

1) 抗中間人攻擊分析

2) 抗冒充攻擊

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

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

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

4) 完美前向安全PFS

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

5) 抗重放攻擊

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

3 協(xié)議的安全性分析

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

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

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

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

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

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

(4)

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

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

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

上述情景模擬器S和敵手M之間的優(yōu)勢關(guān)系為：

(5)

4 結(jié) 語

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

[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。國家自然科學(xué)基金項目(61370188)；北京市支持中央高校共建項目—青年英才計劃；中央高校基本科研業(yè)務(wù)費專項資金資助課題。李子臣，教授，主研領(lǐng)域：公鑰密碼學(xué)，信息安全，后量子簽名理論。張亞澤，碩士生。張峰娟，碩士生。

TP301.4

A

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