Fast batch verification of multiple signatures

Abstract. We propose an efficient batch verification of multiple signa-tures generated by different signers as well as a single signer. We first introduce a method to generate width-w Non-Adjacent Forms (w-NAFs) uniformly. We then propose a batch verification algorithm of exponentia-tions using w-NAF exponents, and apply this to batch verification for the modified DSA and ECDSA signatures. The performance analysis shows that our proposed method is asymptotically seven and four times as fast as individual verification in case of a single signer and multiple signers, respectively. Further, the proposed algorithm can be generalized into τ-adic w-NAFs over Koblitz curves and requires asymptotically only six elliptic curve additions per each signature for batch verification of the modified ECDSA signatures by a single singer. Our result is the first one to efficiently verify multiple signatures by multiple signers that can introduce much wider applications