A Secure Signature Scheme From Bilinear Maps

The authors present a new class of signature schemes based on properties of certain bilinear algebraic maps. These signatures are secure against existential forgery under a chosen message attack in the standard model (without using the random oracle model). Security is based on the computational Diffie-Hellman problem. The concrete schemes that they get are the most efficient provable discrete-log type signature schemes to date. Provably secure signature schemes can be constructed from the most basic cryptographic primitive, one-way functions [NY89,Rom90]. As is often the case with cryptographic schemes designed from elementary blocks, this signature scheme is somewhat impractical. Over the years several signature schemes were proposed based on stronger complexity assumptions.