Batch verifying multiple DSA-type digital signatures
Lein Harn · Electronics Letters · 1998
The digital signature standard proposed by the US government in 1991 is an ElGamal-type signature scheme based on the discrete logarithm problem. Since verifying each ElGamal-type signature requires at least two modular exponentiations, and modular exponentiation is a computationally intensive operation, it becomes desirable to use special purpose hardware or an efficient software algorithm to speed up the signature verification process. The author proposes efficient and secure algorithms to verify multiple digital signatures based on the discrete logarithm. Instead of verifying each individual signature separately, it is proposed to verify multiple signatures simultaneously. The proposed batch verification algorithm can maintain a constant verification time as to verify a single signature.