28-11-2012, 02:23 PM
Group-oriented (t, n) threshold digital signature scheme and digital multisignature
Group-oriented.pdf (Size: 585.56 KB / Downloads: 31)
Abstract:
The paper presents group-oriented (t, n)
threshold digital signature schemes based on the
difficulty of solving the discrete logarithm
problem. By employing these schemes, any t out
of n users in a group can represent this group to
sign the group signature. The size of the group signature
and the verification time of the group signature
are equivalent to that of an individual
digital signature. In other words, the (t. n) threshold
signature scheme has the following five
properties: (i) any group signature is mutually
generated by at least t group members; (ii) the size
of the group signature is equivalent to the size of
an individual signature; (iii) the signature verification
process is simplified because there is only one
group public key required; (iv) the group signature
can be verified by any outsider; and (v) the
group holds the responsibility to the signed
message. In addition to the above properties, two
of the schemes proposed do not require the assistance
of a mutually trusted party. Each member
selects its own secret key and the group public key
is determined by all group members.
Introduction
The threshold cryptosystem was first introduced by
Desmedt [4] in 1987. In this system, each group, instead
of each group member, publishes a single group public
key. An outsider can use this single public key to send an
encrypt message to this group. The received ciphertext
can only be deciphered properly when the number of participating
group members is larger than or equal to the
threshold value. All up-to-date solutions for the grouporiented
threshold cryptosystem can be classified into the
following two categories: (i) solutions with the assistance
of a mutually trusted party to decide the group secret key
and generate individual secrets for all group members
[ S , 8, lo]; and (ii) solutions without the assistance of a
mutually trusted party 113, 161. As pointed out by Ingemarsson
and Simmons [ll], in most applications a
trusted party in a group does not exist. This situation
becomes more common in some commercial and/or
international applications. Thus, the solutions without
the assistance of a mutually trusted party become very
attractive.
Modified ElGamal signature scheme
This scheme was developed from EIGamal’s original signature
scheme [7] in 1985, the modified ElGamal scheme
being proposed by Agnew et al. [I] in 1990.
The scheme starts with a large prime, p, and a primitive
element, a, of GF(p), which are publicly known. In
order to provide adequate security, Pohlig and Hellman
[I71 indicate that p should be selected such that p - 1
contains at least one large prime factor. They recommend
choosing p = 2p’ + I, where p’ is also a large prime. A
one-way functionfalso needs to be made public.
Other features
(i) In this scheme, a signature signed only by partial
members cannot be verified correctly by an outsider. In
other words, a valid group signature must be mutually
generated by all members.
(ii) The group signature in this scheme consists of a
pair of {r, s}. The n individual signatures produced by all
members consist of n pairs of { r i , si}. Thus, the scheme
combines n individual signatures into a single signature.
(iii) The group signature verification process requires
two modular exponentiations. However, the varification
process for n individual signatures requires 2n modular
exponentiations. Thus, this scheme speeds up the verification
process by a factor of n.
(iv) The same scheme can be easily applied to solve the
digital multisignature problem. Instead of combining n
individual signatures in a group-oriented signature, the
digital multisignature scheme should be able to combine
any number of individual signatures into a multisignature.
Also, instead of using a fixed group public key
to verify the signature in the group-oriented signature
scheme, the verifier in the digital multisignature scheme
should use all signer's public keys to verify the multisignature.
There are two properties that need to be
achieved in the design of an optimal digital multisignature
scheme: (a) the size of the multisignature
should be equivalent to the size of an individual's signature;
and (b) the verification process of multisignature
should be almost equivalent to the verification process of
an individual's signatures.
Conclusion
Three threshold digital signature schemes based on the
difficulty of solving the discrete logarithm problem are
proposed. The group signature can be generated when
the number of participating members is larger than or
equal to the threshold value. The size of the group signature
and the verification time of the signature are the
same as that of an individual signature. The first scheme
is a special case which requires all group members to sign
the message together. This scheme can be easily applied
to generate digital multisignature. The second scheme
provides a general solution and it requires the assistance
of a mutually trusted party; however, the third scheme
does not require the mutually trusted party.