International Association
for Cryptologic Research

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.