Digital Multisignature with Distinguished Signing Authorities

Indexing terms: Digital multisignature, Discrete logarithm

Introduction

The digital multisignature (i.e. also called "the group signature") is analogous to an ordinary digital signature. Instead of generating the digital signature by an individual signer with the knowledge of a single private key, the digital multisignatures are generated by multiple group members with the knowledge of multiple private keys. We list the following properties associated with the multisignature:

    1. Digital multisignatures are generated by multiple group members with the knowledge of multiple private keys;

    2. Digital multisignatures can be verified easily by using the group public key without knowing each signer’s public key;

    3. It is computational infeasible to generate the group signature without the corporation of all group members.

Harn has proposed two ElGamal-type efficient multisignature schemes [1, 2] which can combine all individual group signatures into a multisignature without any data expansion. In addition, in Harn’s schemes, the group public key is equivalent to the product of all group members’ public keys. This feature enables all group members to establish the security without the assistance of a mutually trusted party. However, since in these two schemes all group members sign same messages, we call these schemes the multisignature schemes with undistinguished signing authorities. In other words, all group members hold the same responsibility of signing the document.

Properties of multisignature with distinguished signing authorities

In fact, there are some applications that need to use multisignatures with distinguished signing authorities. For example, a company releases a document that may involve financial department, engineering department and program office. Each entity is responsible of preparing and signing a particular section of the document. The signing authority of engineering department may have no interest to read the content prepared by the financial department. However, the combination of all sections represents the company’s document. The company’s document should be easily verified by any outsider using company’s public key. For the sake of confidentiality, some verifiers may be restricted to access and verify only some sections of the document. The multisignature schemes proposed in references [1, 2] cannot provide these features. In this letter, we modify these schemes to convert them to be a multisignature scheme with distinguished signing authorities. We list the following additional properties associated with the multisignature with distinguished signing authorities:

    1. Each group member has distinguished signing responsibility;

    2. Partial contents of the document can be verified without revealing the whole document.

We would like to point out that multisignature with distinguished signing authorities can be found in many cryptographic applications. For example, credit card, telephone, and medical insurance companies can establish a joint venture to issue smart cards to customers. By using the multisignature proposed in this letter can

    1. Allow each company to register and sign its own customers;

    2. Enhance the card security since multiple private keys needed to forge a group signature;

    3. Reduce memory storage on each card since only a multisignature is needed on each card;

    4. Reduce memory storage of each verifier since only the group public key is needed;

    5. Speed up signature verification;

    6. Provide confidentiality by just revealing partial customer’s information to some verifiers.

Review of Harn’s digital multisignature

Here, we would like to review the design concept of the multisignature proposed in reference [1].

Determining the public keys:

A large prime, p, a primitive element, signer randomly selects an integer xi from [1, p-1] and computes a corresponding public key as

The public key for all signers is equivalent to the product of all individual public keys.

We start with the multisignature generating phase.

Generating the multisignature:

Phase 1: Determining the commitment value of r

We assume that there are two signers, U1 and U2, to sign the same message m. Each signer ui randomly selects a number ki from [1, p-1] and computes

(ri) is broadcasted to the other signer. Once r1 and r2 are available through the broadcast channel, each signer computes the commitment value r as r= r1r2 mod p.

Phase 2: Determining the multisignature value of s

Instead of signing the message m directly, all signers should sign the one-way hash result m'=h(m), where h is the one-way hash function. Each signer uses his secret keys, xi and ki, to sign the message m'. Ui solves the equation

for in Once the clerk receives the individual signature (ri, si) from Ui, he needs to verify the validity of this individual signature. The verification procedure is to check

the clerk, the Verifying the multisignature:

Since individual signatures, (r1, s1) and (r2, s2), satisfy

By multiplying these two equations, we obtain the multisignature verification equation as

where y=y1y2 mod p.

Proposed multisignature scheme with distinguished signing authority:

The group public key and the commitment value r can be determined in the same way as described previously. However, since the commitment value r does not depend on the message, this value can be pre-determined by all signers.

Instead of signing the same message m directly, each signer should prepare a section of message mi that he is responsible of and broadcast h(mi) to all other signers, where h is the one-way hash function. Under our previous assumption that U1 and U2 are two signers in a group. Each signer, Ui for i=1, 2, uses his secret keys, xi and ki, to sign the message m'=h(h(m1), h(m2)), where h(h(m1), h(m2)) means the hash value of the concatenation of h(m1) and h(m2). The individual signature (ri, si) from Ui and the multisignature of message m=(m1, m2) are generated in the same way as described previously.

Discussion:

    1. Since each singer is responsible of preparing a section of message, each signer has distinguished signing authority.

    2. Instead of signing m’=h(m1, m2), each signer needs to sign m'=h(h(m1), h(m2)). The computation of h(h(m1), h(m2)) is faster than that of h(m1, m2) since each signer needs only to compute his own h(mi) and the other h(mi) has been computed by the other signer.

    3. In order to successfully forge a group signature, the attacker needs to know all signing keys.

    4. In case some verifiers only allowed to access partial contents of the message, the partial contents can still be verified using the group public key without revealing whole message. This feature can be achieved by just providing the one-way hash values of the inaccessible contents to the verifier. For example, by revealing m1 and h(m2) to the verifier, the verifier can still verify the authenticity of m1.

    5. Signature schemes, (1), (3), (7), (8), (13) and (14), as listed in the Table of reference [3] can provide similar multisignature schemes.

Lein Harn Oct. 20, 1998

(Department of Computer networking, University of Missouri-Kansas City, MO 64110, USA)

References

1. Harn, L.,: 'Group-oriented (t, n) threshold signature and multisignature', IEE Proceedings-E, accepted in Feb. 1994.

2. Harn, L.,:'New digital signature scheme based on discrete logarithm', Electronics Letters, Vol. 30 No. 5, March 1994, pp. 396-398.

3. Harn, L. and Xu Y.,: 'On the design of generalized ElGamal type digital signature schemes based on the discrete logarithm", Electronics Letters, accepted in Nov. 1994.