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

2. Each one of the following signers, in an ordered way, signs the document,
already signed by the one who is previous in the group.
3. The last member of G , U t , signs the signed document that the previous
signer has sent to him and sends to the verifier the original message and the
multisignature calculated by the group of signers.
The verifier performs the verification of the multisignature by checking each
one of the partial signatures of the group of signers, following the protocol and
keeping the order in which they were signed.
The first multisignature scheme was proposed in [5], where a modification of
the RSA cryptosystem was performed in such a way that the module considered
was the product of three primes instead of just two. In [6] a scheme was pro-
posed where the signature length is similar to the length of a simple signature
and shorter than the signature obtained from the scheme proposed in [5]. This
proposal can be used only if the cryptosystem is bijective. Other proposals based
on the RSA cryptosystems have been proposed [7,8,9,10,11].
Regarding multisignature schemes based on the discrete logarithm problem,
in [12] the group of signers must cooperate to sign the message and send the
signature to a given group of verifiers. Only the union of all verifiers is able to
validate the multisignature. Additionally, the signers must use not only their own
private keys, but also the public key of all the verifiers. However, this scheme
has some weaknesses [13,14]. The scheme proposed in [15] allows to perform a
multisignature if the verifiers of the signature belong to a previously specified
group.This scheme has some weaknesses as well [16,17].
In [18] a multisignature scheme for a generic model of public key is presented.
The model requires some properties: Each one of the signers must have a certified
public key with its corresponding private key, which must be generated by the
signer himself. The signers must interact in a given number of rounds. In each
round each signer receives a message, performs several calculations and sends
another message to the next signer. It must be computationally infeasible to
forge a multisignature if there exists one honest signer.
Our multisignature scheme has the property and advantage that each signer
has his own private key, but all of them share the same public key. In this sense,
the new scheme does not match exactly the model proposed in [18] since the
procedure is carried out in just one round in which all the signers participate.
Moreover, each signer does not need to have his own certified pair of keys (public
and private). In fact, in the protocol all the signers share the same public key,
but each one has his own private key. This fact simplifies and spares some of the
problems related to the computational effort for computation, bandwidth, and,
therefore, the overall eciency of the proposed protocol.
Our proposal verifies several properties: It is secure, ecient, independent
of the number of signers, the signature is determined by all the signers in any
previously given order, allows adding new signers, and the verification procedure
does require the verification of the partial signature of each member of G .