Cryptology ePrint Archive: Report 2012/687
The k-BDH Assumption Family: Bilinear Map Cryptography from Progressively Weaker Assumptions
Karyn Benson and Hovav Shacham and Brent Waters
Abstract: Over the past decade bilinear maps have been used to build a large variety of cryptosystems.
In addition to new functionality, we have concurrently seen the emergence of many strong assumptions.
In this work, we explore how to build bilinear map cryptosystems under progressively weaker assumptions.
We propose $k$-BDH, a new family of progressively
weaker assumptions that generalizes the decisional bilinear
Diffie-Hellman (DBDH) assumption. We give evidence in the generic
group model that each assumption in our family is strictly weaker
than the assumptions before it. DBDH has been used for proving many
schemes secure, notably identity-based and functional encryption
schemes; we expect that our $k$-BDH will lead to generalizations of
many such schemes.
To illustrate the usefulness of our $k$-BDH family, we
construct a family of selectively secure Identity-Based Encryption (IBE) systems based on it. Our system can be viewed
as a generalization of the Boneh-Boyen IBE, however, the construction and proof require new ideas to
fit the family. We then extend our methods to produces hierarchical IBEs and CCA
security; and give a fully secure variant. In addition, we discuss the opportunities and challenges of building
new systems under our weaker assumption family.
Category / Keywords: public-key cryptography / pairings, Identity Based Encryption, weaker assumptions
Publication Info: An extended abstract will appear at CT-RSA 2013. This is the full version.
Date: received 6 Dec 2012
Contact author: kbenson at cs ucsd edu
Available format(s): PDF | BibTeX Citation
Version: 20121210:104749 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]