Digital Multi-Signature Scheme and Its Security Proof

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.