抗量子本原格上高效的身份基消息恢复签名方案

doi:10.3969/j.issn.1671-1122.2020.01.004

信息网络安全 ›› 2020, Vol. 20 ›› Issue (1): 26-32.doi: 10.3969/j.issn.1671-1122.2020.01.004

抗量子本原格上高效的身份基消息恢复签名方案

张建航^1,²(), 曹泽阳¹, 宋晓峰², 徐庆征²

1. 空军工程大学防空反导学院,西安 710051
2. 国防科技大学信息通信学院,西安 710106

收稿日期:2019-08-26 出版日期:2020-01-10 发布日期:2020-05-11
作者简介:
作者简介：张建航（1979—）,男,陕西,讲师,博士研究生,主要研究方向为格密码与信息网络安全;曹泽阳（1967—）,男,辽宁,教授,博士,主要研究方向为信息安全保障;宋晓峰（1980—）,男,河南,副教授,博士,主要研究方向为信息安全;徐庆征（1980—）,男,山东,讲师,博士,主要研究方向为网络安全。
基金资助:
国家自然科学基金[61872448];陕西省自然科学基金[2018JM6017];国家留学基金[201703170064]

Quantum-resistant Efficient Identity-based Signature Scheme with Message Recovery over Primitive Lattices

ZHANG Jianhang^1,²(), CAO Zeyang¹, SONG Xiaofeng², XU Qingzheng²

1. Air and Missile Defense College, Air Force Engineering University, Xi’an 710051, China
2. Information and Communication College, National University of Defense Technology, Xi’an 710106, China

Received:2019-08-26 Online:2020-01-10 Published:2020-05-11

摘要/Abstract

摘要：

随着量子算法的提出和量子计算机的快速发展,基于传统数论设计的各类数字签名方案受到严重的潜在威胁。基于格理论的身份基消息恢复签名方案是抗量子的网络信息安全认证的重要方法。然而,已有的两个格上身份基消息恢复签名方案的共同缺点是,在私钥提取阶段采用原像抽样算法,导致方案的整体运行效率较低。针对这一问题,文章在私钥提取阶段引入本原格上新的抽样算法,通过特殊的线性变换和矩阵分解简化抽样过程,并通过在身份签名阶段采用无陷门随机抽样技术,提出一个本原格上高效的身份基消息恢复签名方案。在随机预言机模型下,文章证明了方案在小整数解问题困难性条件下满足适应性选择身份和选择消息攻击下的存在性不可伪造性。理论分析表明,在保证安全性的前提下,方案在私钥提取阶段的抽样时间复杂度和抽样空间复杂度明显优于已有的两个格上身份基消息恢复签名方案,方案的整体运行效率更具有优势。

关键词: 数字签名, 消息恢复, 本原格, 原像抽样算法, 抗量子

Abstract:

With the development of quantum algorithms and quantum computers, all kinds of digital signature schemes based on the traditional number theory are seriously threatened. The signature scheme with message recovery using lattice-based theory is an important quantum-resistant method of network information security authentication. However, the two existing identity-based signature schemes with message recovery over lattices have a common drawback that these schemes are inefficient using the preimage sampleable algorithm in the private key extraction phase. To solve this problem, this paper proposes an efficient identity-based signature scheme with message recovery over the primitive lattices. In the new scheme, the private key is extracted by using a new sampling algorithm over the primitive lattices. The scheme describes a specific choice of linear transformations and matrix decompositions that simplifies the sampling process, and uses a random sampling technology without trapdoors in the identity signature stage. The scheme achieves existential unforgeability against adaptive chosen identity and message under the small integer solution assumption in the random oracle model. Compared with the prior two schemes from the lattice assumptions, the scheme has higher efficiency on the time complexity and space complexity of the sampling process in the private key extraction phase. So the scheme has the advantage of the high efficiency in the all running phase.

Key words: digital signature, message recovery, primitive lattices, preimage sampleable algorithm, quantum-resistant

中图分类号:

TP309

张建航, 曹泽阳, 宋晓峰, 徐庆征. 抗量子本原格上高效的身份基消息恢复签名方案[J]. 信息网络安全, 2020, 20(1): 26-32.

ZHANG Jianhang, CAO Zeyang, SONG Xiaofeng, XU Qingzheng. Quantum-resistant Efficient Identity-based Signature Scheme with Message Recovery over Primitive Lattices[J]. Netinfo Security, 2020, 20(1): 26-32.

图/表 1

参考文献 18

[1]	NYBERG K, RUEPPEL R A.A New Signature Scheme Based on DSA Giving Message Recovery[C]//ACM. The 1st ACM Conference on Computer and Communications Security, November 3-5, 1993, Fairfax, Virginia, USA. New York: ACM, 1993: 58-61.
[2]	ABE M, OKAMOTO T.A Signature Scheme with Message Recovery as Secure as Discrete Logarithm[M]//Spring. Advances in Cryptology-Asiacrypt 1999. London: Spring-Verlag, 1999: 378-389.
[3]	ZHANG Fangguo, SUSILO W, MU Yi.Identity-based Partial Message Recovery Signatures(or How to Shorten ID-based Signatures)[M]//Spring. Financial Cryptography and Data Security, Heidelberg: Springer, 2005: 45-56.
[4]	GROVER L K.Quantum Mechanics Helps in Searching for a Needle in a Haystack[J]. Physical Review Letters, 1997, 79(2): 325-328.
[5]	SHOR P W.Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[J]. SIAM Journal on Computing, 1997, 26(5): 1484-1509.
[6]	PEIKERT C.A Decade of Lattice Cryptography[J]. Foundations and Trends in Theoretical Computer Science, 2016, 10(4): 283-424.
[7]	BRAKERSKI Z, GENTRY C, VAIKUNTANATHAN V.Fully Homomorphic Encryption without Bootstrapping[J]. ACM Transactions on Computation Theory(TOCT), 2014, 6(3): 309-325.
[8]	LU Xiuhua, WEN Qiaoyan, WANG Licheng, et al.A Lattice-based Signcryption Scheme Without Trapdoors[J]. Journal of Electronics & Information Technology, 2016, 9(38): 2287-2293.
	路秀华,温巧燕,王励成,等,无陷门格基签密方案[J]. 电子与信息学报,2016,9(38):2287-2293.
[9]	GÉRARD F, MERCKX K. Post-Quantum Signcryption From Lattice-based Signatures[EB/OL]. , 2019-7-23.
[10]	ZHANG Jiang, ZHANG Zhenfeng, DING Jintai, et al.Authenticated Key Exchange from Ideal Lattices[M]// Spring. Advances in Cryptology-Eurocrypt 2015. Heidelberg: Springer, 2015: 719-751.
[11]	TIAN Miaomiao, HUANG Liusheng.Lattice-based Message Recovery Signature Schemes[J]. International Journal of Electronic Security and Digital Forensics, 2013, 5(3-4): 257-269.
[12]	XIE Jia.Research on Digital Signature Schemes of NTRU Lattice[D]. Xi’an: Xidian University, 2016.
	谢佳. 基于NTRU格的数字签名体制的研究[D]. 西安:西安电子科技大学,2016.
[13]	GENTRY C, PEIKERT C, VAIKUNTANATHAN V, Trapdoors for Hard Lattices and New Cryptographic Constructions[C]//ACM. The Fortieth Annual ACM Symposium on Theory of Computing, May 17-20, 2008, Victoria, British Columbia, Canada. New York: ACM, 2008: 197-206.
[14]	MICCIANCIO D, PEIKERT C.Trapdoor for Lattices: Simpler, Tighter, Faster, Smaller[M]//Spring. Advances in Cryptology-Eurocrypt 2012. Heidelberg: Springer, 2012: 708-718.
[15]	GENISE N, MICCIANCIO D.Faster Gaussian Sampling for Trapdoor Lattices with Arbitrary Modulus[M]//Spring. Advances in Cryptology-Eurocrypt 2018. Cham: Springer, 2018: 174-203.
[16]	GENISE N. Building an Efficient Lattice Gadget Toolkit: Subgaussian Sampling and More[EB/OL]. , 2019-7-23.
[17]	LYUBASHEVSKY V.Lattice Signatures without Trapdoors[M]//Spring. Advances in Cryptology-Eurocrypt 2012. Heidelberg: Springe, 2012: 735-755.
[18]	MICCIANCIO D, GEGEV O.Worst-case to Average-case Reductions Based on Gaussian Measures[J]. SIAM Journal on Computing, 2007, 1(37): 267-302.

方案	参数m	抽样时间	抽样空间	主私钥	签名私钥	签名值
文献[11]	$5n\log q$	$O({{n}^{3}})$	$O({{n}^{2}})$	${{m}^{2}}\log O(\sqrt{n\log q})$	$mk\log ({{s}_{1}}\sqrt{m})$	$\begin{matrix} & m\log (12{{\sigma }_{1}})+ \\ & {{l}_{1}}+{{l}_{2}} \\ \end{matrix}$
文献[12]	$5n\log q$	$O({{n}^{3}})$	$O({{n}^{2}})$	$4n\log (s\sqrt{n})$	$2n\log ({{s}_{2}}\sqrt{m})$	$\begin{matrix} & 2n\log (12{{\sigma }_{2}})+ \\ & {{l}_{1}}+{{l}_{2}} \\ \end{matrix}$
本文方案	$n\left\lceil \log q \right\rceil $	$O(n\log q)$	$O(\log q)$	${{n}^{2}}\log (s\sqrt{n})$	$m\log (\sigma \sqrt{m})$	$\begin{matrix} & m\log (12{\sigma }')+ \\ & {{l}_{1}}+{{l}_{2}} \\ \end{matrix}$

抗量子本原格上高效的身份基消息恢复签名方案

Quantum-resistant Efficient Identity-based Signature Scheme with Message Recovery over Primitive Lattices

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 1

参考文献 18

相关文章 15

编辑推荐

Metrics

本文评价

[1]	张雪锋, 彭华. 一种基于SM9算法的盲签名方案研究[J]. 信息网络安全, 2019, 19(8): 61-67.
[2]	赵谱, 崔巍, 郝蓉, 于佳. 一种针对El-Gamal数字签名生成的安全外包计算方案[J]. 信息网络安全, 2019, 19(3): 81-86.
[3]	左黎明, 夏萍萍, 陈祚松. 基于国密SM2数字签名的网络摄像头保护技术[J]. 信息网络安全, 2018, 18(5): 32-40.
[4]	冯达, 王强, 赵译文, 徐剑. 基于SGX的证书可信性验证与软件安全签发系统[J]. 信息网络安全, 2018, 18(3): 63-69.
[5]	赵萌, 丁勇, 王玉珏. 指定审计员的云数据安全存储方案[J]. 信息网络安全, 2018, 18(11): 66-72.
[6]	姜红, 亢保元, 李春青. 改进的保护身份的云共享数据完整性公开审计方案[J]. 信息网络安全, 2018, 18(10): 85-91.
[7]	陈莉, 顾纯祥, 尚明君. 抗量子攻击的高效盲签名方案[J]. 信息网络安全, 2017, 17(10): 36-41.
[8]	张永强, 卢伟龙, 唐春明. 一种高效实用的基于云服务的数字签名方案研究[J]. 信息网络安全, 2016, 16(7): 1-6.
[9]	张言胜, 汪学明, 仇各各. 一种新的动态门限数字签名方案研究[J]. 信息网络安全, 2016, 16(6): 62-67.
[10]	何光蓉, 汪学明. 一种新的基于HECC的Ad Hoc组密钥管理方案[J]. 信息网络安全, 2016, 16(5): 58-63.
[11]	程思嘉, 张昌宏, 潘帅卿. 基于CP-ABE算法的云存储数据访问控制方案设计[J]. 信息网络安全, 2016, 16(2): 1-6.
[12]	朱鹏飞, 李伟, 张利琴, 刘海燕. 自主标准化密码应用体系下带复核的电子签名方案设计[J]. 信息网络安全, 2015, 15(9): 93-96.
[13]	徐剑, 赵英南, 田永纯, 周福才. 融合二维码与人脸识别的会议身份认证系统研究[J]. 信息网络安全, 2015, 15(4): 13-18.
[14]	. 环Zn上广义圆锥曲线多重数字签名方案的分析与改进[J]. , 2014, 14(4): 60-.
[15]	. 基于节点认证的物联网感知层信息安全传输机制的研究[J]. , 2014, 14(2): 53-.