Identity-based lossy trapdoor functions: new definitions, hierarchical extensions, and implications

Abstract

Lossy trapdoor functions, introduced by Peikert and Waters (STOC’08), have received a lot of attention in the last years, because of their wide range of applications. The notion has been recently extended to the identity-based setting by Bellare et al. (Eurocrypt’12). An identity-based trapdoor function (IB-TDF) satisfying the lossy property introduced by Bellare et al. can be used to construct other cryptographic primitives in the identity-based setting: encryption schemes with semantic security under chosen-plaintext attacks, deterministic encryption schemes, and hedged encryption schemes that maintain some security when messages are encrypted using randomness of poor quality. However, the constructed primitives can be proved secure only against selective adversaries who select the target identity upfront. Our first contribution is an alternative definition for the lossiness of an identity-based trapdoor function. We prove that an IB-TDF satisfying the new property can be used to construct all the aforementioned primitives, in the identity-based setting, with security against adaptive adversaries. We further consider the new definition and its implications in the more general scenario of hierarchical identity-based cryptography, which has proved very useful both for practical applications and to establish theoretical relations with other cryptographic primitives (including encryption with chosen-ciphertext security or with forward-security). As a second contribution, we describe a pairing-based hierarchical IB-TDF satisfying the new definition of lossiness against either selective or, for hierarchies of constant depth, adaptive adversaries. This is also the first example of hierarchical trapdoor functions based on traditional (i.e., non-lattice-related) number theoretic assumptions. As a direct consequence of our two contributions, we obtain a hierarchical identity-based (HIB) encryption scheme with chosen-plaintext security, a HIB deterministic encryption scheme and a HIB hedged encryption scheme, all of them with security against adaptive adversaries.