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

In this attack, if the signers U i and U j , j>i , share their signatures ( F i ,g i )
and ( F j ,g j ), they know that the following holds
F i · β g i ≡ β g j F j · (mod n ) ,

β b i C i β md i ≡ β b j C j β md j

A i · · · A j · · · (mod n ) ,

α a i + s·b i + m·c i + s·m·d i ≡ α a j + s·b j + m·c j + s·m·d j (mod n ) .

Then, they can suppose that the exponents verify the following equations:

a i + s · b i + m · c i + s · m · d i ≡ a j + s · b j + m · c j + s · m · d j (mod r ) ,

a i − a j + m ( c i − c j ) ≡ s (( b j − b i )+ m ( d j − d i )) (mod r ) ,

d i )) − 1 (mod r ) .
But, none of them can solve this equation because they do not know a i ,a j ,c i ,c j .
The scheme is secure even if a user has access to the signatures of two distinct
messages signed with the same keys because it implies solving IFP and DLP.
Finally, nobody can determine a forged multisignature for the message M
without being detected by

s ≡ ( a i − a j + m ( c i − c j ))(( b j − b i )+ m ( d j −

. In fact, a forger could know the public key, ( P, Q ),
the message, M ,itshash, m , the number of signers, t , and the values ( α, r, β, n ).
From these data, he can choose an integer g and determine the element β g =
α s·g ∈

T

S r . Moreover, he can compute
F

( β g ) − 1 (mod n )
and publish the pair ( F,g ) as a multisignature of the signer group G for the
message M , that passes the verification equation (2).
Nevertheless,

P t · Q t·m ·

≡

T can prove that this multisignature is a forgery. It is sucient

that it calculates

t

F

C i ≡ A i · (mod n ) ,

i =1

F − 1

and shows that · F ≡ 1(mod n ).

3 Conclusions

A new semi-short multisignature scheme based on three dicult problems from
Number Theory, namely, integer factorization, discrete logarithms, and subgroup
discrete logarithms has been proposed. A multisignature ( F, g )issemi-shortin
the sense that F ∈ Z n ∈ Z r

and g , where the bitlength of n is much bigger than

the the bitlength of r .
This scheme permits one to obtain a semi-short signature with a fixed
bitlength, which is independent of the number of signers.
The multisignature scheme is ecient since the computations only require
polynomial time, verifies the conditions of multisignature schemes, and moreover
it is secure both against conspiracy attacks and against forgery.

Acknowledgment. This work has been partially supported by the “Fundacion
MemoriaD.SamuelSolorzano Barruso” under the Project FS/7-2010.