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 permu-tations 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 com-
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 permu-tations 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 com-
In this paper, we propose an efficient, standard model, semi-generic transformation of selectivesecure (Hierarchical) Identity-Based Encryption schemes into fully secure ones. The main step is a procedure that uses admissible hash functions (whose existence is implied by collision-resistant hash functions) to convert any selective-secure wildcarded identity-based encryption (WIBE) scheme into a fully secure (H)IBE scheme. Since building a selective-secure WIBE, especially with a selective-secure HIBE already in hand, is usually much less involved than directly building a fully secure HIBE, this transform already significantly simplifies the latter task. This black-box transformation easily extends to schemes secure in the Continual Memory Leakage (CML) model of Brakerski et al. (FOCS 2010), which allows us obtain a new fully secure IBE in that model. We furthermore show that if a selective-secure HIBE scheme satisfies a particular security notion, then it can be generically transformed into a selective-secure WIBE. We demonstrate that several current schemes already fit this new definition, while some others that do not obviously satisfy
Receiver selective opening (RSO) security considers the security of encryption schemes under the scenario of a single sender and multiple receivers, where an adversary is allowed to adaptively corrupt some receivers’ secret keys. RSO security has been proven to be more secure than indistinguishability-based security notions. A lot of research has focused on RSO security in terms of public-key encryption and identity-based encryption (IBE); however, hierarchical IBE (HIBE), which is a generalization of IBE, is still lacking in the study, and how to obtain such a construction remains an open problem. To address this gap, we initiate a study of RSO security on HIBE in this work. Precisely, we first formalize the definition of simulation-based RSO against identity-chosen-plaintext/ciphertext attacks in the k-challenge setting (SIM-ID-RSO k -CPA/CCA) for HIBE. We then present generic SIM-ID-RSO k -CCA secure HIBE constructions by introducing the double secret key paradigm. Specifically, we show that a SIM-ID-RSO k -CCA secure HIBE scheme can be obtained from an IND-ID-CPA secure HIBE scheme as well as a one-time signature scheme that satisfies strong unforgeability. Through our general construction, we can derive various concrete schemes based on different hard assumptions (e.g., lattice-based and pairing-based SIM-ID-RSO k -CCA secure HIBE schemes) according to usage requirements.
Abstract We construct the first tightly secure hierarchical identity-based encryption (HIBE) scheme based on standard assumptions, which solves an open problem from Blazy, Kiltz, and Pan (CRYPTO 2014). At the core of our constructions is a novel randomization technique that enables us to randomize user secret keys for identities with flexible length. The security reductions of previous HIBEs lose at least a factor of Q, which is the number of user secret key queries. Different to that, the security loss of our schemes is only dependent on the security parameter. Our schemes are adaptively secure based on the Matrix Diffie-Hellman assumption, which is a generalization of standard Diffie-Hellman assumptions such as k-Linear. We have two tightly secure constructions, one with constant ciphertext size, and the other with tighter security at the cost of linear ciphertext size. Among other things, our schemes imply the first tightly secure identity-based signature scheme by a variant of the Naor transformation.
Recent breakthroughs in cryptography have positioned indistinguishability obfuscation as a “central hub” for almost all known cryptographic tasks, and as an extremely powerful building block for new cryptographic tasks resolving long-standing and foundational open problems. However, constructions based on indistinguishability obfuscation almost always rely on non-black-box techniques, and thus the extent to which it can be used as a building block has been completely unexplored so far. We present a framework for proving meaningful negative results on the power of indistinguishability obfuscation. By considering indistinguishability obfuscation for oracle-aided circuits, we capture the common techniques that have been used so far in constructions based on indistinguishability obfuscation. These include, in particular, non-black-box techniques such as the punctured programming approach of Sahai and Waters [A. Sahai and B. Waters, How to use indistinguishability obfuscation: Deniable encryption, and more, in Proceedings of the 46th Annual ACM Symposium on Theory of Computing, ACM, New York, 2014, pp. 475--484] and its variants, as well as subexponential security assumptions. Within our framework we prove the first negative results on the power of indistinguishability obfuscation and of the tightly related notion of functional encryption. Our results are as follows: (1) There is no fully black-box construction of a collision-resistant function family from an indistinguishability obfuscator for oracle-aided circuits. (2) There is no fully black-box construction of a key-agreement protocol with perfect completeness from a private-key functional encryption scheme for oracle-aided circuits. Specifically, we prove that any such potential constructions must suffer from an exponential security loss, and thus our results cannot be circumvented using subexponential security assumptions. Our framework captures constructions that may rely on a wide variety of primitives in a non-black-box manner (e.g., obfuscating or generating a functional key for a function that uses the evaluation circuit of a puncturable pseudorandom function), and we only assume that the underlying indistinguishability obfuscator or functional encryption scheme itself is used in a black-box manner.
Recently, Luo et al. proposed an efficient hierarchical identity based encryption (HIBE) scheme with constant size of ciphertexts, and proved its full security under standard assumptions. To construct the scheme, they used the dual system encryption technique of Waters, and devised a method that compresses the tag values of dual system encryption. In this paper, we show that the security proof of Luo et al. is wrong since there exists an algorithm that distinguishes whether it is a simulation or not.