2012 | OriginalPaper | Chapter
On Black-Box Reductions between Predicate Encryption Schemes
Authors : Vipul Goyal, Virendra Kumar, Satya Lokam, Mohammad Mahmoody
Published in: Theory of Cryptography
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.