Abstrakt. Detta dokument beskriver nya metoder i parningsbaserade signatursystem för att identifiera ogiltiga digitala signaturer i ett parti, efter att partiverifieringen har misslyckats. Dessa metoder identifierar effektivt icke-trivialt antal ogiltiga signaturer i satser av (potentiellt stora) antal signaturer. Våra metoder använder "split-and-conquer" sökning för att identifiera ogiltiga signaturer i ett parti, men beskär sökträdet för att avsevärt minska antalet parning beräkningar som krävs. De metoder som presenteras i detta papper kräver beräkning på genomsnittliga O(w) produkter av parningar för att identifiera w ogiltiga signaturer inom ett parti av storlek N, jämfört med O(w(w(log 2 (N/w)+1)) [för w < N/2] som traditionella uppdelning-och-konquer metoder kräver. Våra metoder undviker problemet med exponentiell tillväxt av förväntade beräkningskostnader som påverkar tidigare förslag som i genomsnitt kräver datorprodukter från parningar. Vi jämför den förväntade prestandan hos våra batchverifieringsmetoder med tidigare publicerade split-and-conquer och exponentiella kostnadsmetoder för Cha-Cheon identitetsbaserade signaturer [6]. Våra metoder gäller dock också för ett antal korta signatursystem och andra identitetsbaserade signatursystem.
Utmed liknande linjer, Matt förbättrar prestandan av dessa metoder när antalet ogiltiga signaturer är stort REF.
Identification of multiple invalid signatures in pairing-based batched signatures
{'venue': 'PKC 2009, volume 5443 of LNCS', 'journal': None, 'mag_field_of_study': ['Computer Science']}