International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 17 August 2015

Mohammad Mahmoody, Ameer Mohammedy
ePrint Report ePrint Report
We prove that there is no fully black-box construction of collision-resistant hash functions (CRH) from hierarchical identity-based encryption (HIBE) with arbitrary polynomial number of identity levels. As a corollary we obtain a series of separations showing that none of the primitives implied by HIBE in a black-box way (e.g., IBE, CCA-secure public-key encryption) can be used in a black-box way to construct fully homomorphic encryption or any other primitive that is known to imply CRH in a black-box way. To the best of our knowledge, this is the first limitation proved for the power of HIBE.

Our proof relies on the reconstruction paradigm of Gennaro and Trevisan (FOCS 2000) and Haitner et al (FOCS 2007) and extends their techniques for one-way and trapdoor permutations to the setting of HIBE. A technical challenge for our separation of HIBE stems from the adaptivity of the adversary who is allowed to obtain keys for different identities before she selects the attacked identity. Our main technical contribution is to show how to achieve compression/reconstruction in the presence of such adaptive adversaries.

Expand

Additional news items may be found on the IACR news page.