New constructions in pairing-based cryptography

2009 2009

Other formats: Order a copy

Abstract (summary)

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.

Indexing (details)

Computer science
0405: Mathematics
0984: Computer science
Identifier / keyword
Applied sciences; Pure sciences; Bilinear pairings; Cryptography; Pairing-based cryptography
New constructions in pairing-based cryptography
Lu, Steve Naichia
Number of pages
Publication year
Degree date
School code
DAI-B 70/03, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
Ostrovsky, Rafail
University of California, Los Angeles
University location
United States -- California
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.