Name
Abstract | ||
|---|---|---|
We prove that there is no black-box construction of a threshold predicate encryption system from identity-based encryption. Our result signifies nontrivial progress in a line of research suggested by Boneh, Sahai and Waters (TCC '11), where they proposed a study of the relative power of predicate encryption for different functionalities. We rely on and extend the techniques of Boneh et al. (FOCS '08), where they give a black-box separation of identity-based encryption from trapdoor permutations. In contrast to previous results where only trapdoor permutations were used, our starting point is a more powerful primitive, namely identity-based encryption, which allows planting exponentially many trapdoors in the public-key by only planting a single master public-key of an identity-based encryption system. This makes the combinatorial aspect of our black-box separation result much more challenging. Our work gives the first impossibility result on black-box constructions of any cryptographic primitive from identity-based encryption. We also study the more general question of constructing predicate encryption for a complexity class F, given predicate encryption for a (potentially less powerful) complexity class G. Toward that end, we rule out certain natural black-box constructions of predicate encryption for NC1 from predicate encryption for AC0 assuming a widely believed conjecture in communication complexity. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-28914-9_25 | TCC |
Keywords | Field | DocType |
predicate encryption scheme,black-box separation result,trapdoor permutation,black-box construction,black-box separation,identity-based encryption,black-box reduction,certain natural black-box construction,communication complexity,predicate encryption,identity-based encryption system,threshold predicate encryption system | Multiple encryption,Discrete mathematics,Computer science,Deterministic encryption,Attribute-based encryption,Plaintext-aware encryption,Encryption,Theoretical computer science,Probabilistic encryption,40-bit encryption,56-bit encryption | Conference |
Volume | ISSN | Citations |
7194 | 0302-9743 | 8 |
PageRank | References | Authors |
0.49 | 34 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vipul Goyal | 1 | 2859 | 129.53 |
| Virendra Kumar | 2 | 11 | 0.91 |
| Satya Lokam | 3 | 8 | 1.17 |
| Mohammad Mahmoody | 4 | 200 | 19.27 |