Identyfikacja blednych podpisow w kolekcjach

Weryfikacja poprawnosci podpisów cyfrowych jest obliczeniowo kosztowna. Aby ja zwiekszyc, zamiast pojedynczych podpisów weryfikacji poddaje sie kolekcje. Jezeli wszystkie podpisy w kolekcji sa poprawne, to cała kolekcja jest akceptowana. Pojawienie sie błednych podpisów w kolekcji powoduje, ze weryfikacja jest błedna. Nie mozna odrzucic całej kolekcji, zachodzi wiec koniecznosc identyfikacji błednych podpisów w kolekcji. W artykule zdefiniowano metody identyfikacji błednych podpisów. W szczególnosci okreslono weryfikacje typu „dziel i rzadz”, w których wejsciowe kolekcje sa dzielone na podkolekcje tak długo, az koncowe błedne kolekcje zawieraja pojedyncze podpisy. Opisano równiez weryfikator Hamminga identyfikujacy jeden błedny podpis w kolekcji oraz uogólniono ten weryfikator do postaci dwupoziomowego weryfikatora, umozliwiajacego identyfikacje dwóch błednych podpisów. Podano tez definicje ogólnego weryfikatora zdolnego do identyfikacji dowolnej liczby błednych podpisów w kolekcjach.