University of Wollongong
Browse

Identification of Bad Signatures in Batches

Download (295.97 kB)
conference contribution
posted on 2024-11-13, 14:12 authored by J Pastuszak, D Michalek, J Pieprzyk, Jennifer SeberryJennifer Seberry
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.

History

Citation

This conference paper was originally published as Pastuszak, J, Michalek, D, Pieprzyk, J and Seberry, J, Identification of Bad Signatures in Batches, in Imai, H and Zheng, Y (eds), Workshop on Practice and Theory in Public Key Cryptosystems, PKC2000,, Melbourne, Victoria, Australia. Lecture Notes in Computer Science, 1751, 2000, 28-45. Copyright Springer-Verlag. Original book available here. ISSN 0302 9743 ISBN 3 540 66967 1

Pagination

143-154

Language

English

RIS ID

5538

Usage metrics

    Categories

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC