一种高效的SM2数字签名批量验证算法

An efficient batch verification algorithm for SM2 signatures

数字签名在身份认证、抗抵赖性等方面具有重要作用。例如电子货币系统,商家或消费者需要使用数字签名对电子货币进行签署或验证,以确保电子货币信息的安全性与正确性。当同时对大量的电子现金进行数字签名验证时,会大幅度降低整个系统的运行效率,因此使用批量验证算法显得尤为重要。对于DSA、RSA和ECDSA等数字签名已经有了很多成熟的批量验证算法,但是对于SM2数字签名算法目前还没有对应的批量验证算法。首次提出一种高效的SM2批量验证算法,将最为耗时的点乘运算由n次降为1次(n为签名数量),大大缩短了验证时间。证明了SM2批量验证算法的正确性和安全性,并进行了实验验证。从实验结果可以看出,相对于单个验证算法,批量验证算法的效率显著提升,当签名数量达到约100万(220)时,单个验证算法大约需要1 h,而批量验证算法仅需2 s。

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.