Full text  Click to download. 
Citation  PhD Thesis, Stanford University, 2005

Author  Hovav Shacham

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 higherlevel protocols.
Groups featuring a computable bilinear map are particularly well
suited for signaturerelated primitives. For some signature variants
the only constructionknown is based on bilinear maps. Where
constructions based on, e.g., RSA are known, bilinearmapbased
constructions are simpler, more efficient, and yield shorter
signatures.
In this thesis, we describe several constructions that support the
claim above. First, we consider BonehLynnShacham (BLS) and
BonehBoyen short signatures. BLA signatures with security comparable
to 1024bit 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 BonehGentryLynnShacham 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 signingandaggregation 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 BonehBoyenShacham 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
1024bit 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 verifierlocal 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 BonehShacham VLR group signature scheme, which has
signatures even shorter than in BBS.