A New ID-based Signature with Batch Verification

Jung Hee Cheon; Yongdae Kim; Hyo Jin Yoon

Paper 2004/131

A New ID-based Signature with Batch Verification

Jung Hee Cheon, Yongdae Kim, and Hyo Jin Yoon

Abstract

An identity (ID)-based signature scheme allows any pair of users to communicate securely and to verify each other's signatures without exchanging public key certificates. We have several ID-based signatures based on the discrete logarithm problem. While they have an advantage that the system secret can be shared by several parties through threshold schemes, they have a critical disadvantage in efficiency. To enhance the efficiency of verification, we propose a new ID-based signature scheme that allows batch verification of multiple signatures. The verification cost of the proposed signature scheme for signatures is almost constant with minimal security loss and when a new signature by a different signer is added to the batch verification, the additional cost is almost a half of that of a single signature. We prove that the proposed signature scheme is secure against existential forgery under adaptively chosen message and ID attack in the random oracle model and show why other ID-based signature schemes are hard to achieve these properties.

Metadata

Available format(s): PDF PS
Category: Cryptographic protocols
Publication info: Published elsewhere. Unknown where it was published
Keywords: ID-based signatures Batch verifications
Contact author(s): jin25 @ math snu ac kr
History: 2004-06-03: received
Short URL: https://ia.cr/2004/131
License: CC BY

BibTeX

@misc{cryptoeprint:2004/131,
      author = {Jung Hee Cheon and Yongdae Kim and Hyo Jin Yoon},
      title = {A New {ID}-based Signature with Batch Verification},
      howpublished = {Cryptology {ePrint} Archive, Paper 2004/131},
      year = {2004},
      url = {https://eprint.iacr.org/2004/131}
}