Abstract: Digital signature has many important applications such as identity authentication and non-repudiation. For example, in the e-cash system, merchants or consumers sign/verify e-cashes with digi- tal signatures to ensure the security and correctness of e-cashes. When a large number of e-cash signatures are simultaneously verified, the efficiency of the system is obviously reduced. Therefore, it is important to use the batch verification algorithms. Although many batch verification algorithms for standard digital signatures have been proposed, such as DSA, RSA and ECDSA, there isn’t a batch verification algorithm for SM2 digital signature. An efficient SM2 batch verification algorithm is firstly proposed. It reduces the most time-consuming point multiplication operation from n times to 1 time (n is the number of signatures) and remarkably shortens the running time for verification. The correctness and security of the SM2 batch verification algorithm are proved and verified by experiments. Experimental results show that the proposed batch verification algorithm is more efficient than the single verification algorithm. If the number of signatures is 1 million(220), the single verification algorithm  takes about an hour, while the batch verification algorithm  only needs 2 seconds. 

Key words: SM2, batch verification, digital signature, elliptic curve