Identyfikacja błędnych podpisów w kolekcjach

Weryfikacja poprawności podpisów cyfrowych jest obliczeniowo kosztowna. Aby ją zwiększyć, zamiast pojedynczych podpisów weryfikacji poddaje się kolekcje. Jeżeli wszystkie podpisy w kolekcji są poprawne, to cała kolekcja jest akceptowana. Pojawienie się błędnych podpisów w kolekcji powoduje, że weryfikacja jest błędna. Nie można odrzucić całej kolekcji, zachodzi więc konieczność identyfikacji błędnych podpisów w kolekcji. W artykule zdefiniowano metody identyfikacji błędnych podpisów. W szczególności określono weryfikacje typu "dziel i rządź", w których wejściowe kolekcje są dzielone na podkolekcje tak długo, aż końcowe błędne kolekcje zawierają pojedyncze podpisy. Opisano również weryfikator Hamminga identyfikujący jeden błędny podpis w kolekcji oraz uogólniono ten weryfikator do postaci dwupoziomowego weryfikatora, umożliwiającego identyfikacje dwóch błędnych podpisów. Podano też definicję ogólnego weryfikatora zdolnego do identyfikacji dowolnej liczby błędnych podpisów w kolekcjach.

Verification of digital signatures is expensive in terms of computing resources required to perform the task. Batch verification is a technique that uses homomorphic property to increase efficiency. If all signatures are correct in a batch, the whole batch is accepted otherwise bad signature must be identified and rejected. For obvious reasons, rejection of bad batches is not possible as they typically include also valid signatures that must be accepted. In the paper, methods of bad signature identification are defined. In particular, the identification using the "divide and conquer" method is described. In this method the input batch is repeatedly divided into sub-batches until the final sub-batches contain single bad signatures. The Hamming verifier is defined as the one being able to identify a single bad signature. Its generalisation allowing identification of two bad signatures resulting in the so-called two level Hamming verifier, is given. The work concludes with remarks about verifiers that identify arbitrary number of bad signatures.