一种前向-后向安全的数字签名方案

doi:10.3969/j.issn.1001-2400.2014.02.012

Abstract

Abstract:

A new signature scheme based solely on the MQ-problem is presented, which satisfies the following properties:(1) Forward security, which means that a compromise of a key now does not necessarily expose old traffic. (2) Backward security, which means that a compromise of a key now does not necessarily expose future traffic. We do not have to revoke our public key and re-issue a new key system everytime we detect a key leak. We use two fundamental tools, such as zero knowledge proof and mulitivariate public crypto. Our basic model is Koichi Sakumoto's identifcation scheme which is transformed by parallel processing and Fiat-Shamir transforming. What is novel about our approach is the key updating algortithm, which makes our scheme preserve backward security besides the forward property. Finally, we prove that our scheme satisfies the security under the random oracle model.

Key words: MQ-problem, zero knowledge, identification scheme, forward securrity, backward security, digital signature, random oracle model

CLC Number:

TP309

WANG Mingwei;HU Yupu. Forward and backward secure signature scheme[J].J4, 2014, 41(2): 71-78.

References

［1］ Anderson R. Invited Lecture［C］//Proceedings of Fourth Annual Conference on Computer and Communication Security. New York: ACM Press, 1997: 1-7.
［2］ Bellare M, Miner S K. A Forward-secure Digital Signature Scheme［C］//Advances in Cryptography-CRYPTO'99. Berlin: Springer-Verlag, 1999: 431-448.
［3］ Anderson R. Two Remarks on Public-key Cryptology［R］. UCAM-CL-TR-549. Cambridge: University of Cambridge, 2000.
［4］ Abdalla M, Reyzin L. A New Forward-secure Digital Signature Scheme［C］//6th International Conference on the Theory and Application of Cryptology and Infromation Security. Berlin: Springer-Verlag, 2000: 116-129.
［5］ Back A. Non-interactive Forward Secrecy［Z］. Posting to Cypherpunks Mailing List, 1996.
［6］ Canetti R, Halevi S, Katz J. A Forward-secure Public-key Encryption Scheme［J］. Journal of Cryptology, 2007, 20: 265-294.
［7］ Kozlov A, Reyzin L. Forward-secure Signatures with Fast Key Update［C］//International Conference on Security in Communication Networks. Berlin: Springer-Verlag, 2011: 241-256.
［8］ Krawczyk H. Simple Forward-secure Signatures from Any Signature Scheme［C］//Proceedings of the Seventh ACM Conference on Computer and Communication Security. Piscataway: Association for Computing Machine, 2000.
［9］ Malkin T, Micciancio D, Miner S. Efficient Generic Forward-secure Signatures with an Unbounded Number of Time Periods［C］//Advances in Cryptology-Eurocrypt: 2332. Berlin: Springer-Verlag, 2002: 400-417.
［10］ Lin D T, Wang C I, Guan D J. A Forward-Backward Secure Signature Scheme［J］. Journal of Information Science and Engineering, 2010, 26(6): 2319-2329.
［11］ Sakumoto K, Shirai T, Hivatari H. Sony Corporation:Public-Key Identification Schemes Based on Multivariate Quadratic Polynomials［C］//CRYPTO2011. Heidelberg: Springer-Verlag, 2011: 706-723.
［12］ Garey M, Johnson D. Computers and Intractability, a Guide to the Theory of NP-completeness［M］. New York: Freeman, 1979: 128-130.
［13］ Patarin J, Goubin J. Trapdoor One-way Permutations and Multivariate Polynomials［C］//Proceedings of ICISC 1997. Berlin: Springer Verlag, 1997: 356-368.
［14］ Gene I. Forward Security Adaptive Crytography: Time Evolution［R］. National Science Foundation under Grant No.0311485. Boston: Computer Science Department, Boston University, 2004.
［15］ Hastad J, Impagliazzo R, Levin L. Construction of Pseudo-random Generator from Any One-way Function［J］. SIAM Journal on Computing, 1993, 28(4): 1364-1396.
［16］ Krawczyk H. Simple Forward-secure Signatures from Any Signature Scheme［C］//Seventh ACM Conference on Computer and Communication Security. Piscataway: Association for Computing Machine, 2000: 108-115.
［17］ Bouillaguet C, Chen H C, Cheng C M, et al. Fast Exhaustive Search for Polynomial Systems in F2［C］//International workshop on Cryptographic Hardware and Embeded Systems. Heidelberg: Springer, 2011: 203-218.
［18］ Goldreich O. Foundations of Cryptography: Volume I. Basic Tools［M］. Cambridge: Cambridge University Press, 2001.
［19］ Addalla M, An J H, Bellare M, et al. From Identification to Signatures via the Fiat-Shamir Transform: Necessary and Sufficient Conditions for Security and Forward-Security［J］. IEEE Transactions on Information Theory, 2008, 54(8): 3631-3646.
［20］ Itkis G, Reyzin J. Forward-secure Signatures with Optimal Signing and Verifying［C］//Proceedings of CRYPTO, LNCS 2139. Heidelberg: Springer, 2001: 332-354.
［21］李成, 何明星. 一个前向和后向安全的数字签名方案［J］. 武汉大学学报(理学版), 2008, (5): 557-560.
Li Cheng, He Mingxing. A Forward Secure and Backward Secure Signature Scheme［J］. Journal of Wuhan University(Natural Science Edition), 2008, (5): 557-560.
［22］邱钢, 王宏, 肖鸿, 等. 两个前向安全盲签名体制的安全性分析［J］. 西安电子科技大学学报, 2010, 37(1): 107-112.
Qiu Gang, Wang Hong, Xiao Hong, et al. Security Analysis of Two Forward-secure Blind Signature Schemes［J］. Journal of Xidian University, 2010, 37(1): 107-112.

[1]	ZHANG Yongqiang;LIU Jia'nan;TIAN Haibo. [J]. Journal of Xidian University, 2018, 45(1): 117-122.
[2]	MIAO Yinbin;MA Jianfeng;ZHANG Junwei;LIU Zhiquan. Efficient verifiable multi-keyword search over encrypted data [J]. Journal of Xidian University, 2017, 44(4): 18-23+68.
[3]	FU Zhangjie;SHU Jiangang;SUN Xingming;ZHOU Lu. Secure zero knowledge watermark detection scheme based on the text robust feature [J]. J4, 2015, 42(4): 176-181.
[4]	JIANG Mingming;HU Yupu;WANG Baocang;LIU Zhenhua;LAI Qiqi. Proxy re-signature scheme over the lattice [J]. J4, 2014, 41(2): 20-24.
[5]	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.
[6]	WANG Fenghe;HU Yupu;JIA Yanyan. Lattice-based signature scheme in the standard model [J]. J4, 2012, 39(4): 57-61+119.
[7]	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.
[8]	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.
[9]	MING Yang1;ZHAN Yang2;WANG Yu-min2;PANG Liao-jun2. Improved certificateless signature scheme [J]. J4, 2008, 35(6): 1094-1099.
[10]	DING Yong. Key management scheme for WSN using ECC [J]. J4, 2008, 35(4): 739-742.
[11]	JIA Xiao-yun1;3;LUO Shou-shan2;3;YUAN Chao-wei1. New digital signature scheme based on the discrete logarithm [J]. J4, 2008, 35(2): 351-355.
[12]	LI Yong-jiang1;2;LI Wei3;ZHU Xiao-yan1;GE Jian-hua1. New signature scheme based on the strong RSA assumption [J]. J4, 2007, 34(4): 634-637.
[13]	SI Guang-dong1;LI Yan-ping1;2;XIAO Guo-zhen1. An improvement on group signature [J]. J4, 2007, 34(1): 106-109.
[14]	XIN Xiang-jun1;2;LI Fa-gen3;XIAO Guo-zhen1. A fair exchange protocol based on short signature with the off-line semi-trusted third party [J]. J4, 2007, 34(1): 92-95.
[15]	FU Xiao-tong;ZHANG Ning;XIAO Guo-zhen. Security analysis of Chang et al.'s signature scheme with message recovery [J]. J4, 2005, 32(6): 920-921.

Forward and backward secure signature scheme

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0