一种新型基于环上带误差学习问题的认证密钥交换方案

杨孝鹏 马文平 张成丽



一种新型基于环上带误差学习问题的认证密钥交换方案

杨孝鹏*马文平 张成丽

(西安电子科技大学综合业务网及关键技术国家重点实验室 西安 710071)

利用格上判定带误差学习问题(Ring-DLWE)困难假设，该文基于Peikert的调和技术构造认证密钥交换方案。在标准模型下，该方案是CK模型中可证明安全的，并达到弱前向安全性(wPFS)。与现有的基于LWE的密钥交换方案相比，该方案使用平衡的密钥提取函数，因而保护共享会话密钥，同时因其基于格中困难问题，所以能抵抗量子攻击。

密码学；格；认证密钥交换；CK模型；环上判定带误差学习问题(Ring-DLWE)

1 引言

认证密钥交换是密码学中的基本原型。它不仅允许通信双方协商出共享密钥而且为双方提供认证。每个通信方拥有一对静态公私钥，其中静态公钥由可信第三方颁发。在协议执行过程中，每个通信方首先生成自己的短暂公私钥，再计算会话状态，最后利用密钥提取函数计算共享密钥。

近年来，基于格的密码体制因其具有较高的渐进效率、可并行计算、抗量子攻击等优点，迅速成为密码学研究新热点，并取得了一系列成果。其中，基于带误差学习(Learning With Errors, LWE)问题的困难性在建立秘密共享方案方面应用广泛。文献[6]基于LWE提出了认证密钥交换协议，并证明协议是强安全的。文献[7]指出文献[6]的协议难以抵抗不知道任何秘密信息的外部攻击者实施的假冒攻击。文献[8]提出基于LWE的秘密共享方案。该方案借助符号函数来降噪，但符号函数泄露了密钥的一些信息。文献[9]提出基于LWE的认证密钥交换方案，并构造了特征函数和符号函数。为了使符号函数输出分布与均匀分布不可区分，要求模数很大。针对现有文献的不足，该文基于环上带误差学习问题(RLWE)问题[10]提出新的认证密钥交换方案，使用较小的模数，并利用平衡密钥提取器，所以不会泄露共享密钥的信息，而且所有计算可以采用分圆域上快速傅里叶变换(FFT)[10]加速。

2 预备知识

2.1符号说明

2.2格上亚高斯变量

定义1[10]对于,，若满足，则称上随机变量是标准偏差为的-亚高斯变量。由马尔科夫不等式得：，有

事实1[10]若是-亚高斯变量，标准偏差为,是-亚高斯变量，标准偏差为。与相互独立，则是-亚高斯变量，标准偏差为。

引理1[10]设是-亚高斯变量，标准偏差为。，则对于，用的每个解码基表示时，系数均是-亚高斯变量，标准偏差为。

引理2[10]设，其中,。则是-亚高斯变量，标准偏差为，且以至少的概率成立。

2.3代数整数环上格的抽样

2.4困难问题

定义2[4,10]对于,上的分布，随机均匀选取,是服从的噪声。计算。记的分布为。以不可忽略的概率区分与上的均匀分布问题就是判定Ring-LWE问题，记作。

引理3[4]设，向量，分布与分布统计距离至多为。

2.5 安全模型

安全模型定义请参见文献[13]。

2.6调和技术

调和函数定义请参见文献[11]。

引理4[11]对于偶数模，若是随机均匀的，则是随机均匀的。

引理5[11]对于偶数模，若,,，则。

引理6[11]对于奇数模，若是随机均匀的，，给定条件下，的分布是一致分布。

3 方案

3.1方案描述

图1 基于Ring-LWE的认证密钥交换方案

3.2正确性

3.3参数选取

3.4效率比较

方案效率由计算复杂度和通信复杂度组成。计算复杂度主要考虑向量乘法和抽样。通信复杂度考虑发送比特总数。表1对现有的基于Ring-LWE的密钥交换方案做比较(密钥为bit)。

表1 基于Ring-LWE的密钥交换方案的性能比较(密钥为bit)

表1 基于Ring-LWE的密钥交换方案的性能比较(密钥为bit)

方案认证q的尺寸困难假设安全模型计算复杂度ROM发送比特总数 文献[8]×n4×× 文献[9]√BR√ 本文√CK×

4 安全分析

1,0这个游戏是敌手和协议之间的真实交互。按照模型规定的能力向模拟器发出询问，并得到相应的回答。特别地，当向一个未完成的会话发出询问时，选取。若，则返回一个随机密钥给。否则，返回的真实密钥给。

1,1这个游戏和1,0基本相同，下述情况除外：抽取，计算，选取，计算，选取，计算，依据协议规范地计算，并发送给。

1,2这个游戏和1,1基本相同，下述情况除外：选取，计算，选取，设置，依据协议规范地计算和。

1,3这个游戏和1,2基本相同，下述情况除外：选取,，计算，选取，计算，选取，并设置，发送给。

1,2中替换为1,3中的随机值。设和是两个Ring-LWE挑战组。构造求解Ring-LWE问题的区分器,设置,,，选取，计算，设置，依据协议规范计算。另外，选取，设置，发送给。若是困难问题，则

1,4这个游戏和1,3基本相同，下述情况除外：选取，设置作为共享密钥。在1,4中，是均匀随机的。给定条件下，的输出分布统计接近均匀分布。1,3与1,4计算不可区分，且有

2,0这个游戏与情形1中游戏相同。

2,1这个游戏和2,0基本相同，下述情况除外：抽取，计算，抽取，计算，选取，计算，选取，计算，并发送给。类似分析与的不可区分性，可以得到

2,2这个游戏和2,1基本相同，下述情况除外：用替换中的。类似分析与的不可区分性，可以得到

2,3这个游戏和2,2基本相同，下述情况除外：抽取，计算，选取，计算，依据协议规范地计算。类似分析与的不可区分性，可以得到

2,4这个游戏和2,3基本相同，下述情况除外：抽取，计算，计算，计算，依据协议规范地计算。由引理3可知不能区分2,4与2,3。则有

2,5这个游戏和2,4基本相同，下述情况除外：选取，依据协议规范地计算。因为在随机均匀条件下，的分布是一致分布。由引理5可知猜测成功的优势可忽略，则有

5 结束语

本文利用Ring-DLWE困难假设，基于调和技术构造出一种新型认证密钥交换方案。相对于现有的基于LWE的认证密钥交换方案来说，本文使用较小的模数，并利用平衡函数提取共享密钥。下一步工作可以考虑基于LWE构造强安全的认证密钥交换方案。

参考文献

[1] Gentry C, Peikert C, and Vaikuntanathan V. Trapdoor for hard lattices and new cryptographic constructions[C]. Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, BC , Canada, 2008: 197-206.

[3] Peikert C. Public-key cryptosystems for the worst-case shortest vector problem[C]. Proceedings of the 41th Annual ACM Symposium on Theory of Computing, Bethesda, MD, USA, 2009: 333-342.

[4] Lyubashevsky V, Peikert C, and Regev O. On ideal lattices and learning with errors over rings[C]. Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Riviera, France, 2010: 1-23.

[5] Benny A, David C, and Peikert C. Fast cryptographic primitives and circular-secure encryption based on hard learning problems[C]. Proceedings of the 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, 2009: 595-618.

[6] Fujioka A, Suzuki K, Xagawa K,. Practical and post-quantum authenticated key exchange from one-way secure key encapsulation mechanism[C]. Proceedings of the 8th ACM Symposium on Information, Computer, and Communication Security, Hangzhou, China, 2013: 83-94.

[7] 胡学先, 魏江宏, 叶茂, 等. 对一个强安全的认证密钥交换协议的分析[J]. 电子与信息学报, 2013, 35(9): 2278-2282.

Hu Xue-xian, Wei Jiang-hong, Ye Mao,.. Cryptanalysis of a strongly secure authenticated key exchange protocol[J].&, 2013, 35(9): 2278-2282.

[8] Ding Jin-tai. A simple provably secure key exchange scheme based on the learning with errors problems[OL]. http://eprint.iacr.org/2012/688, 2014, 6.

[9] Zhang Jiang, Zhang Zhen-feng, Ding Jin-tai,Authenticated key exchange from ideal lattices[OL]. http://eprint.iacr.org/2014/589, 2014, 7.

完善的知识产权管理体系对“三农”产业的发展和保护具有重要意义，能够推动企业不断发展升级，从而产生经济效益。通过对知识产权的实际运用，使企业能够充分发挥自身的创新潜力，为企业的健康可持续发展奠定坚实基础。

[10] Lyubashevsky V, Peikert C, and Regev O. A toolkit for ring-LWE cryptography[C]. Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, 2013: 35-54.

[11] Peikert C. Lattice cryptography for the Internet[C]. Proceedings of the 6th International Workshop, Post-Quantum Cryptography, Waterloo, Canada, 2014: 197-219.

[12] Peikert C. An efficient and parallel gaussian sampler for lattices[C]. Proceedings of the 30th Annual International Cryptology Conference, Santa Barbara, CA, USA, 2010: 80-97.

[13] Canetti R and Krawczyk H. Analysis of key-exchange protocols and their use for building secure channels[C]. Proceedings of the 20th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Innsbruck, Austria, 2001: 453-474.

New Authenticated Key Exchange Scheme Based on Ring Learning with Errors Problem

Yang Xiao-peng Ma Wen-ping Zhang Cheng-li

(,710071,)

Using the hard assumption of Ring-Decision Learning With Errors (Ring-DLWE) in the lattice, a new Authenticated Key Exchange (AKE) scheme is proposed, which is based on the Peikert’s reconciliation technique. Under the standard model, the proposed scheme is provably secure in the CK model, which is additionally achieves weak Perfect Forward Secrecy (wPFS). Compared with the current Key Exchange (KE) schemes based on the LWE, the proposed scheme not only protects the shared session key with balanced key derivation function but also resists quantum attacks because of the hard assumption on lattice problem.

Cryptography; Lattice; Authenticated Key Exchange (AKE); CK model; Ring-Decision Learning With Errors (Ring-DLWE)

TP309

A

1009-5896(2015)08-1984-05

10.11999/JEIT141506

杨孝鹏 xp_yang89xidian@126.com

2014-11-27收到，2015-02-19改回，2015-06-08网络优先出版

国家自然科学基金(61072140, 61373171)，高等学校博士学科点专项科研基金(20100203110003)，高等学校创新引智计划项目(B08038)，“十二五”国家密码发展基金(MMJJ201401003)和华为技术有限公司合作项目(YB2013120005)资助课题

杨孝鹏： 男，1986年生，博士生，研究方向为格密码.

马文平： 男，1965年生，博士，教授，博士生导师，研究方向为通信理论、纠错码和信息安全等.

张成丽： 女，1985年生，博士生，研究方向为格密码.