Cryptology ePrint Archive: Report 2012/549
Faster batch forgery identification
Daniel J. Bernstein and Jeroen Doumen and Tanja Lange and Jan-Jaap Oosterwijk
Abstract: Batch signature verification detects whether a batch of signatures contains any forgeries. Batch forgery identification pinpoints the location of each forgery. Existing forgery-identification schemes vary in their strategies for selecting subbatches to verify (individual checks, binary search, combinatorial designs, etc.) and in their strategies for verifying subbatches. This paper exploits synergies between these two levels of strategies, reducing the cost of batch forgery identification for elliptic-curve signatures.
Category / Keywords: public-key cryptography / signatures, batch verification, elliptic curves, scalar multiplication
Date: received 20 Sep 2012
Contact author: tanja at hyperelliptic org
Available format(s): PDF | BibTeX Citation
Note: Expanded version of Indocrypt 2012 paper.
Version: 20120922:124501 (All versions of this report)
Short URL: ia.cr/2012/549
[ Cryptology ePrint archive ]