基于RLWE的双因子三方认证密钥交换协议*

申艳梅，李亚平，王 岩，王 辉，黄鹂娟

(河南理工大学计算机科学与技术学院,河南 焦作 454003)

1 引言

密钥交换KE(Key Exchange)协议是通信方在开放的信道上产生共享会话密钥来建立安全的通信信道。认证密钥交换AKE(Authenticated Key Exchange)协议使得通信双方在有主动敌手的信道上建立安全的共享会话密钥，同时实现彼此身份的相互认证，在之后的对称密码中用于保证数据的完整性和真实性。

在后量子时代，随着量子计算机的快速发展，现有的AKE协议在很大程度上是基于传统的数学问题设计的，这些问题在使用量子计算机进行攻击时是不安全的。而基于格理论构造的新型密码体制因具有较好的渐进效率、运算简单、可并行性、抗量子攻击和存在最坏情况下的随机实例等优点，成为密码学中最有前途的后量子选择之一。

2005年，Regev[1]提出了格上的困难性问题误差学习LWE(Learning With Error)，并设计了基于LWE的公钥密码体制，使得构造密码系统时更加安全、方便。2010年，Lyubashevsky[2]提出基于环上误差学习RLWE(Ring Learning With Error)问题的代数结构，并将其多项式时间量子算法的困难性规约为理想格上最坏情形下的困难问题。基于RLWE问题构造的密码体制因其密钥及密文尺寸短、运行效率高等优势，成为学术界设计后量子密钥交换协议的研究热点。而目前已有的基于RLWE的后量子密钥交换协议[3 - 8]大多是无认证的Diffie-Hellman式密钥交换协议，只能提供被动安全，满足用户服务器的认证结构。但是，实际网络中广泛运用的密钥交换协议存在主动攻击，且需要满足端到端的大规模通信，因此在后量子时代设计更高效、更安全的用户-服务器-用户结构的三方口令认证密钥交换协议PAKE(Password Authenticated Key Exchange)迫在眉睫。

2005年，Abdalla等[9]在两方PAKE的基础上，基于经典困难问题构造了三方PAKE协议的通用结构，之后更多的此类协议[10 - 13]被设计出来，然而都不能抵抗量子攻击。2009年，Katz等[14]首次提出了基于LWE假设的公钥密码体制，设计了格上的两方PAKE协议。2013年，叶茂等[15]在文献[14]的两方PAKE框架下，设计了基于LWE的三方PAKE协议，减少了通信轮数，提高了通信效率，实现用户之间的显式双向认证，适用于大规模通信。2018年，于金霞等[16]基于LWE的困难性问题设计了格上的三方PAKE协议，可抵抗消息的重放攻击。基于LWE的协议安全性更加稳定、可靠，但由于存在大矩阵使得协议的计算时间和通信量增大。

2015年，Zhang等[17]排除数字签名，直接基于RLWE的困难性和误差问题的安全性，提出了一种客户-服务器模式的认证密钥交换协议，提供了几个具体的可供选择的参数，并证明了协议的安全性。2017年，Ding等[18]基于RLWE的假设，利用底层环的可加结构，设计了基于格的PAKE协议，实现了相互认证。2018年，王彩芬等[19]为了同时实现用户和服务器的双向认证，设计了2个基于RLWE的匿名三方PAKE协议，实现了通信方的显式认证，具有更高的效率和更短的密钥长度，经研究发现该协议存在会话密钥不一致性问题。

本文基于格上RLWE的困难性问题，利用口令和生物特征信息，通过丁式错误协调机制提出了一种新的三方PAKE协议。主要贡献：(1)使用生物特征和口令实现服务器对客户的显式认证，减少协议的通信轮数，降低通信量，并增强了协议的安全性。(2)设计了三方AKE协议，避免客户-服务器模式的局限性，同时协议可抵抗字典攻击。本文协议的安全性可规约为RLWE的困难性，是一种安全性增强、效率更高的后量子PAKE协议，且适用于端到端的大规模通信系统。

2 基础知识

2.1 环上误差学习

定义1(离散高斯分布) 对任何正整数α∈R和向量c∈Rm，设ρα,c(Zm)=∑x∈Zmρα,c(x)，本文定义离散高斯分布为DZm,α,c(x)=ρα,c(x)/ρα,c(Zm)，这里x∈Zm。

定义2(RLWE分布) 设s∈Rq为秘密，χ是Rq上的错误概率分布，a∈Zq是随机均匀选取的，错误e←χ从错误概率分布χ中采样得到，则RLWE分布为(a,as+emodq)∈Rq×Rq。

定义3(Cha函数) 设奇数q>2，定义Zq={-(q-1)/2,…,(q-1)/2}，取该区间的中间一半定义为E={-|q/4|,…,q/4}，则信号函数Cha可定义为：

则对于任意的v∈Zq，v+Cha(v)·(q-1)/2 modq∈E。

定义4(模函数Mod2)Zq×{0,1}→{0,1},设b=Cha(v)，有Mod2(v,σ)=(v+σ·(q-1)/2) modqmod 2。

引理3对于奇数q，以及v∈Zq,e∈Zq，当|e|

2.2 安全模型

通过对已有的安全模型的学习，本文构造了如下安全模型：

(2)长期密钥：每个用户都有一个从随机口令字典D中选取的口令pwi作为长期密钥，服务器与用户共享口令。

(3)预言机询问：攻击者A可以询问任意多次的预言机查询，预言机查询的描述如下所示：

④PasswordReveal(U,pw)询问：通过该询问攻击者A将获得用户和服务器共享的口令pw。

⑤BiometricReveal(U,B)询问：通过该询问攻击者A将获得用户的生物特征信息BX,其中，X∈{A,B}。

⑥Hash(mes)询问：通过该询问攻击者A可获得哈希值。随机预言机返回散列表中存在的结果，否则返回随机数r给攻击者A，并存储(mes,r)在散列表中。

3 基于RLWE的双因子认证密钥交换协议

3.1 用户注册阶段

本节将要使用到的符号说明如表1所示。

Table 1 Symbol description表1 符号说明

协议执行之前，用户需要在服务器上注册，通过安全信道发送自己的身份信息IDA、IDB、口令pwA、pwB和从生物特征提取器获得的生物信息BA、BB给服务器。当服务器收到信息后，利用模糊提取技术，通过随机字符串生成算法Gen(BA)→(RA,PA),Gen(BB)→(RB,PB)，产生随机字符串RA、RB和公开的辅助随机字符串PA、PB，计算WA=H(RA‖pwA),WB=H(RB‖pwB)，发送PA、PB给用户，并将(IDA,IDB，PA,PB，WA,WB，pwA,pwB)存储在数据库中。

3.2 相互认证及密钥生成

Figure 1 RLWE-based three-party authentication key exchange protocol图1 基于RLWE的三方认证密钥交换协议

协议执行过程：

(1)用户A随机采样sA,eA←χβ,计算α=asA+eA。录入生物信息得RA=Rep(BA,PA),计算WA=H1(RA‖pwA)，ΑuthA=H(pwA)⊕WA，并发送信息[IDA,α,ΑuthA]给用户B。

(2)用户B收到来自用户A的信息后，随机采样sB,eB←χβ,计算β=asB+eB。录入生物信息得RB=Rep(BB,PB),计算WB=H1(RB‖pwB),ΑuthB=H(pwB)⊕WB，并发送信息[IDA,α,ΑuthA,IDB,β,ΑuthB]给可信服务器。

(3)服务器收到来自用户B的消息[IDA,α,ΑuthA,IDB,β,ΑuthB]后，先验证身份信息ΑuthA、ΑuthB，验证不通过，则终止通信。否则采样s′A,e′A;s′B,e′B←χβ，计算α′=as′A+2e′A，β′=as′B+2e′B，k′A=αs′A,k′B=βs′B,，ω′A=Cha(k′A),ω′B=Cha(k′B)，E′A=Mod2(k′A,ω′A),E′B=Mod2(k′B,ω′B),YA=α′+H2(IDA,S,pwA,wA);YB=β′+H2(IDB,S,pwB,wB),Δ=E′A⊕E′B,最后发送消息[YA,YB,ω′A,ω′B,Δ]给用户B。

下面将描述一系列的协议来计算攻击者的优势：

协议P0：最初的协议P。

协议P1：该协议类似协议P，若诚实用户通过通信窃听获取身份认证信息ΑuthA、ΑuthB，执行协议生成会话密钥，则攻击者成功的优势可忽略。

证明攻击者通过监听通信线路窃取ΑuthA、ΑuthB想要模拟用户执行协议获取会话密钥，此时攻击者可以通过身份验证，但服务器端通过生物特征和口令的哈希值传递环元素YA=α′+H2(IDA,S,pwA,wA);YB=β′+H2(IDB,S,pwB,wB)给用户，如果执行Send、Execute和随机预言机询问的概率为(nro+nse+nex)/qn，且nse+nex是确定的，则随机获取YA和YB值的概率为((nse+nex)+(nro+nse+nex))/qn。在攻击者不知道口令和用户生物特征的情况下，不能恢复环元素和模函数Mod2(kA,ωA)、ModB(kB,ωB),故不能获得会话密钥，攻击失败。

□

协议P2：该协议除了不使用随机预言机来询问Send、Execute，其他都和协议P1类似，而对于任何随机预言机的询问，使得攻击者A与Send、Execute询问返回一致的结果。

□

协议P3：该协议对客户端的口令进行正确的猜测攻击，通过询问获得正确的H(pw)，执行协议，若获得正确的会话密钥便终止协议，攻击者攻击成功。显然攻击者不能获得用户的生物特征信息，则无法通过身份验证，攻击成功的概率可以忽略。

证明攻击者通过对H(pw)的询问得到口令哈希值，当进行Αuth=H(pw)⊕WC询问认证用户身份时，则可以区分协议P3和P2，则攻击者获取成功的概率是可忽略的，其中WC是用户的生物特征信息和口令的哈希值。

□

协议P4：该协议获取用户的生物特征信息，通过询问获得正确的WC=H1(RC‖pw)并执行协议，RC是用户的生物特征信息经过模糊提取器后产生的比特值。若获得正确的会话密钥便终止协议，攻击者攻击成功。显然攻击者不能获得用户的口令，则无法通过身份验证，攻击成功的概率可以忽略。

证明攻击者通过询问得到WC=H1(RC‖pw)，当通过Αuth=H(pw)⊕WC认证用户身份时，因无法获取用户的口令散列值，无法通过认证，则可以区分协议P1和P2，则攻击者获取成功的概率是可忽略的。

□

证明攻击者执行协议成功的概率为：

定理1得证。

□

因此,本文所提的三方认证协议是安全的。

4 协议性能分析比较

本文通过分析协议的安全性和效率，在相互认证、通信轮数、通信量、计算复杂度、类型、困难假设、运算方法几个方面，与文献[4,5,16-19]相比较，其分析结果如表2所示。

由表2可知，文献[4]选取维度n=1024的参数,其协议发起方通信量为4 096 B，响应方通信量为4 224 B，和本文协议相比总的通信量几乎不变。文献[5]发起方通信量为1 824 B，响应方通信量为2 048 B，和本文的协议相比总的通信量更加理想。但是，文献[4，5]是经典Diffie-Hellman式密钥交换协议，任何人都可以参加协议的运行，不能抵抗中间人攻击，无法实现相互认证，只提供被动的安全性。而本文协议在不改变通信轮数的前提下，提供主动安全性并且可抵抗中间人攻击，提供通信方的显式相互认证，且实现了客户-服务器-客户模式的大规模通信。文献[16]是基于LWE困难问题的三方口令认证密钥交换协议，协议更加稳定，因LWE的大矩阵运算使得协议计算复杂度高，通信量大，相比而言本文协议通信量和计算开销小，且安全属性更高。文献[17]在BR模型下可证明安全，是理想格上基于RLWE的认证密钥交换协议，该协议既不使用签名方式也不使用密钥封装方式，却实现了通信方的相互认证。但是，协议的通信量和计算复杂度略高于本文协议，且不适用于客户-服务器-客户模式的大规模通信。文献[18]是具有三轮通信消息基于口令的AKE协议，相比而言，本文提出的三方口令认证密钥交换协议在实现通信方相互认证的同时，降低了通信量，可抵抗口令丢失用户假冒攻击。文献[19]是基于RLWE的三方口令AKE协议，尽管适用于大规模通信且可相互认证，其通信轮数为3轮，比本文协议多1轮，通信量几乎不变，但本文协议是基于口令和生物特征的双因子认证密钥交换协议，安全属性更全面，可抵抗口令丢失用户假冒攻击。

5 结束语

针对基于RLWE的Diffie-Hellman式密钥交换协议存在的无认证性、不能抵抗中间人攻击，本文结合生物特征和口令设计认证密钥交换协议，不仅实现了认证性，还增强了协议的安全属性。因两方协议不适用于大规模通信，从通信量和计算复杂度考虑，提出了一个格上基于RLWE的双因子三方认证密钥交换协议，并证明了其安全性。该协议结合丁式错误协调机制，经过2轮通信消息，使得通信双方通过可信服务器提取随机均匀比特的会话密钥。协议将用户口令和生物特征信息作为长期会话密钥，避免单一口令存在的离线字典攻击和抵抗口令丢失引起的用户假冒攻击，加强服务器对客户的显式身份认证，可防止开放信道上的主动攻击。分析表明该协议增强了安全属性，减少了通信轮数，降低了通信量，在后量子密钥交换协议中具有一定的优势。

Table 2 Protocol performance comparison表2 协议性能比较