Josef Pieprzyk

Abstract. The paper addresses the problem of bad signature identi-cation in batch verication of digital signatures. The number of generic tests necessary to identify all bad signatures in a batch instance, is used to measure the eciency of veriers. The divide-and-conquer veri-er DCV (x; n) is dened. The verier identies all bad signatures in a batch instance x of the length n by repeatedly splitting the input into sub-instances. Its properties are investigated. In particular, probability distributions for the number of generic tests necessary to identify one, two and three bad signatures, are derived. The average numbers of GT tests necessary to identify bad signatures ranging from 1 to 16 are ob-tained from computer simulation. Further, a Hamming verier (HV) is de ned which allows to identify a single bad signature in a batch of the length n = 2 k 1 using k+2 tests. HV is generalised into the two-layer Hamming verier (2HV). Given a batch instance of the length 2 k 2, the 2HV verier identies a single bad signature using k + 2 tests and two bad signatures in expense of 3k+3 tests. The work is concluded by comments about a general model for verication codes identifying t bad signatures and the design of veriers using combinatorial structures.