We propose the first batch verifier for messages from many (certified) signers without random oracles and with a verification time where the dominant operation is independent of the number of signatures to verify. We further propose a new signature scheme with very short signatures, for which batch verification for many signers is also highly efficient. Combining our new signatures with the best known techniques for batching certificates from the same authority, we get a fast batch verifier for certificates and messages combined. Although our new signature scheme has some restrictions, it is very efficient and still practical for some communication applications.
Category / Keywords: signatures, batch verification, screening, vehicular networks Publication Info: Full version of the Eurocrypt 2007 paper Date: received 9 May 2007, last revised 3 Sep 2009 Contact author: michael at daimi au dk Available format(s): PDF | BibTeX Citation Version: 20090903:072019 (All versions of this report) Short URL: ia.cr/2007/172