Identification of Bad Signatures in Batches

摘要: The paper addresses the problem of bad signature identification in batch verification digital signatures. number generic tests necessary to identify all signatures a instance, is used measure efficiency verifiers. divide-and-conquer verifier DCV α (x,n) defined. identifies instance x length n by repeatedly splitting input into sub-instances. Its properties are investigated. In particular, probability distributions for one, two and three signatures, derived. average numbers GT ranging from 1 16 obtained computer simulation. Further, Hamming (HV) defined which allows single n=2 k -1 using k+2 tests. HV generalised two-layer (2HV). Given 2 − 2, 2HV expense 3k+3 work concluded comments about general model codes identifying t design verifiers combinatorial structures.