New Paradigms in Signature Schemes

Abstract

In a digital signature scheme, Alice uses her private key to sign a message of her choice. This procedure creates a signature, a short string that binds Alice to the message and the message to her. Anyone who has Alice's public key, the signature, and the message can verify that the signature is valid, i.e., was produced by Alice on the message at hand. No one but Alice can generate a signature on any message that verifies as valid under Alice's public key.

Digital signatures thus provide authenticity and integrity. That is, a signature by Alice on a message demonstrates that it was Alice who signed (and, therefore, intended to send) that message; and that the message is exactly the message sent by Alice, and was not tampered with. In a legal setting, they are sometimes said to provide nonrepudiation; however, this term is not well +defined.

Signatures are a standard cryptographic primitive with many applications in higher-level protocols.

Groups featuring a computable bilinear map are particularly well suited for signature-related primitives. For some signature variants the only constructionknown 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.

In this thesis, we describe several constructions that support the claim above. First, we consider Boneh-Lynn-Shacham (BLS) and Boneh-Boyen short signatures. BLA signatures with security comparable to 1024-bit RSA are 160 bits long, the shortest of any scheme based on standard assumptions. BB signatures can be as short as BLS or (in a variant with longer signatures) can be proved secure +without random oracle.

Next, we present several extension and variants of BLS signatures. Amongst these is the Boneh-Gentry-Lynn-Shacham aggregate signature scheme. In an aggregate signature scheme, it is possible, given n signatures on n distinct messages fromn distinct users, to aggregate all these signatures into a single short signature. This single aggregate suffices to convince a verifier that the usersdid indeed sign their respective messages.

BGLS aggregates are based on BLS signatures and are 160 bits long, regardless ofhow many signatures are aggregated. No construction is known for aggregate signatures that does not employ bilinear maps. We also show that BGLS aggregates give rise to verifiably encrypted signatures, a signature variant with applications in contract signing.

In a digression, we show how one can construct sequential aggregate signatures based only on the existance of trapdoor permutations. Sequential aggregate signatures is variant of aggregate signatures in which signing-and-aggregation is a single operation, in which each signer adds her signature to the aggregate signature of all the signers before her.

Next, we present the Boneh-Boyen-Shacham 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 a 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.

Finally, we consider variants and extensions of the BBS group signature scheme, including a group signature with a novel revocation mechanism that we call verifier-local revocation (VLR). In a VLR group signature, messages announcing the revocation of some users need only be processed by the verifiers;the signers are stateless. We present the Boneh-Shacham VLR group signature scheme, which has signatures even shorter than in BBS.

Back to publications
Back to previous page