标准模型下的格基数字签名方案

doi:10.3969/j.issn.1001-2400.2012.04.011

Abstract

Abstract:

To improve the efficiency of the Bonsai trees signature which was proposed in Eurocrypt'10, utilizing the Bonsai trees algorithm, a new lattice-based signature scheme is proposed. Based on the hardness of the short integer solution problem (SIS), the proposed scheme is provably existentially unforgeable under a static chosen-massage attack in the standard model. Moreover, the public-key length of our proposed signature is (k+1)mn log q bit while the bonsai trees signature's is (2k+1)mn log q bit; the signature length of message is (1+k/2)m log q bit while the Bonsai trees signature scheme's is (k+1)m log q bit. So the proposed signature scheme is more efficient than the Bonsai trees signature.

Key words: digital signature, lattice, bonsai trees, short integer solution problem, the standard model

CLC Number:

TP309

WANG Fenghe;HU Yupu;JIA Yanyan. Lattice-based signature scheme in the standard model[J].J4, 2012, 39(4): 57-61+119.

References

［1］ Shor P W. Polynomial-time Algorithm for Prime Factorizeation and Discrete Logarithm on a Quantum Computer ［J］. SIAM Journal on Computing, 1997, 26(5): 1484-1509.
［2］ Lyubashevsky V, Micciancio D. Asymptotically Efficient Lattice-Based Digital Signature［C］//Proc of TCC2008: LNCS 4948. Berlin: Springer, 2008: 37-54.
［3］ Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for Hard Lattices and New Cryptographic Constructions［C］//Proc of STOC'2008: ACM. Victoria: STOC, 2008: 197-206.
［4］ Cash D, Hofheinz D, Kiltz E, et al. Bonsai Trees, or How to Delegate a Lattice Basis［C］//Proc of Eurocrypt 2010: LNCS 6110. Berlin: Springer, 2010: 523-552.
［5］ Rückert M. Strongly Ungorgeable Signatures and Hierarchical Identity-based Signatures from Lattices without Random Oracles［C］//Proc of Post-Quantum Cryptography 2010: LNCS 6061. Darmstadt: Springer, 2010: 182-200.
［6］ Gordon S D, Katz J, Vaikuntanathan V. A Group Signature Scheme from Lattice Assumptions［C］//Proc of ASIACRYPT 2010: LNCS 6477. Berlin: Springer, 2010: 395-412.
［7］ Rückert M. Lattice-based Blind Signatures ［C］//Proc of Asiacrypt'10: LNCS 6477. Berlin: Springer, 2010: 413-430.
［8］ Boyen X. Lattice Mixing and Vanishing Trapdoors: a Framework for Fully Secure Short Signatures and More［C］// Proc of PKC 2010: LNCS 6056. Berlin: Springer, 2010: 499-517.
［9］ Agrawal S, Boneh D, Boyen X. Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE［C］//Proc of CRYPTO'10: LNCS 6223. Berlin: Springer, 2010: 98-115.
［10］ Alwen J, Peikert C. Generating Shorter Bases for Hard Random Lattices［C］//Proc of STACS: 09001. Freiburg: Springer, 2009: 75-86.
［11］ Micciancio D, Regev O. Worst-case to Average-case Reductions Based on Gaussian Measures ［J］. SIAM J Comput, 2007, 37(1): 267-302.
［12］张乐友, 胡予濮, 刘振华. 标准模型下基于身份的可证安全门限签名方案［J］. 西安电子科技大学学报, 2008, 35(1): 81-86.
Zhang Leyou, Hu Yupu, Liu Zhenhua. Provable Secure ID-based Threshold Signature Scheme without Random Oracles ［J］. Journal of Xidian University, 2008, 35(1): 81-86.

[1]	YAN Xixi;LIU Yuan;LI Zichen;TANG Yongli;YE Qing. Multi-authority attribute-based encryption scheme from LWE problem [J]. Journal of Xidian University, 2018, 45(4): 129-136.
[2]	ZHANG Yongqiang;LIU Jia'nan;TIAN Haibo. [J]. Journal of Xidian University, 2018, 45(1): 117-122.
[3]	WANG Wei;LI Yongzhao;ZHANG Hailin. Low complexity lattice reduction aided precoding algorithm with orthogonality defect threshold for MIMO systems [J]. J4, 2015, 42(5): 1-6+32.
[4]	LIU Jiajia;LEI Tianmin;ZHANG Yuming;CHEN Delin;GUO Hui;ZHANG Zhiyong. Effect ofthe manganese doping concentration and site on the magnetism of graphene [J]. J4, 2015, 42(4): 76-80+106.
[5]	WANG Mingwei;HU Yupu. Forward and backward secure signature scheme [J]. J4, 2014, 41(2): 71-78.
[6]	JIANG Mingming;HU Yupu;WANG Baocang;LIU Zhenhua;LAI Qiqi. Proxy re-signature scheme over the lattice [J]. J4, 2014, 41(2): 20-24.
[7]	XU Weitao;ZHANG Wenqiang;XU Yang;ZHANG Dexian. α-generalized resolution principle based on the lattice-valued first-order logic system [J]. J4, 2014, 41(1): 135-139.
[8]	ZHENG Xiang;TONG Ming;CAO Yang. LBM craniocerebral MR 3D medical image non-rigid registration method [J]. J4, 2013, 40(6): 125-131.
[9]	TONG Ming;CAO Yang;HE Mengyue;ZHANG Jianlong. Non-rigid registration method of the medical image based on the LBM [J]. J4, 2013, 40(1): 6-13.
[10]	LIU Dongsu;MIAO Meixia;MA Hua;LIN Ruibin;TIAN Haibo. Digital anti-counterfeiting scheme based on key-exposure free chameleon signature [J]. J4, 2012, 39(5): 24-29.
[11]	LI Jiandong;CHEN Rui;LI Changle;LIU Wei;CHEN Dan. Lattice-reduction-aided detection in spatial correlated MIMO channels [J]. J4, 2012, 39(1): 11-16+22.
[12]	XIAO Hong;WANG Hong;MA Runnian;CUI Jie. Provably secure threshold FFS signature scheme in the random oracle model [J]. J4, 2011, 38(6): 130-133+151.
[13]	ZHANG Yinghui；LI Hui；MA Hua. Free protocol for the subliminal channels in the Schnorr-type ordinal multi-signature schemes [J]. J4, 2011, 38(3): 140-144.
[14]	GAO Shan;BI Du-yan. Mathematical comprehension of the intersecting cortical model using the lattice theory [J]. J4, 2009, 36(6): 1120-1125.
[15]	DING Yong. Key management scheme for WSN using ECC [J]. J4, 2008, 35(4): 739-742.

Lattice-based signature scheme in the standard model

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 10