Structural Properties of Cryptographic Sequences - Computational Intelligence in Security for Information Systems - page 140

The verification of each partial signature carried out by each signer (but the
first one) is necessary in order to avoid that a signer signs a non-valid message.
Moreover, the verification of the U i 's partial signature is correct because it is

β g i α a 1 + ··· + a i + m ( c 1 + ··· + c i ) β b 1 + ··· + b i + m ( d 1 + ··· + d i ) F i · (mod n ) ≡

α a 1 + ··· + a i ( α c 1 + ··· + c i ) m β b 1 + ··· + b i ( β d 1 + ··· + d i ) m ≡

i i

β b j α c j β d j m α a j Q m = P i · Q i·m . ≡ · · ≡ P ·

j =1 j =1

2.4 Verifying the Multisignature

Let ( F, g ) be the multisignature for a message M computed by the group of t
signers, G . In order to verify such signature, a verifier must to check if

P t · Q t·m ≡ β g F · (mod n ) . (2)

This verification equation is correct as

β g α a 1 + ··· + a t + m ( c 1 + ··· + c t ) β b 1 + ··· + b t + m ( d 1 + ··· + d t ) F · (mod n ) ≡

t t

β b j α c j β d j m

α a j Q m = P t · Q t·m . ≡ · · ≡ P ·

j =1 j =1

2.5 Properties and Security Analysis

The proposed multisignature scheme has the following properties:

1. The scheme has a fixed size, i.e. , it does not depend on the number of signers.
2. The multisignature is a semi-short signature in the sense that the pair ( F, g )
is composed by two elements belonging to Z n Z r , respectively.

3. The multisignature is ecient as all computations require polynomial time.
4. It is possible to include new signers in the group G without re-execution
of the protocol by the rest of the signers. It is possible to place the new
signers at the end of the signer group so that each one of them follows the
protocol by computing his partial signature from the previously computed
multisignature.
5. The multisignature verification process is easy and ecient.

and to

The proposed multisignature scheme is secure since to break the proposed scheme
an attacker needs to solve three dicult problems: IFP, DLP, and SDLP. Hence,
a signer knowing only his private key cannot determine neither T 's private key

nor its secret value s .
In the scheme it is impossible for two signers to compute a forged signature
because each signer verifies the signatures of all the previous signers.
Moreover, two or more signers could try to conspire with the goal of obtaining
the secret value s of T , and then computing new private keys.