id: 06046654
dt: a
an: 06046654
au: Goyal, Vipul; Kumar, Virendra; Lokam, Satya; Mahmoody, Mohammad
ti: On black-box reductions between predicate encryption schemes.
so: Cramer, Ronald (ed.), Theory of cryptography. 9th theory of cryptography
    conference, TCC 2012, Taormina, Sicily, Italy, March 19‒21, 2012.
    Proceedings. Berlin: Springer (ISBN 978-3-642-28913-2/pbk). Lecture
    Notes in Computer Science 7194, 440-457 (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: Predicate Encryption; Black-Box Reductions; Identity-based Encryption;
    Communication Complexity
ci: 
li: doi:10.1007/978-3-642-28914-9_25
ab: Summary: 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.
rv: