Paper 2004/088

Efficient Batch Verification of Signature Schemes based on Bilinear Maps

Noel McCullagh

Abstract

In this paper we present batch signature verification schemes for identity and non-identity signatures schemes based on bilinear maps. We examine some signature schemes and exploit their properties so that we can batch process the verification of these signatures in an efficient manner. Batch verification of message signatures is useful in real world applications. Most email clients are predominantly offline and so do not download emails one at a time. Instead the mails arrive at an online mail server individually, where they are collected together and stored. It is only after some period of time that any mails on the server are downloaded in bulk. It is not unreasonable to have 5 - 10 emails download into your inbox in any one transaction with the mail server. Say these mails were all signed, then this would be an ideal time to do batch signature verification. We show that we can make substantial savings over the naïve approach of verifying one message signature at a time.