基于RLWE的后量子认证密钥交换协议

李子臣 谢 婷 张卷美 徐荣华

1(北京印刷学院 北京 102600)2(西安电子科技大学通信工程学院 西安 710071)3(北京电子科技学院 北京 100018)(lizc2020@163.com)

密钥交换(key exchange，KE)协议在安全通信领域具有重要的基础性作用，其旨在使得通信双方在不安全的信道上可以协商出共同的会话密钥.Diffile-Hellman密钥交换协议的提出在公钥密码学史上具有里程碑的意义，但此协议为被动安全的密钥交换协议，无法抵御中间人攻击.而认证密钥交换(authenticated key exchange,AKE)协议，不仅使通信双方通过协商得到共享会话密钥，且可为通信双方提供有效认证.AKE协议中，通信双方各自持有一个长期公私钥对与一个临时公私钥对，其中长期公钥由可信赖的第三方颁发，双方通过信息交互与计算最终得到共享会话密钥.

随着量子计算机技术不断取得突破，特别是以Shor算法为典型代表的量子算法的提出，在理论上相关运算操作可实现从指数级别向多项式级别的转变，对于经典计算机来说足够困难的问题必将在可预期的将来被实用型量子计算机轻易破解.2015年8月美国国家安全局宣布当前联邦政府使用的“密码算法B 套件”将升级为抗量子密码系统.2016 年4 月美国国家标准局在全球范围内展开了后量子密码算法的征集工作.近年来欧洲国家的“后量子密码”(PQCrypto)和“安全密码”(SAFEcrypto)项目以及日本的CREST密码数学项目都取得了优秀成果.量子计算的前溯性威胁使部署后量子密码技术需求更加迫切.

格密码具有较好的扩展性，可设计加密、数字签名、密钥交换协议、全同态密码等，被认为是后量子密码算法中最有力的竞争者.在理论研究方面，1996年Ajtai[1]首先基于格上小整数解问题(short integer solution,SIS)构造了抗碰撞杂凑函数；1998年Hoffstein等人[2]基于NTRU密码体制的公钥加密方案，与格上困难问题密切相关.2005年Regev等人[3]基于格理论提出错误学习问题(learning with errors,LWE)，可归约为一般格上最近向量的最坏情形；2010年Lyubashevsky等人[4]提出了基于环上错误的学习问题(ring learning with errors,RLWE)，可归约为理想格上的困难问题SVP(shortest vector problem)的最坏情形；2015年Langlois等人[5]研究了基于模上错误学习性问题(module learning with errors,MLWE)，MLWE问题是理想格与一般格的推广.中国密码学研究者王小云等人[6]、张平原等人[7]、刘亚敏等人[8]对格密码理论方面也进行了较深入的研究.在应用实现方面，美国微软公司于2016年4月发布了格密码库；2016年7月美国谷歌公司在后量子项目试验中，在其浏览器进行了格理论设计的KE协议相关部署测试工作.基于格理论构造密码系统已成为当前后量子密码领域研究的热点.

本文基于格理论RLWE困难问题设计了一种新型AKE协议.首先基于密文压缩技术提出了一个IND-CPA安全的公钥加密算法，在此基础上使用Fujisaki-Okamoto变换技术得到一种IND-CCA安全的密钥封装机制(key encapsulation mechanism，KEM)，最后通过参与者双方分别拥有长期、临时公私钥对的隐式认证方式构造了一种AKE协议.协议在错误分布选取上，采用抽样效率相较于高斯分布更高的二项分布.采用密文压缩方式为基础构造有关方案，与使用计算较复杂的错误协调技术相比，更加简洁高效.本文提出的AKE协议在eCK模型下可证明安全且可达到弱的完美前向安全[16]，是一种更加简洁安全、高效的后量子AKE协议.

1 预备知识

1.1 判定型RLWE，HNF-RLWE问题

判定型RLWE问题是指给定分布(a,v)，区分(a,v)为RLWE分布还是随机均匀分布.

判定型HNF-RLWE问题是指给定分布(a,v)，区分(a,v)为RLWE分布还是随机均匀分布.

1.2 中心二项分布

1.3 密文压缩技术

┌lbq┐.

由定义可得压缩函数和解压函数之间的关系为x′=Decompress(Compressq(x,d),d)，其中x与x′满足|x′-xmod±q|≤Bq=┌q/2d+1」.

2 基于RLWE问题AKE协议方案设计

基于RLWE困难问题设计了一种新型AKE协议.首先基于加密机制以及密文压缩技术提出一种IND-CPA安全的公钥加密方案，在此公钥加密方案的基础上并使用Fujisaki-Okamoto变换技术得到了一种IND-CCA安全的KEM方案，在KEM方案基础上，通过通信双方各持有一对长期、临时私钥的隐式认证方式构造了一个命名为NLPQ(new lattice post quantum)的AKE协议.

2.1 IND -CPA安全的公钥加密方案

算法1～3分别为密钥生成、加密以及解密算法，下面分别对3个算法进行具体说明.

算法1.密钥生成算法：NLPQ.KeyGen.

②a←Parse(SHAKE-128(seed))；

④y=Compress(a·s+e,d)；

⑤pk=(y,seed)，sk=s.

算法2.加密算法：NLPQ.Enc(pk，m),其中pk=(y,seed)，m∈M.

①x′=Decompressq(y,d)；

③a←Parse(SHAKE-128(seed))；

⑤y′=Compressq(a·s′+e′,d)；

⑥y″=Compressq(x·s′+e″+┌q/2┐·m,d)；

⑦ 返回值c=(y′,y″).

算法3.解密算法：NLPQ.Dec，其中sk=s，c=(y′,y″).

①u=Decompressq(y′,d)；

②v=Decompressq(y″,d)；

③ 返回值m′=Compressq(v-u·s,1).

2.2 IND-CCA密钥封装机制

已知杂凑函数G：{0,1}*→{0,1}512，H：{0,1}*→{0,1}256，应用Fujisaki-Okamoto变换，可将IND-CPA安全的公钥加密方案转变为IND-CCA安全的KEM方案[19].本节设计的IND-CCA安全的KEM方案包括NLPQ.KeyGen，NLPQ.Encaps，NLPQ.Decaps三个算法组成，其中NLPQ.KeyGen为2.1节的算法1.算法4，5分别为NLPQ.Encaps和NLPQ.Decaps.

算法4.加密封装算法NLPQ.Encaps，其中pk=(y,seed).

①m←{0,1}256；

② (k,t)=G(pk,m)，k和t的长度均为256 b；

③ (y′,y″)=IND-CPA.Enc((y,seed),m)；

④c′=(y′,y″,t)；

⑤K=H(k,H(c′))；

⑥ 返回值(c′,K).

算法5.算法NLPQ.Decaps，其中sk=s，c=(y′,y″,t)).

①m′=IND-CPA.Dec(s,(y′,y″))；

② (k′,t′)=G(pk,m′)；

③ (z′,z″)=Enc((y,seed),m′)；

④ 如果满足(z′,z″,t′)=(y′,y″,t)条件时，返回值K=H(k′,H(c′))；

⑤ 否则返回值K=H(r,H(c′))，r是一个随机秘密种子.

2.3 密钥交换协议方案

使用算法1～5构造的KE协议方案如图1所示：

AB(pk,sk)←NLPQ.KeyGenv()pk→(c,K)←NLPQ.Encaps(pk)key=NLPQ.Decaps(sk,c)c←key=K

Fig.1 Key exchange protocol图1 密钥交换协议

2.4 认证密钥交换协议

已知通信参与者A和B分别持有长期公私钥(pkA,skA)，(pkB,skB)，临时公私钥(pk1,sk1)，(pk2,sk2).利用通信双方各自持有一对长期、临时公私钥对，构造了一个基于RLWE问题的AKE协议，双方最终得到了共享会话密钥.图2是基于HNF-RLWE问题构造的AKE协议的具体过程.

AB(pkA,skA)←NLPQ.KeyGen()(pkB,skB)←NLPQ.KeyGen()(pk1,sk1)←NLPQ.KeyGen()(pk2,sk2)←NLPQ.KeyGen()(cB,KB)←NLPQ.Encaps(pkB)cB,c2→(cA,KA)←NLPQ.Encaps(pkA)(c2,K2)←NLPQ.Encaps(pk2)(c1,K1)←NLPQ.Encaps(pk1)K'B←NLPQ.Decaps(sk2,cB)K'A←NLPQ.Decaps(skA,c)cA,c1←K'2←NLPQ.Decaps(sk2,c2)K'1←NLPQ.Decaps(sk1,c1)key=H(K'A,KB,K'1,K2)key=H(KA,K'B,K1,K'2)

Fig.2 Authentication key exchange protocol 图2 认证密钥交换协议

3 参数设置与正确性分析

为了满足正确性与安全性需求，参数设置如下：模数q=12 289<214，维度n=1 024，此时NLPQ.IND-CPA公钥加解密方案解密错误的概率δ是可以忽略的，可得解密正确性的概率为1-δ，其中δ<2-128.

Compressq(x·s′+e″+┌q/2」·m,d)代入上式可得

|e·s′+f·s′+e″+f″-e′·s-f′·s|<┌q/4」，此时

记为|v-u·s|=w+┌q/2」·m，向量v-u·s中

的每个元素为wi，可得|wi|<┌q/4」，已知在算法3中有m′=Compressq(v-u·s,1)，计算得到向量为v-u·s-┌q/2」·m′，其中的每个元素为vi，因此可以得到结果┌q/4」>|vi|，之后，向量w+┌q/2」·m-┌q/2」·m′中的每个元素设为mi，进而

得到┌q/4」>|mi|，根据分析已知|wi|<┌q/4」，可

得┌q/2」·(m-m′)|<2×┌q/4」,由已知q是奇数，因此可得m=m′，由此可得NLPQ.IND-CPA公钥加解密方案的正确性.由于杂凑函数G和H是随机预言模型，FO变换技术使得IND-CPA安全的公钥加解密方案转变为IND-CCA安全的KEM方案，因此可得NLPQ.IND-CCA方案的正确性概率为1-δ，其中δ<2-128.因此依据算法1～5构造的KE协议和AKE协议方案，通信参与双方可得到正确的会话密钥.

4 安全性分析及测试

4.1 协议安全性分析

本文构造的协议方案基于随机预言机在标准eCK模型下是可证明安全的，并且由文献[16]相关结论可得可以达到弱的完美前向安全.此AKE协议的安全性最终可归约为格上的HNF-RLWE问题的困难性.

情形1.猜测攻击.攻击者M通过猜测得到通信双方的会话密钥.

情形2.密钥复制攻击.敌手M与参与者建立了与测试会话相同的会话，此时敌手M通过SessionKeyReveal()查询可得到此次会话的会话密钥key，攻击者M得到了测试会话的会话密钥key.

情形3.伪造攻击.攻击者预先计算出会话密钥材料，进而通过H查询得到会话密钥key.

首先分析情形1，由于H为随机预言机，因此通过t次猜测猜到会话密钥的概率只有O(1/2t)，因此通过猜测攻击无法得到真实的会话密钥.

下面分析情形2，协议方案杂凑函数G和H为随机预言机，生成碰撞的概率可以忽略；协议的参与者进行每次新的会话时临时私钥随机产生.因此，会话参与者2次不同的会话中持有相同的临时私钥的概率可忽略.情形2密钥复制攻击无法达到攻击目的.

分析情形3中伪造攻击：若攻击者M可构造一个模拟器S，且模拟器S可利用M以不可忽略的优势解决RLWE问题.

证毕.

本文构造的协议可抵御猜测攻击、密钥复制攻击以及伪造攻击，基于随机预言机在标准eCK模型下是可证明安全的，且可以达到弱的完美前向安全.协议方案的安全性可归约为格理论上的RLWE问题的困难性.

4.2 协议安全性测试

在本协议方案中，设置参数维度n=1 024，模数q=1 073 479 681，选用n=16的中心二项分布错误分布.在2015年Albrecht等人[20]提出的LWE测试器，为当前最权威的针对LWE，RLWE问题的密码系统的安全度测试工具.通过计算暴力搜索、BKW、格基归约、MITM攻击等攻击复杂度来衡量密码系统的安全度.基于LWE，RLWE问题的密码系统的此种LWE测试器，被认为是目前最准确、高效、便捷的安全度测试工具.给定任意有效参数，LWE测试器便可输出各种攻击下的计算复杂度和空间复杂度，目前很多基于LWE和RLWE问题设计的公钥密码方案使用此工具进行方案的安全度测试.

在LWE性能测试平台上对本文设计的基于RLWE问题的协议进行安全性测试，可得协议的安全度为313 b.结果如图3所示：

Fig.3 Security test of the protocol图3 协议的安全性测试

5 效率分析对比

依据目前公开的最新学术成果，基于格上困难问题设计的KE协议与本文设计的方案进行综合分析.选取最典型的无认证KE协议方案BCNS15[11]，NewHope[12]，Frodo[13]方案.另外选取基于RLWE问题构造的HMQV式AKE协议[14]、基于NTRU体制构造的AKE方案[15].分别从模数q、维度n、困难问题假设、公私钥以及密文长度(单位b)、通信复杂度以及协议安全度(单位b)进行对比.表1为本方案与现有的基于格上困难问题设计有关方案性能指标对比情况.本文方案在安全度上有较大优势，与安全度较高的NewHope方案相比，公私钥以及密文尺寸相对较小.协议在较强安全性模型即标准eCK模型下可证明安全，并且可达到弱的完美前向安全.

Table 1 Performance Comparison of Key Exchange Protocols Based on Difficult Problem of Lattice表1 基于格困难问题设计的密钥交换协议的性能比较

6 总 结

本文基于格理论RLWE困难问题，采用计算高效的密文压缩方式设计出一种隐式认证方式的AKE协议.协议在标准eCK模型下可证明安全，并且达到弱的前向安全.与当前的无认证的KE协议以及AKE协议相比，在公私钥及密文长度、通信复杂度与安全度上有很强的竞争力.

量子计算机研制技术的迅速发展，使得现代公钥密码体制的安全性面临着巨大挑战.目前政府、工业界以及相关标准化组织对于实用化的后量子密码系统的需求迫切.2018年4月11—13日，美国国家标准与技术研究院召开了首届后量子时代公钥密码标准化的国际会议，对2017年12月截止的在全球范围内征集的82个密码算法进行首轮评估测试，2019年初宣布共计26个密码算法方案进入了第2轮评估.

未来考虑基于RLWE问题及NTRU密码体制设计出计算简洁高效、安全度更高的KE协议.