In the past decade, pairing-based cryptography has emerged as an active area of research that gave rise to new algorithms, protocols, and primitives. These new techniques allowed researchers to achieve cryptographic schemes which had no known (or less efficient) counterparts in groups without bilinear pairings. In this dissertation, we introduce several schemes in which pairings play a central role in their construction. The results that we present in this dissertation stem from three papers which are respectively joint work with Rafail Ostrovsky, Amit Sahai, Hovav Shacham, and Brent Waters, with Jens Groth, and with Vipul Goyal, Amit Sahai, and Brent Waters.

In the dissertation, we present the first sequential aggregate signature, the first multisignature, and the first verifiably encrypted signature provably secure without random oracles. Our constructions derive from a novel application of a signature scheme due to Waters. We review the definition of these signature variants and consider applications to secure routing and proxy signatures. We show how these are constructed using pairing-based cryptography.

Another scheme we present is a non-interactive verifiable shuffle. A shuffle is a permutation and re-encryption of a set of ciphertexts. Shuffles are used, for instance, in mix-nets for anonymous broadcast and voting. One way to make a shuffle verifiable is to give a zero-knowledge proof of correctness. All currently known practical zero-knowledge proofs for correctness of a shuffle rely on interaction. We give the first efficient non-interactive zero-knowledge proof for correctness of a shuffle based on pairings.

Finally, we consider the problem of accountability for PKGs in identity-based encryption. A well-known concern in the setting of identity-based encryption is that the PKG is all powerful and must be completely trusted. To mitigate this problem, the notion of Accountable Authority Identity-Based Encryption (A-IBE) was recently introduced by Goyal, who provided constructions to realize the notion of A-IBE only in the white-box and weak black-box models. In this dissertation, we present a resolution to the main open question left in Goyal's work by providing a construction of a fully black-box A-IBE system. We show how such a scheme can be securely realized from generic underlying primitives, then give a concrete realization of the scheme in any bilinear group where the Decisional Bilinear Diffie-Hellman assumption holds.