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

doi:10.3969/j.issn.1671-1122.2020.01.004

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

CLC Number:

TP309

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.

Figures/Tables 1

References 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}$