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