2012 | OriginalPaper | Buchkapitel
On Black-Box Reductions between Predicate Encryption Schemes
verfasst von : Vipul Goyal, Virendra Kumar, Satya Lokam, Mohammad Mahmoody
Erschienen in: Theory of Cryptography
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$\mathbb{F}$
, given predicate encryption for a (potentially less powerful) complexity class
$\mathbb{G}$
. Toward that end, we rule out certain natural black-box constructions of predicate encryption for
NC
1
from predicate encryption for
AC
0
assuming a widely believed conjecture in communication complexity.