DSA Type Secure Interactive Batch Verification Protocols
L. Harn
Indexing terms: Cryptography, Signature verification
We propose some DSA type secure interactive batch verification protocols, where the signer generates n signatures through interactions with the verifier, and the verifier validates these n signatures at once.
Introduction: Naccache et al. [1] proposed various ways to optimize the DSA [2] for smart card applications. It included an interactive batch verification protocol, where the signer generates n signatures through interactions with the verifier, and then the verifier validates these n signatures at once based on the batch verification criterion. Lim and Lee [3] pointed out that the interactive DSA batch protocol proposed by Naccache et al. is insecure. The fundamental problem of this protocol is that the batch verification criterion used to verify n signatures is insecure, although it is derived by combining multiple secure DSA signature equations. In other words, Lim and Lee show ways to generate individual signatures to satisfy the batch verification criterion; but the individual signatures cannot satisfy the DSA signature verifications. Since the purpose of the protocol is to verify multiple signatures at once, we would like to propose some secure batch verification criteria to preserve security.
DSA type interactive batch transaction: It involves two procedures. The signer follows the signature collection protocol to generate n signatures through interactions with the verifier. Then the verifier validates these n signatures at once through the batch verification criterion.
(a) Signature collection protocol:
Let p, q and
a be the DSA type public parameters: p a large prime, q a large prime divisor of p-1 and a an element in Zp of order q. Let H denote the secure hash algorithm (SHA) and mi denote the ith message to be signed . The signer has a secret key xŒZq and a public key y=
.
(i) The signer randomly picks ki
ŒZq, and computes ri=
, for i=1, 2, ..., n. The signer also computes 
The signer sends R to the verifier.
(ii) For i=1, 2, ..., n, the following steps are performed:
(ii-a) The signer sends ri to the verifier.
(ii-b) The verifier replies with an e-bit message randomizer bi.
(ii-c) The signer sends si=xRH(mi
˜ÿ bi)-ki mod q.
(b) Batch verification criterion:
The verifier checks that
, and
y
=Ra
mod p.
and replaces {ri, si, bi, mi Ô for i=1, 2, ..., n} by the DSA type triples {R mod q, 
, (mi˜ÿ bi Ô for i=1, 2, ..., n)}.
Theorem: If all signatures are generated by the legitimate signer, it will satisfy the verification criterion.
{proof} According to (ii-c), each signature satisfies
y
= 
si mod p.
By multiplying above equation repeatedly for i=1, 2, ..., n, we have
mod p.
Thus, we obtain
y
=Ra
mod p. Q. E. D.
This scheme is essentially as fast as a single DSA verification. Since the verification criterion is one of the secure ElGamal type signature scheme as proposed in [4], (i.e. with signature equation rmx=k+s mod ∆(p) and signature verification yrm=ras mod p), only the legitimate signer with the knowledge of x can generate the signatures to satisfy the verification. Although the attacker can generate bogus signatures in the signature collection protocol, these signatures cannot satisfy the batch verification criterion. There are some other secure ElGamal type signature schemes as proposed in [4] that can also be used to design similar DSA type secure interactive batch verification protocols. We list those schemes in the following:
Signature Signature
equation verification
(1) mx=rk+s mod ∆(p) ym=rras mod p
(2) sx=rk+m mod ∆(p) ys=rram mod p
(3) sx=k+mr mod ∆(p) ys=ramr mod p
(4) (r+m)x=k+s mod ∆(p) yr+m=ras mod p
(5) sx=k+(m+r) mod ∆(p) ys=ram+r mod p
Conclusion: Instead of using an insecure batch verification criterion as proposed by the Naccache et al. in Eurocrypt '94, we propose several secure batch verification criteria in this letter. By using the interactive batch verification protocol, the signer follows the signature collection protocol to generate n signatures through interactions with the verifier and the verifier validates these n signatures at once through the batch verification criterion.
Dec.1, 1994
Lein Harn (Computer Science Telecommunications Program, University of Missouri - Kansas City, MO 64110, USA)
References
1. Naccache, D., M'Raihi, D., Rapheali, D., and Vaudenay, S.: 'Can DSA be improved: Complexity trade-offs with the digital signature standard', Pre-Proceedings of Eurocrypt '94, 1994, pp. 85-94.
2. NIST: ''Digital signature standard' (FIPS PUB XX, 1993).
3. Lim, C. H., and Lee, P. J.: 'Security of interactive DSA batch verification', Electronics Letters, Sept. 1994, Vol. 30, No 19, pp. 1592-1593.
4. 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.