New paradigms in signature schemes
Digital signatures provide authenticity and nonrepudiation. They are a standard cryptographic primitive with many applications.
Groups featuring a computable bilinear map are particularly well suited for signature-related primitives. For some signature variants the only construction known is based on bilinear maps. Where constructions based on, e.g., RSA are known, bilinear-map-based constructions are simpler, more efficient, and yield shorter signatures. We support this thesis with three constructions. These constructions are proved secure in the appropriate security models. We also consider applications of each construction.
First, we present the BLS short signature scheme. BLS signatures with security comparable to 1024-bit RSA are 160 bits long, the shortest of any scheme based on standard assumptions.
Second, we present the BGLS aggregate signature scheme. In an aggregate signature scheme, it is possible, given n signatures on n distinct messages from n distinct users, to aggregate all these signatures into a single short signature. This single aggregate suffices to convince a verifier that the the users did indeed sign their respective messages. BGLS aggregates are based on BLS signatures and are 160 bits long, regardless of how many signatures are aggregated. No construction is known for aggregate signatures that does not employ bilinear maps.
Third, we present the BBS group signature scheme. Group signatures provide anonymity for signers. Any member of the group can sign messages, but the resulting signature keeps the identity of the signer secret. In some systems there is a third party that can trace the signature, or undo its anonymity, using a special trapdoor. BBS group signatures with security comparable to 1024-bit RSA are 1443 long, shorter than any previous scheme by an order of magnitude. The signing operation is also an order of magnitude more efficient than in previous schemes.