TY - GEN
T1 - Identification of bad signatures in batches
AU - Pastuszak, Jaroslaw
AU - Michalek, Dariusz
AU - Pieprzyk, Josef
AU - Seberry, Jennifer
PY - 2000
Y1 - 2000
N2 - The paper addresses the problem of bad signature identification in batch verification of digital signatures. The number of generic tests necessary to identify all bad signatures in a batch instance, is used to measure the efficiency of verifiers. The divide-and-conquer verifier DCVα(x,n) is defined. The verifier identifies 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 obtained from computer simulation. Further, a Hamming verifier (HV) is defined which allows to identify a single bad signature in a batch of the length n = 2k −1 using k + 2 tests. HV is generalised into the two-layer Hamming verifier (2HV). Given a batch instance of the length 2k − 2, the 2HV verifier identifies 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 verification codes identifying t bad signatures and the design of verifiers using combinatorial structures.
AB - The paper addresses the problem of bad signature identification in batch verification of digital signatures. The number of generic tests necessary to identify all bad signatures in a batch instance, is used to measure the efficiency of verifiers. The divide-and-conquer verifier DCVα(x,n) is defined. The verifier identifies 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 obtained from computer simulation. Further, a Hamming verifier (HV) is defined which allows to identify a single bad signature in a batch of the length n = 2k −1 using k + 2 tests. HV is generalised into the two-layer Hamming verifier (2HV). Given a batch instance of the length 2k − 2, the 2HV verifier identifies 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 verification codes identifying t bad signatures and the design of verifiers using combinatorial structures.
UR - https://www.scopus.com/pages/publications/84957804123
M3 - Conference proceeding contribution
AN - SCOPUS:84957804123
SN - 3540669671
SN - 9783540669678
VL - 1751
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 28
EP - 45
BT - Public Key Cryptography - 3rd International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000, Proceedings
PB - Springer, Springer Nature
CY - Berlin; Heidelberg
T2 - 3rd International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000
Y2 - 18 January 2000 through 20 January 2000
ER -