A Structured Multi-signature Scheme Against Forgery Attack

Digital signature is one of the important problems of cryptography, it is a simulation of traditional handwritten signatures, and can realize sign electronic news. General digital signature scheme includes three processes: system initialization procedures, signature generating process and signature verification process. Signature algorithm is the cornerstone of digital signature system. Currently there are three kinds effective digital signature algorithm: (1) based on big integer factor decomposition problem; (2) based on discrete logarithm problem (DLP) of finite field, (3) based on elliptic curve discrete logarithm problem (ECDLP).

Digital signature is the important tool which realize network identity authentication, data integrity protection and non-repudiation service basics, also develop e-commerce and sign electronic contract. Using common digital signature, each signer has a respective key to generate signature and validate the signature, there are only a signer participation. let multiple users cooperate to sign one message, in many cases, it is important and necessary, the result that Generation of the multi-signature, the length of signature is irrelevant to the number of signature. In this special digital signature, each signer processes information by using their deposited secret respectively, then synthesis the results of treatment as the entire group signature; when the verifier of signature know the unique public keys of this group, and can validate that the signature is valid. In multi-signature

This material is based upon work supported by the National Natural Science Foundation under Grants NO.60963023 and Chongqing University Posts and Telecommunications Talent Introduction Foundation of China [2009].

* Corresponding author.

scheme, part of the signer's signature means the members sign some messages by using their own deposited secret, and all the signer's part signature is group multi-signature.

According to the different signature process, multi-signature [1] can be divided into orderly multi-signature and broadcasting multi-signature. Orderly multi-signature is a serial signature, it requires the signer according to certain order to sign message, each signer firstly validates the effectiveness of the signature what he received, if effective, it continues to signatures, then send to the next signer; if the signature is invalid, it declines to the signature and terminates the entire signature. And broadcast multi-signature is parallel, all signers can simultaneously sign message and send signature to signature collector, then signature collector collates all signature into a multi-signature. So-called structured multi-signature [2] means signature group has the predetermined signature structure, the structure is orderly or broadcast, also can both union.

Multi-signature was first pointed out in 1983 by Itakura.J K [3]. Burmester pointed out a structured based on ElGamal variant of the sequential multi-signature scheme [4], it makes that the signer can sign structured signature with serial and parallel combination. In 2000, Miyaji and Mitomi pointed out two multi-signature schemes, one was based on the DLP, another was based on RSA problem [5]. In 2003, Kawauehi and Tada pointed out improvement scheme on the basis of literature [5], and demonstrated its safety [6]. In 2004, L.Harn etc put forward respectively based on RSA and two ElGamal of multi-signature algorithm [7].

The rest of this paper is organized as follows: In section 2, I briefly review of Burmester’s scheme. In section 3, the paper put forward a structured multi-signature scheme prevent forgery attack. In section 4 is safety analysis of the new scheme. Finally, I draw our conclusions in Section 5.

• 2.    Briefly Review of Burmester’s Scheme

  • 2.1.    System Initialization

• 2.2.    Signature Process

Put U 1 to the sender, Uv for signature verification, Ui for message signer, supposed (U 1, U 2, ™, Un ) are the signature order. Selecting big primes p , q is p — 1a large prime factor, let g be the primitive-root of the cyclic group GF(p), h () is a one-way hash function. Each signer Ui (i = 1,2,™, n) randomly choose an *

integer as their private keys x G Z . Then compute their public keys as follows: q y1 = gx mod p , yi = (yi—1 g)xi mod p . Opening system parameters (p, q, g, h) , Signers open their public keys, and preserve their private key.

• 1) . Signature Parameters R Generation

• (1)    Signer U 1 randomly selects an integer k 1 G Z q and computes r 1 = g k ¹ mod p , then broadcast r 1 to next signer.

• (2)    For i G ( 2,3, ™ , n ) , U i randomly selects an integer k i G Z q and computes his signature parameters r i = ( r_{i — 1} ) x ' • g k mod p ,then broadcast to next signer.

• (3)    When the last signer U n generates his signature Parameter r n , they compute R = r n .

• 2) . Generation of signature

• (1)  The first signer U 1 computes 5 1 = X 1 + k 1 Rh ( R , M ) mod q , and sends ( 5 1 , M ) to next signer.

• (2)    For i g ( 2,3, — , " ) , the signer U i verifies that g^{5 — 1}?у _{— —} 1 • Rh ( R , M ) mod p , then computes

• 2.3.    Signature Verification

• 3.    A New Structured Multi-Signature Scheme

• 3.1.    System Initialization

S i = ( S i - 1 + 1) X i + kRh ( R , M )mod q and sends ( 5 i , M ) to next signer.

When all the signers have finished signing the message M, the last signer U_n sends ( s_n , M ) to the signature verifier U v , U v verifies g⁵ " ?y n • R R ^{h ( R} ’ M ) mod p . If the equations establish, it is that the signature is valid, else judge invalid and reject the signature.