A Batch Verification Scheme by Using the Matrix-Detection Algorithm

Abstract

When a government office O delivers a batch of documents to a remote government office R, for security consideration, R has to verify whether the documents received are those originally sent by O or not. To do so, we need a security mechanism to perform the verification. That is, before sending the documents, the mailroom of O encrypts them with a private key, i.e., a digital signature. On receiving the documents, the mailroom of R decrypts them as a verification test with the corresponding public key. However, verifying the signatures of the documents received one by one is a crucial and inefficient work. In fact, if we can treat the documents received as a whole, and verify their signatures simultaneously, the verification efficiency will be higher. Therefore, a batch verification approach, a method simultaneously verifying a batch of signatures as a whole, was then proposed. In literatures, some batch verification schemes cannot efficiently and effectively identity bad signatures existing in a set of given signatures. The Small Exponent Test, a popular batch verification method, has its own problems, e.g., after a test, bad signatures still exist with some escape probability. In this paper, we propose a batch verification approach, called Matrix-Detection Algorithm (MDA for short), with which when the number of bad signatures in a batch of signatures is less than four, the batch cannot pass the MDA verification test. Analytical results show that the MDA is more secure and efficient than the SET.