无陷门格基签密方案

路秀华 温巧燕 王励成 杜 蛟



无陷门格基签密方案

路秀华*①②温巧燕②王励成③杜 蛟④

①(廊坊师范学院数学与信息科学学院 廊坊 065000)②(北京邮电大学网络与交换技术国家重点实验室 北京 100876)③(北京邮电大学信息安全中心 北京 100876)④(河南师范大学数学与信息科学学院 新乡 453007)

现有的格基签密方案以陷门产生算法和原像取样算法为核心算法。但是，这两个算法都很复杂，运算量较大，严重影响格基签密方案的执行效率。该文运用无陷门格基签名及其签名压缩技术，结合基于带错学习问题的加密方法，提出第1个基于格理论的、不依赖于陷门产生算法和原像取样算法的签密方案。方案在带错学习问题和小整数解问题的难解性假设下，达到了自适应选择密文攻击下的不可区分性和自适应选择消息攻击下的不可伪造性。方案在抗量子攻击的同时，保证了较高的执行效率。

基于格的密码学；签密；无陷门格基签名；带错学习问题；小整数解问题

1 引言

签密是由文献[1]提出的基本密码学原语，可以同时实现信息的机密性和认证性，为信息的安全传输，提供最基本的安全保障。在大整数因子分解问题和离散对数问题等传统数论问题的难解性假设下，已有大量的签密方案被提出。但是伴随着文献[5]提出分解大整数和解决离散对数问题的量子多项式时间算法，以及量子计算机这些年来的飞速发展，我们不得不去探寻能够抵抗量子算法攻击的密码体制。

基于格的密码学是新兴的抗量子密码，由于其独特的理论优势，近二十年来发展迅速。格基密码目前可以实现绝大部分的密码学功能，比如认证密钥交换方案[6]，可撤销的加密方案[7]等。至于签密方案，格上的实现已有文献[8-11]，这些方案都以格中的陷门产生算法和原像取样算法为基础，算法的计算复杂度较大。文献[12]在2012年提出了格中无陷门签名方案的构造方法，文献[13]在2014年对其进行了改进，缩短了签名的长度。本文在文献[13]的基础上，构建了一个不需要陷门产生算法和原像取样算法的格基签密方案，并以带错学习问题和小整数解问题的难解性假设为基础，结合文献[14]的转化方法，证明了方案的自适应选择密文攻击下的不可区分性和自适应选择消息攻击下的不可伪造性。最后，给出了方案的效率分析，验证了所构造方案的高效性。

2 签密的形式化定义

一个签密方案由3个算法组成：密钥生成算法，签密算法，解签密算法。

3 签密的安全模型

一个签密方案必须同时实现信息的机密性和认证性，因此方案的安全性包含两个方面：(1)自适应选择密文攻击下的不可区分性(INDistinguishability against adaptive Chosen Ciphertext Attacks, IND- CCA2); (2)自适应选择消息攻击下的不可伪造性(Existential UnForgeability against adaptive Chosen Message Attacks, EUF-CMA)。

3.1 IND-CCA2安全性

签密方案的IND-CCA2安全性由下面的游戏来描述，游戏由挑战者和敌手交互完成。

定义1 一个签密方案是IND-CCA2安全的，如果每个多项式有界的敌手在上述游戏中的优势都是可忽略的。特别地，如果在上述游戏中不允许敌手进行解签密查询，则签密方案具有选择明文攻击下的不可区分性(INDistinguishability against Chosen Plaintext Attacks, IND-CPA)。

3.2 EUF-CMA安全性

定义2 签密方案是EUF-CMA安全的，如果每个多项式有界的敌手在上述游戏中的优势都是可忽略的。

4 无陷门格基签密方案1

(1) 系统设置：

(2)密钥生成算法：

4.1方案1的正确性

4.2方案1的IND-CPA安全性

定理1 方案1 以LWE问题的难解性为基础，达到了IND-CPA安全性。

证明 我们给出一个游戏序列。

G0是IND-CPA安全性定义中的游戏。

G1在G0的基础上，将挑战者生成的挑战密文中的改为对称加密算法密文空间中一个均匀随机选取的。

G2在G1的基础上，将挑战者生成的挑战密文中的改为中的随机值。

G3在G2的基础上，将挑战者生成的挑战密文中的改为中的随机值。

在G3的挑战密文中，,,都是各自取值空间中的随机值，此时挑战密文中已经不再含有关于明文的任何信息，因此敌手猜对的优势为零。

由G3和G0的计算不可区分性，在G0中，敌手猜对的优势是可以忽略的，所以方案1是IND- CPA安全的。

证毕

5 无陷门格基签密方案2

为了使无陷门格基签密方案达到IND-CCA2安全性，我们采用文献[14]的转化方法，在方案1的基础上构建了无陷门格基签密方案2。由方案1的IND-CPA安全性和文献[14]的结论，方案2是IND- CCA2安全的。方案2描述如下：

(1)系统设置

(2)密钥生成算法：

5.1 方案2的正确性

5.2方案2的IND-CCA2安全性

定理2 方案2以判定性LWE问题的难解性为基础，达到了IND-CCA2安全性。

(1)服从均匀分布。

证毕

5.3方案2的EUF-CMA安全性

定理3 方案2以SIS问题的难解性为基础，达到了EUF-CMA安全性。

证毕

5.4方案2的效率分析

表1与文献[10]的效率对比

6 结束语

陷门产生算法和原像取样算法的计算复杂度是影响格基密码实用性的重要因素。本文提出的格基签密方案，使用了无陷门签名技术和基于LWE问题的加密方法，避免了陷门产生算法和原像取样算法的使用，提高了方案的运算效率，高效地保证了量子计算机环境下信息传输的机密性和认证性。在本文方案的基础上研究代理签密，多接收者签密，聚合签密等具有特殊应用需求的高效签密方案的设计，将是下一步的研究内容。

[1] ZHENG Y. Digital signcryption or how to achieve cost (signature+encryption)<

[2] MALONE-LEE J and MAO W. Two birds one stone: signcryption using rsa[C]. Proceedings of the 2003 RSA conference on The Cryptographers’ track, San Francisco, USA, 2003: 211-226.

[3] LI Fagen and TAKAGI T. Secure identity-based signcryption in the standard model[J]., 2013, 57(11/12): 2685-2694.

[4] LU Y and LI J. Efficient certificate-based signcryption secure against public key replacement attacks and insider attacks[J]., 2014, Article ID 295419.

[5] Shor P. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]., 1997, 26(5): 1484-1509.

[6] 杨孝鹏, 马文平, 张成丽. 一种新型基于环上带误差学习问题的认证密钥交换方案[J]. 电子与信息学报, 2015, 37(8): 1984-1988.

YANG Xiaopeng, MA Wenping, and ZHANG Chengli. New authenticated key exchange scheme based on ring learning with errors problem[J].&, 2015, 37(8): 1984-1988.

[7] 张彦华, 胡予濮, 江明明, 等. 格上可撤销的基于身份的适应性安全的加密方案[J]. 电子与信息学报, 2015, 37(2): 423-428.

ZHANG Yanhua, HU Yupu, JIANG Mingming,. A lattice-based revocable adaptive-id secure encryption scheme [J].&, 2015, 37(2): 423-428.

[8] WANG Fenghe, HU Yupu, and WANG Chunxiao. Post- quantum secure hybrid signcryption from lattice assumption[J].&, 2012, 6(1): 23-28.

[9] LI Fagen, BIN MUHAVA F T, KHAN M K,. Lattice-based signcryption[J]., 2013, 25(14): 2112-2122.

[10] YAN Jianhua, WANG Licheng, YANG Yixian,. Efficient lattice-based signcryption in standard model[J]., 2013, Article ID 702539.

[11] LU Xiuhua, WEN Qiaoyan, JIN Zhengping,. A lattice- based signcryption scheme without random oracles[J]., 2014, 8(4): 667-675.

[12] LYUBASHEVSKY V. Lattice signatures without trapdoors [C]. EUROCRYPT 2012, Cambridge, USA, 2012: 738-755.

[13] BAI Shi and GALBRAITH S D. An improved compression technique for signatures based on learning with errors[C]. CT-RSA 2014, San Francisco, USA, 2014: 28-47.

[14] FUJISAKI E and OKAMOTO T. Secure integration of asymmetric and symmetric encryption schemes[J]., 2013, 26(1): 80-101.

[15] BELLARE M and NEVEN G. Multi-signatures in the plain public-key model and a general forking lemma[C]. Proceedings of the 13th ACM Conference on Computer and Communications Security, Alexandria, USA, 2006: 390-399.

A Lattice-based Signcryption Scheme Without Trapdoors

LU Xiuhua①②WEN Qiaoyan②WANG Licheng③DU Jiao④

①(Faculty of Mathematics and Information Science, Langfang Teachers University, Langfang 065000, China)②(State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China)③(Information Security Center, Beijing University of Posts and Telecommunications, Beijing 100876, China)④(College of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, China)

The existing lattice-based signcryption schemes are based on trapdoor generation algorithm and preimage sample algorithm. However, both algorithms are complex, require a lot of time to run, and affect the efficiency of latticed-based signcryption schemes deeply. To solve this problem, the first lattice-based signcryption scheme without trapdoor generation algorithm and preimage sample algorithm is proposed, with the help of the technique of lattice signatures without trapdoors and the associated signature compression technique, as well as the encryption method based on the learning with errors assumption. The scheme achieves indistinguishability against adaptive chosen ciphertext attacks under the learning with errors assumption. It also achieves existential unforgeability against adaptive chosen message attacks under the small integer solution assumption. The proposed scheme is not only quantum resistant, but also efficient.

Lattice-based cryptography; Signcryption; Lattice signatures without trapdoors; Learning with errors problem; Small integer solution problem

TP309

A

1009-5896(2016)09-2287-07

10.11999/JEIT151044

2015-09-14；

2016-06-27；

2016-08-09

国家自然科学基金(61300181, 61502044, 61402015, U1404601, 11471104)，中央高校基本科研业务费专项资金 (2015RC23)，河北省教育厅青年基金(QN2015084)，廊坊市科技局项目(2015011063)，廊坊师范学院博士基金(LSLB201408)

The National Natural Science Foundation of China (61300181, 61502044, 61402015, U1404601, 11471104), The Fundamental Research Funds for the Central Universities (2015RC23), Hebei Province Education Funds for Youth Project (QN2015084), Langfang Municipal Science and Technology Support Program (2015011063), Langfang Teachers University Doctor Funds (LSLB201408)

路秀华 luxiuhua2014@sina.cn

路秀华： 女，1979年生，副教授，博士生，研究方向为基于格的公钥密码学.

温巧燕： 女，1959年生，教授，研究方向为密码学和信息安全.

王励成： 男，1971年生，副教授，研究方向为密码学和网络安全.

杜 蛟： 男，1978年生，讲师，博士，研究方向为密码学与应用数学.