In this paper, we compare three methods in detecting invalid signatures in batch verification. The first method, randomly select test, randomly chooses a half of signatures to verify in a batch. The second method is the small exponent test which is widely used. The third method, randomly numbering test, is a simplified method of the matrix-detection algorithm. The randomly numbering test randomizes the order of the signatures and verifies the signatures in [log k] + 1 batches where k is the number of signatures. We simulate each method and analyze the efficiency of the methods. As a result, randomly numbering test is more efficient than small exponent test when the number of signatures in a batch verification is large.
展开▼
