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

2.3 Signing a Message
We will present a protocol to determine a multisignature of the group G for a
given message M , where only the signers participate.
We suppose a secure hash function,

h , has been selected (for example, one

of the SHA-2 family) with ( M )= m . Moreover, it is assumed that the set of

signers has been ordered, due to the fact that each signer will sign the signature
determined by the previous signer.
The process is as follows: Each signer verifies the partial signature determined
by the previous signer, computes his own signature by using the received signa-
ture, and sends the new partial signature to the next signer.

h

1. The first signer, U 1 , computes his partial signature for the message M by
using his private key, ( b 1 ,d 1 ,A 1 ,C 1 ), and m = h ( M ):

C 1 F 1 ≡ A 1 · (mod n ) ,

g 1 ≡ b 1 + m · d 1 (mod r )

and sends ( F 1 ,g 1 ) to the second signer, U 2 .
2. The second signer, U 2 , verifies U 1 's signature checking if
P Q m ≡ β g 1 · F 1 · (mod n ) .

U 2 computes his partial signature for the message:
F 2 ≡ C 2 α a 1 + a 2 + m ( c 1 + c 2 ) ,

F 1 · A 2 · (mod n ) ≡

b 1 + b 2 + m ( d 1 + d 2 ) .
U 2 sends ( F 2 ,g 2 ) as his partial signature to the third signer.

g 2 ≡ g 1 + b 2 + m · d 2 (mod r ) ≡

...
i. The signer U i receives the U i− 1 's partial signature ( F i− 1 ,g i− 1 )andthen
verifies this partial signature checking if
P i− 1 Q ( i− 1) ·m ≡ β g i − 1 · F i− 1 · (mod n ) .

U i computes his partial signature:
F i ≡ C i α a 1 + ··· + a i + m ( c 1 + ··· + c i ) ,

F i− 1 · A i · (mod n ) ≡

g i ≡ g i− 1 + b i + m · d i (mod r ) ≡ b 1 + ··· + b i + m ( d 1 + ··· + d i ) .

U i sends ( F i ,g i ) to the next signer.

...
t. The last signer in the group, U t , receives the U t− 1 's partial signature and
verifies that signature testing if
P t− 1 Q ( t− 1) ·m ≡ β g t − 1 · F t− 1 · (mod n ) .

U t computes his partial signature for the message:
F t ≡ C t α a 1 + ··· + a t + m ( c 1 + ··· + c t ) ,

F t− 1 · A t · (mod n ) ≡

g t ≡ g t− 1 + b t + d t · m (mod r ) ≡ b 1 + ··· + b t + m ( d 1 + ··· + d t ) .

U t makes public the multisignature for M :( F, g )=( F t ,g t ).