2007 | OriginalPaper | Buchkapitel
Fast Batch Verification of Multiple Signatures
verfasst von : Jung Hee Cheon, Jeong Hyun Yi
Erschienen in: Public Key Cryptography – PKC 2007
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We propose an efficient batch verification of multiple signatures generated by
different signers
as well as a single signer. We first introduce a method to generate width-
w
Non-Adjacent Forms (
w
-NAFs) uniformly. We then propose a batch verification algorithm of exponentiations using
w
-NAF exponents, and apply this to batch verification for the modified DSA and ECDSA signatures. The performance analysis shows that our proposed method is asymptotically seven and four times as fast as individual verification in case of a single signer and multiple signers, respectively. Further, the proposed algorithm can be generalized into
τ
-adic
w
-NAFs over Koblitz curves and requires asymptotically only six elliptic curve additions per each signature for batch verification of the modified ECDSA signatures by a single singer. Our result is the first one to efficiently verify multiple signatures by multiple signers that can introduce much wider applications.