[Resource Topic] 2004/131: A New ID-based Signature with Batch Verification

Welcome to the resource topic for 2004/131

A New ID-based Signature with Batch Verification

Authors: Jung Hee Cheon, Yongdae Kim, Hyo Jin Yoon


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 k
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.

ePrint: https://eprint.iacr.org/2004/131

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .