12. Harn

A digital signature is analogous to an ordinary hand-written signature used for signing messages. It must be unique and private to the signer. More specifically, suppose that B is the recipient of a message m signed by A. Then, A’s signature must satisfy three requirements [1]:

1. B must be able to validate A’s signature on m easily.
2. It must be impossible for anyone, including B, to forge A’s signature.
3. It must be possible for a judge or third party to resolve any dispute between A and B.

At this time, there are two most popular public-key algorithms which can provide digital signatures: (a) the RSA scheme [2], in which the difficulty of breaking the scheme is based on solving the factoring a large integer into two large prime factors, and (b) the ElGamal scheme [3], in which the difficulty of breaking the scheme is based on solving the discrete logarithm problem.

The RSA digital signature has been adopted by Visa and Master Cards in the Secure Electronic Transactions (SET) standard [4] for providing security of electronic transfers of credit and payment information over the Internet. In SET, signatures are used to provide certificates for public keys and to authenticate messages. Since public-key cryptography requires intensive computations, it is desirable to speed up these public-key computations by using either special-purpose hardware or efficient software algorithms. In this paper, we propose an efficient algorithm to verify batch RSA signatures signed by the same private key. Instead of verifying one signature at a time, we propose to verify multiple signatures simultaneously. This approach maintains the same computational load as to verify a single signature. Thus, a significant reduction in time for signature verification can be achieved. The application of our scheme can be used in the Electronic Commerce to reduce the computational load significantly. For example, multiple public-key certificates signed by the same certificate authority (CA), or multiple authenticate messages signed by the same payment gateway can be verified based on our scheme.

The scheme is based on the property that RSA signatures satisfy the multiplicative property. We use the following example to illustrate this property.

Assume that the RSA signature scheme has selected the modulus n=pq, where p and q are two large secret primes. Let us denote e as the public key and d as the private key, where ed mod(p-1)(q-1)=1, and h(.) is a one-way hash function. The RSA’s signature of a message m_{i i} is S_i=h(m_i)^d mod n. The signature verification is performed by checking whether h(m_i)= S_i^e mod n. We assume that the RSA signatures of m₁, _i m₂, …, _i m_t are S₁, _i S₂, …, _i S_t. Due to the multiplicative homomorphism, we can easily prove the following theorem.

Theorem 1. If the signatures S₁, _i S₂, …, _i S_t, of m₁, _i m₂, …, _i m_t are all valid, then we have

We call the product of individual signatures p_i=1^t S_i mod n as the "multiplicative signature" of m₁, _i m₂, …, _i m_t. To verify this multiplicative signature needs only to compute one exponentiation. The objective of this paper is to prove that the multiplicative signature is a valid signature of messages m₁, _i m₂, …, _i m_t.

We would like to point out that the signer can generate two individual signatures S₁’= S₁/2 and S₂’= 2S₂ such that their product satisfies S₁’ S₂’= S₁ S₂. Since this ability can only be associated with the signer with proper secret key, any related dispute can be easily solved. In addition, in case the batch verification is failed, all individual signatures need to be verified separately.

We have proposed an efficient way to verify batch RSA signatures simultaneously. The performance of our scheme is almost constant.

Sep.13, 1997

12. Harn (Racal Datacom Group, Sunrise, FL 33323-2899, USA)