Paper 2012/687

The k-BDH Assumption Family: Bilinear Map Cryptography from Progressively Weaker Assumptions

Karyn Benson, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. An extended abstract will appear at CT-RSA 2013. This is the full version.
Keywords
pairingsIdentity Based Encryptionweaker assumptions
Contact author(s)
kbenson @ cs ucsd edu
History
2012-12-10: received
Short URL
https://ia.cr/2012/687
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/687,
      author = {Karyn Benson and Hovav Shacham and Brent Waters},
      title = {The k-BDH Assumption Family: Bilinear Map Cryptography from Progressively Weaker Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2012/687},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/687}},
      url = {https://eprint.iacr.org/2012/687}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.