Chinese Journal of Computers   Full Text
Title	Digital Multi-Signature Scheme and Its Security Proof
Authors	WANG Xiao-Feng1),2) ZHANG Jing1) WANG Shang-Ping1),2)
Address	1)(School of Computer Science and Engineering, Xi′an University of Technology, Xi′an 710048) 2)(School of Science, Xi′an University of Technology, Xi′an 710054)
Year	2008
Issue	No.1(176—183)
Abstract &   Background	Abstract A new sequential digital multi-signature scheme and a new broadcasting digital multi-signature scheme are proposed based on the difficulty assumption of factoring and quadratic residues. The advantages of the proposed schemes are as follows: the multi-signature is a co-signature which is generated by multiple signers in collaborative and simultaneous manner, in which, per signer generates partly signature, rather than accumulating per signer′s single signature. The length of the partly signatures does not grow with the number of the signers. The computation complicacy of the partly signature algorithm and the verification algorithm is independent of the signer′s number. The signing sequence of the proposed sequential digital multi-signature scheme is fixed and unable to be changed freely by the signers. Proposed schemes have lower computation complicacy and more efficient, and are secure against existent attacks for multi-signature schemes. Their securities are proved under the difficulty assumption of factoring and quadratic residues in the random oracle model. keywords quadratic residues；sequential digital multi-signature；broadcasting digital multi-signature；security proof background This paper focuses on the field of the digital multi-signature. A digital multi-signature scheme is a digital signature scheme that allows multiple signers to generate a single signature in collaborative and simultaneous manner. In some applications, co-signers in a signing group may associate with different roles/positions and therefore have different management liabilities and authorization capabilities. Thus, multi-signatures generated by the same group of co-signers with different signing orders often imply different meanings. Hence, we can say that a digital multi-signature scheme is quite useful in E-Commerce and E-Government. In the past few years, there are many digital multi-signature schemes have been proposed, and each scheme has its own special features. However, most of the existing schemes are based on the discrete logarithms difficulty assumption or Gap Diffie-Hellman Group, which are complex in computation. In this paper, the authors propose a new sequential digital multi-signature scheme and a new broadcasting digital multi-signature scheme based on the difficulty assumption of factoring and Quadratic Residues. Proposed schemes have lower computation complicacy and more efficient. They prove its security under the factoring and quadratic residues problem assumption in the random oracle model. This research work is supported by the Natural Science Basic Research Plain in Shaanxi Province of China (2005F02), the Science and Technology Innovation Foundation in Xi′an University of Technology (108210402), the Foundation in Education Department of Shaanxi Province of China(06JK211).