Paper 2015/815

On the Power of Hierarchical Identity-Based Encryption

Mohammad Mahmoody and Ameer Mohammed

Abstract

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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
FoundationsHierarchical Identity-based EncryptionCollision Resistant HashingHomomorphic EncryptionBlack-Box Separations.
Contact author(s)
mahmoody @ gmail com
History
2015-09-14: last of 2 revisions
2015-08-17: received
See all versions
Short URL
https://ia.cr/2015/815
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/815,
      author = {Mohammad Mahmoody and Ameer Mohammed},
      title = {On the Power of Hierarchical Identity-Based Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2015/815},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/815}},
      url = {https://eprint.iacr.org/2015/815}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.