Verification of a Batch of Bad Signatures by Using the Matrix-Detection Algorithm

Batch verification is a method devised to verify multiple signatures as a whole simultaneously. In literatures, we can see that some conventional batch verification schemes cannot effectively and efficiently identity bad signatures. Small Exponent test, a popular batch verification method, has its own problems, e.g., after a test, bad signatures still exist with some escape probabilities. In this paper, we propose a batch verification approach, called Matrix-Detection Algorithm (MDA for short), with which when a batch of signatures has less than four bad signatures or odd number of bad signatures, all bad signatures can be identified. Given 1024 signatures with 4 bad signatures, the maximum escape probability p_max of the MDA is 5.3 × 10^-5, and p_max decreases as digital signatures or bad signatures increase. Analytic results show that the MDA is more secure and efficient than the SET.