李子臣 张亚泽 张峰娟

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)是设计后量子安全公钥密码方案的重要理论。基于格理论设计的密码方案具有抗量子计算机攻击、计算效率高、可证明安全等优势。因此，基于格理论的公钥密码方案是后量子时代最具有潜力替代传统基于数论难题的密码方案。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