Alex Escala
email: alex.escala@ma4.upc.edu

Javier Herranz
email: jherranz@ma4.upc.edu

Benoît Libert
email: benoit.libert@uclouvain.be

Carla Ràfols
email: carla.rafols@rub.de

Hierarchical Identity-Based (Lossy) Trapdoor Functions

Keywords: Lossy trapdoor functions, hierarchical identity-based encryption, partial lossiness

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 in theoretical cryptography. The notion has been recently extended to the identity-based setting by Bellare et al. (Eurocrypt'12). We provide one more step in this direction, by considering the notion of hierarchical identity-based (lossy) trapdoor functions (HIB-TDFs). Hierarchical identity-based cryptography has proved very useful both for practical applications and to establish theoretical relations with other cryptographic primitives. The notion of security for IB-TDFs put forward by Bellare et al. easily extends to the hierarchical scenario, but an (H)IB-TDF secure in this sense is not known to generically imply other related primitives with security against adaptive-id adversaries, not even IND-ID-CPA secure encryption. Our first contribution is to define a new security property for (H)IB-TDFs. We show that functions satisfying this property imply secure cryptographic primitives in the adaptive identity-based setting: these include encryption schemes with semantic security under chosen-plaintext attacks, deterministic encryption schemes, and (non-adaptive) hedged encryption schemes that maintain some security when messages are encrypted using randomness of poor quality. We emphasize that some of these primitives were unrealized in the (H)IB setting previous to this work. As a second contribution, we describe the first pairing-based HIB-TDF realization. This is also the first example of hierarchical trapdoor function based on traditional number theoretic assumptions: so far, constructions were only known under lattice assumptions. Our HIB-TDF construction is based on techniques that differ from those of Bellare et al. in that it uses a hierarchical predicate encryption scheme as a key ingredient. The resulting HIB-TDF is proved to satisfy the new security definition, against either selective or, for hierarchies of constant depth, adaptive adversaries. In either case, we only need the underlying predicate encryption system to be selectively secure.

Introduction

(Identity-Based) Lossy Trapdoor Functions

Lossy trapdoor functions, as introduced by Peikert and Waters in [START_REF] Peikert | Lossy trapdoor functions and their applications[END_REF], have been proved very powerful in theoretical cryptography and received a lot of attention in the recent years (see, e.g., [START_REF] Freeman | More Constructions of Lossy and Correlation-Secure Trapdoor Functions[END_REF][START_REF] Hemenway | Lossy Trapdoor Functions from Smooth Homomorphic Hash Proof Systems[END_REF][START_REF] Mol | Chosen-Ciphertext Security from Slightly Lossy Trapdoor Functions[END_REF][START_REF] Boyen | Shrinking the Keys of Discrete-Log-Type Lossy Trapdoor Functions[END_REF][START_REF] Hofheinz | All-But-Many Lossy Trapdoor Functions[END_REF][START_REF] Wee | Dual Projective Hashing and its Applications -Lossy Trapdoor Functions and More[END_REF]). Roughly speaking, a lossy trapdoor function is a family of functions that can be instantiated in two different modes. In the injective mode, the function is injective and can be inverted using the corresponding trapdoor. In lossy mode, the function is (highly) non-injective since its image size is much smaller than the size of the domain. The key point is that lossy instantiations of the function must be indistinguishable from injective instantiations.

In their seminal paper [START_REF] Peikert | Lossy trapdoor functions and their applications[END_REF], Peikert and Waters showed that lossy trapdoor functions provide black-box constructions of chosen-ciphertext secure (IND-CCA) public-key encryption schemes as well as universal one-way and collision-resistant hash functions. Later on, other applications of lossy trapdoor functions were discovered: they gave rise to deterministic encryption schemes [START_REF] Bellare | Deterministic Encryption: Definitional Equivalences and Constructions without Random Oracles[END_REF] in the standard model [START_REF] Boldyreva | On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles[END_REF], public-key encryption hedged schemes maintaining some security in the absence of reliable encryption coins [START_REF] Bellare | Hedged Public-Key Encryption: How to Protect against Bad Randomness[END_REF] and even public-key encryption with selective-opening security [START_REF] Bellare | Possibility and Impossibility Results for Encryption and Commitment Secure under Selective Opening[END_REF] (i.e., which offer certain security guarantees in case of sender corruption).

Recently, Bellare, Kiltz, Peikert and Waters [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF] introduced the notion of identity-based (lossy) trapdoor function (IB-TDF), which is the analogue of lossy trapdoor functions in the setting of identity-based cryptography [START_REF] Shamir | Identity-Based Cryptosystems and Signature Schemes[END_REF]. In the identity-based scenario, users' public keys are directly derived from their identities, whereas secret keys are delivered by a trusted master entity. In this way, the need for digital certificates, which usually bind public keys to users in traditional publickey cryptography, is drastically reduced. Throughout the last decade, several generalizations of identity-based cryptography were put forth, including hierarchical identity-based cryptography [START_REF] Gentry | Hierarchical ID-Based Cryptography[END_REF], attribute-based cryptography [START_REF] Sahai | Fuzzy Identity-Based Encryption In Eurocrypt'05[END_REF][START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF] or predicate-based cryptography [START_REF] Boneh | Conjunctive, Subset, and Range Queries on Encrypted Data[END_REF][START_REF] Katz | Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products[END_REF]. In the setting of hierarchical identity-based cryptography, identities are organized in a hierarchical way, so that a user who holds the secret key of an identity id can generate, use and distribute valid secret keys for any identity that is a descendant of id in the hierarchy. Hierarchical identity-based encryption (HIBE) is of great interest due to both practical and theoretical reasons. On the practical side, many organizations and systems that may need (identity-based) cryptographic solutions are organized in a hierarchical way. On the theoretical side, generic constructions [START_REF] Canetti | A Forward-Secure Public-Key Encryption Scheme[END_REF][START_REF] Canetti | Chosen-Ciphertext Security from Identity-Based Encryption[END_REF] are known to transform a weakly secure HIBE scheme (i.e., IND-CPA security against selective adversaries) into (public-key) encryption schemes with strong security properties, like chosen-ciphertext security [START_REF] Canetti | Chosen-Ciphertext Security from Identity-Based Encryption[END_REF] or forwardsecurity [START_REF] Anderson | Two Remarks on Public Key Cryptology[END_REF][START_REF] Canetti | A Forward-Secure Public-Key Encryption Scheme[END_REF], where private keys are updated in such a way that past encryptions remain safe after a private key exposure.

Bellare et al. [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF] proposed instantiations of identity-based lossy trapdoor functions based on bilinear maps and on lattices (as noted in [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF], almost all IBE schemes belong to these families). The former makes clever use of an anonymous IBE system (where the ciphertext hides the receiver's identity) with pseudorandom ciphertexts whereas the latter relies on lossiness properties of learningwith-error-based cryptosystems. Moreover, they show that their definition of partial-lossiness for identity-based trapdoor functions leads to the same cryptographic results as lossy trapdoor functions, but in the selective identity-based setting only, where the attacker must choose the target identity upfront in the attack game. Namely, in the case of selective adversaries, IB-TDFs satisfying their definition imply identity-based encryption with semantic security, identity-based deterministic encryption and identity-based hedged encryption. In [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF], it was left as an open problem to prove that the same results hold in the case of adaptive adversaries.

Our Contributions

This paper extends to the hierarchical setting the notion of identity-based (lossy) trapdoor function.

New Definition of Partial Lossiness. From a theoretical standpoint, we first define a new security property for hierarchical identity-based trapdoor functions (HIB-TDFs). We show that a HIB-TDF which satisfies this property can be used to obtain the same kind of results that are derived from standard lossy trapdoor functions [START_REF] Peikert | Lossy trapdoor functions and their applications[END_REF]. Namely, they lead to standard encryption schemes, to deterministic encryption schemes, and to non-adaptive hedged encryption schemes, which are secure in the hierarchical identity-based setting, in front of adaptive-id adversaries. Since HIB-TDFs contain IB-TDFs as a particular case, our results for adaptive adversaries solve an open problem in [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF]. Interestingly, the pairing-based IB-TDF of Bellare et al. [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF] can be proved to also satisfy the new security property. As a consequence, it provides adaptively secure deterministic and hedged IBE schemes. Recently, Xie et al. [START_REF] Xie | Deterministic Public Key Encryption and Identity-Based Encryption from Lattices in the Auxiliary-Input Setting[END_REF] designed an adaptively secure D-IBE system using lattices. The construction of [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF] is thus the first adaptively secure pairing-based realization.

Construction of a Pairing-Based Hierarchical Trapdoor Function. On the constructive side, we focus on pairing-based systems where, as already mentioned in [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF], greater challenges are faced. Indeed, in the hierarchical scenario, anonymity -which was used as an important ingredient by Bellare et al. [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF] -has been significantly harder to obtain in the world of bilinear maps than with lattices [START_REF] Cash | Bonsai Trees, or How to Delegate a Lattice Basis[END_REF][START_REF] Agrawal | Efficient Lattice (H)IBE in the Standard Model[END_REF][START_REF] Agrawal | Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE[END_REF]: for example, the first pairing-based anonymous HIBE system [START_REF] Boyen | Anonymous Hierarchical Identity-Based Encryption (Without Random Oracles)[END_REF] appeared four years after the first collusion-resistant HIBE [START_REF] Gentry | Hierarchical ID-Based Cryptography[END_REF]. Moreover, very few anonymous IBE systems seem amenable for constructing IB-TDFs, as noted in [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF] where a new scheme was specially designed for this purpose.

Using bilinear maps, we thus construct a HIB-TDF and prove that it satisfies our new definition of partial lossiness under mild hardness assumptions in groups of prime order. As an intermediate step, we design a hierarchical predicate encryption (HPE) system [START_REF] Shi | Delegating Capabilities in Predicate Encryption Systems[END_REF][START_REF] Okamoto | Hierarchical Predicate Encryption for Inner-Products[END_REF] with suitable anonymity properties, which may be of independent interest. Perhaps surprisingly, although this scheme is proved secure only against weak selective adversaries (who select their target attribute set before seeing the public parameters), we are able to turn it into a HIB-TDF providing security (namely, our new version of partial lossiness) against adaptive adversaries for hierarchies of constant depth. To the best of our knowledge, our HIB-TDF gives rise to the first hierarchy of trapdoor functions which does not rely on lattices: realizing such a hierarchy using traditional number theoretic techniques was identified as an open problem by Cash et al. [START_REF] Cash | Bonsai Trees, or How to Delegate a Lattice Basis[END_REF].

Beyond its hierarchical nature, our construction brings out an alternative design principle for (H)IB-TDFs. The idea is to rely on hierarchical predicate encryption (HPE) to deal with hierarchies. Namely, public parameters consist of a matrix of HPE encryptions and, when the function has to be evaluated, the latter matrix is turned into a matrix of (anonymous) HIBE ciphertexts. The homomorphic properties of the underlying HIBE then make it possible to evaluate the function while guaranteeing a sufficient amount of lossiness in lossy mode.

While the pairing-based construction of Bellare et al. [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF] builds on an adaptively secure anonymous IBE, our (hierarchical) IB-TDF is obtained from a selectively weakly attribute-hiding HPE system. This result is somewhat incomparable with [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF]: on one hand, we start from a more powerful primitive -because predicate encryption implies anonymous IBE -but, on the other hand, we need a weaker security level to begin with. Both (H)IB-TDF constructions rely on specific algebraic properties in the underlying IBE/HPE and neither is generic. It would be interesting to see if a more general approach exists for building such functions.

Discussion on the Implications

Combining our HIB-TDF with the theoretical implications of our new security property, we obtain: (1) a semantically secure HIBE encryption scheme under adaptive adversaries, (2) the first secure deterministic HIBE scheme4 , (3) the first HIBE scheme that (non-adaptively) hedges against bad randomness, as advocated by Bellare et al. [START_REF] Bellare | Hedged Public-Key Encryption: How to Protect against Bad Randomness[END_REF].

In the case of adaptive adversaries, these results only hold for hierarchies of constant depth (said otherwise, we do not provide full security). However, using our definition of partial lossiness or that of Bellare et al. [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF], this appears very difficult to avoid. The reason is that both definitions seem inherently bound to the partitioning paradigm. Namely, they assume the existence of alternative public parameters, called lossy parameters, where the identity space is partitioned into subsets of injective and lossy identities. The definition of [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF] intuitively captures that a fraction δ of identities are lossy in the case of lossy parameters. In the hierarchical setting, the analogy with HIBE schemes suggests that all ancestors of a lossy identity be lossy themselves. Hence, unless one can make sure that certain lossy identities only have lossy descendants, the fraction δ seems doomed to exponentially decline with the depth of the hierarchy.

Finally, due to the results of Canetti, Halevi and Katz [START_REF] Canetti | A Forward-Secure Public-Key Encryption Scheme[END_REF], our construction also implies the first forward-secure deterministic and hedged public-key encryption schemes (note that selective security suffices to give forward-secure public-key cryptosystems). Although our scheme is not practical due to very large ciphertexts and key sizes, it provides the first feasibility results in these directions.

Hierarchical Identity-Based (Lossy) Trapdoor Functions, and Applications

In this section we extend to the hierarchical scenario the definitions for identity-based (lossy) trapdoor functions given in [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF].

Syntax. A hierarchical identity-based trapdoor function (HIB-TDF) is a tuple of efficient algorithms HF = (HF.Setup, HF.MKg, HF.Kg, HF.Del, HF.Eval, HF.Inv). The setup algorithm HF.Setup takes as input a security parameter ∈ N, the (constant) number of levels in the hierarchy d ∈ N, the length of the identities µ ∈ poly( ) and the length of the function inputs n ∈ poly( ), and outputs a set of global public parameters pms, which specifies an input space InpSp, an identity space IdSp and the necessary mathematical objects and hash functions. The master key generation algorithm HF.MKg takes as input pms and outputs a master public key mpk and a master secret key msk. The key generation algorithm HF.Kg takes as input pms, msk and a hierarchical identity (id 1 , . . . , id ) ∈ IdSp, for some ≥ 1 and outputs a secret key SK (id 1 ,...,id ) . The delegation algorithm HF.Del takes as input pms, msk, a hierarchical identity (id 1 , . . . , id ), a secret key SK (id 1 ,...,id ) for it, and an additional identity id +1 ; the output is a secret key SK (id 1 ,...,id ,id +1 ) for the hierarchical identity (id 1 , . . . , id , id +1 ) iff (id 1 , . . . , id , id +1 ) ∈ IdSp. The evaluation algorithm HF.Eval takes as input pms, msk, an identity id = (id 1 , . . . , id ) and a value X ∈ InpSp; the result of the evaluation is denoted as C. Finally, the inversion algorithm HF.Inv takes as input pms, msk, a hierarchical identity id = (id 1 , . . . , id ), a secret key SK id for it and an evaluation C, and outputs a value X ∈ InpSp.

A HIB-TDF satisfies the property of correctness if

(f ) = {f (x) : x ∈ Dom(f )}, we say that f is ω-lossy if λ(f ) ≥ ω, where λ(f ) = log |Dom(f )| |Im(f )| .
To properly define lossiness in the IB setting, it will also be useful to consider extended HIB-TDFs, which differ from standard HIB-TDFs in that, in the latter, the algorithm HF.Setup specifies in pms an auxiliary input space AuxSp, and HF.MKg takes as additional auxiliary input aux ∈ AuxSp. Also, given some HIB-TDF HF = (HF.Setup, HF.MKg, HF.Kg, HF.Del, HF.Eval, HF.Inv), a sibling for HF is an extended HIB-TDF LHF = (HF.Setup, LHF.MKg, LHF.Kg, HF.Del, HF.Eval, HF.Inv) whose delegation, evaluation and inversion algorithms are those of HF, and where an auxiliary space AuxSp is contained in pms ← HF.Setup( ), so that IdSp ⊂ AuxSp.

Looking ahead, we will define, as in [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF], two different experiments: one corresponding to the standard setup and one corresponding to the lossy setup, in one of them the experiment will interact with a standard HIB-TDF, in the other one with a sibling in which some identities lead to lossy evaluation functions. The notion of extended HIB-TDF will serve to construct both of these functions as an extended HIB-TDF but with different auxiliary inputs y (0) , y (1) .

A New Security Definition for HIB-TDFs

The basic security property of a trapdoor function is one-wayness, which means that the function is hard to invert without the suitable secret key. In the identity-based setting, one-wayness is required to hold even when the adversary has oracle access to the secret keys for some identities. Partial lossiness for identity-based trapdoor functions was introduced in [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF], where it was proved to imply one-wayness. Roughly speaking, partial lossiness requires that the weighted difference of the probability that any adversary outputs 1 in the lossy or in the real setup is negligible. For the selective case, the weights can simply be set to 1 and it can be proved that an IB-TDF satisfying their notion of partial lossiness in the selective scenario can be used to build: (1) identity-based encryption (IBE) schemes with selective IND-CPA security, (2) selectively secure deterministic IBE schemes, (3) selectively secure hedged IBE schemes. However, these results are not known to be true in the adaptive setting, in particular, the definition is not even known to yield an IND-ID-CPA secure encryption scheme.

To address this question, we propose an alternative definition for the partial lossiness of (hierarchical) identity-based trapdoor functions -in particular, they also result in a new definition when the hierarchy depth is equal to 1, the case considered by Bellare et al. [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF]. We will show that a HIB-TDF satisfying this new definition gives a secure construction of the same primitives we mentioned for the selective case.

As in [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF], we define two different experiments, a lossy experiment and a real experiment. For any adversary A against a HIB-TDF, and any ζ ∈ (0, 1), the REAL A HF,LHF,P,ω,ζ experiment and the LOSSY A HF,LHF,P,ω,ζ experiment are parameterized by the security parameter (which we will usually omit in the notation) and values ζ( ), ω( ). The value ζ will be important to show that our construction implies other cryptographic primitives. Intuitively, ζ will be the advantage of an adversary against a cryptographic scheme the security of which is reduced to the security of the HIB-TDF. The experiment also takes as input the specification of some efficient algorithm P which takes as input ζ, pms, mpk 1 , msk 1 , IS, id , and outputs a bit d 2 . This procedure P can be, in general, any probabilistic and polynomial-time algorithm. In the security analysis of the selectively secure version of our HIB-TDF, P will be the trivial algorithm that always outputs d 2 = 1. In other cases, P could be a more complicated algorithm; for instance, in order to prove the security of the adaptive-id version of our HIB-TDF, we will take as pre-output stage P Waters' artificial abort step. Actually, procedure P is a way to relax the security requirements in Denition 1, in order to allow the possibility of building cryptographic schemes from secure HIB-TDFs, in a black-box way.

Finally, the value ω is related to the lossiness of the trapdoor function. To simplify notation, we will simply write REAL instead of REAL A HF,LHF,P,ω,ζ and LOSSY instead of LOSSY A HF,LHF,P,ω,ζ . For compactness, we present the two experiments as a single experiment depending of a bit β: the challenger C, who interacts with the adversary A, runs either REAL if β = 0 or LOSSY if β = 1. Also, some instructions of both experiments depend on whether selective or adaptive security is being considered. We say that a hierarchical identity id = (id 1 , . . . , id ) is a prefix of another one id = (id 1 , . . . , id ) if ≤ and id i = id i for every i = 1, . . . , . We denote it by id ≤ id . 0. C chooses global parameters pms by running HF.Setup. The parameters pms are given to A, who replies by choosing a hierarchical identity id † = (id † 1 , . . . , id † † ), for some † ≤ d. 1. C runs (mpk 0 , msk 0 ) ← HF.MKg(pms) and (mpk 1 , msk 1 ) ← LHF.MKg(pms, aux = id † ). The adversary A receives mpk β and lists IS ← ∅, QS ← ∅ are initialized. 2. A can make adaptive queries for hierarchical identities id = (id 1 , . . . , id ) and identities id +1 .

-Create-key: A provides id and C creates a private key SK id . If β = 0, SK id is created by running HF.Kg(pms, msk 0 , id).

If β = 1,
A ¬abort = d 1 ∧ d 2 ∈ {0, 1}.
For notational convenience, from now on, let us define

d A exp = d A ∧ d A ¬abort .
Note that, in the lossy experiment, some identities may lead to lossy functions, which can be detected by A if it queries the secret key for such an identity. This causes an asymmetry when comparing the real and the lossy experiments. For this reason, Bellare et al. defined the advantage of a distinguisher among the lossy and real experiments as the weighted difference of the probability of outputting 1 in the real case minus the same probability in the lossy case. Our solution is different: we force the experiment to adopt the same behavior in the real and lossy settings: if a query would force the LOSSY experiment to set the bits d 1 or d 2 to 0 (and, as a consequence, setting d A exp = 0), then it also forces the REAL experiment to set d 1 or d 2 to 0, respectively. Therefore, the difference of probabilities in our definition (see condition (i) below) is not weighted. Definition 1. A HIB-TDF is (ω, δ)-partially lossy if it admits a sibling and an efficient pre-output stage P such that for all PPT adversaries A and for all non-negligible ζ, there exist two nonnegligible values 1 , 2 with δ = 1 2 such that the following three conditions hold: (i) the following advantage function is negligible in the security parameter :

Adv lossy HF,LHF,P,ω,ζ (A) = | Pr[d A exp = 1| REAL] -Pr[d A exp = 1| LOSSY]| (1)
(ii) Pr[d A ¬abort = 1 | REAL] ≥ 1 . (iii) if A is such that Pr[d A = 1 | REAL] -1 2 > ζ, then Pr[d A = 1 | REAL ∧ d A ¬abort = 1] - 1 2 > 2 • ζ, (2)
where δ may be a function of q the maximal number of secret key queries of A.

As said above, condition (i) is a simple modification of the definition of partial lossiness of Bellare et al. [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF]. We add condition (ii) to rule out some cases in which the definition would be trivial to satisfy, like the case where the procedure P aborts with overwhelming probability or the case where the sibling admits only lossy identities: in any of these scenarios, we would have d ¬abort = 1 with negligible probability, which would render the scheme useless with the sole condition (i). Then, we add a third condition (iii) which allows reducing HIB-TDFs to other primitives. Roughly speaking, this condition guarantees that the probability of aborting is somewhat independent of the behavior of any computationally bounded adversary. Interestingly, it is possible to prove (by proceeding exactly as in the proof of our HIB-TDF) that the pairing-based IB-TDF described by Bellare et al. [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF] satisfies our new partial-lossiness definition.

Implications of Lossy (H)IB-TDFs: the Example of (H)IBE

Using the same argument as in [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF], it is quite easy to prove that a HIB-TDF which enjoys the new version of the partial lossiness property is already one-way, in both the selective and adaptive settings. In this section we prove that a HIB-TDF which satisfies our new security definition can be used to build other primitives in the hierarchical identity-based security, with security against adaptive adversaries. We detail the example of hierarchical identity-based encryption (HIBE) with IND-CPA security 5 . The construction is the direct adaptation of the Peikert-Waters construction [START_REF] Peikert | Lossy trapdoor functions and their applications[END_REF] in the public-key setting.

Let HF be a HIB-TDF with message space {0, 1} n and lossiness ω, and H a family of pairwise independent hash functions from {0, 1} n to {0, 1} l where l ≤ ω -2 lg(1/ LHL ) for some negligible LHL . The HIBE scheme has message space {0, 1} l . Its setup, key generation and key delegation algorithms are basically the same ones as those for HF, the rest are as follows:

MKGen(pms) Enc(pms, mpk, m, id) Dec(pms, mpk, SK id , C, id) (mpk , msk) ← HF.MKg(1 k ) x ← {0, 1} n x = HF.Inv(pms, mpk, SK id , c 1 , id) h ← H c 1 = HF.Eval(pms, mpk, id, x) m = c 2 ⊕ h(x) mpk = (mpk , h) c 2 = h(x) ⊕ m Return m Return mpk Return C = (c 1 , c 2 )
We prove the following theorem.

Theorem 1. If HF is (ω, δ)-partially lossy for some non-negligible value of δ, then the HIBE scheme Π described is IND-ID-CPA secure. In particular, for every IND-ID-CPA adversary B against Π there exists a PPT adversary A against HF such that

Adv lossy HF,LHF,P,ω,ζ (A) ≥ 2 3 • δ • Adv ind-id-cpa (B) -ν( )
for some negligible function ν; both adversaries A and B run in comparable times.

Proof. Let us assume that an adversary B has advantage at least ζ in breaking the IND-ID-CPA security of the HIBE scheme Π, for some non-negligible ζ. We build an adversary A that breaks the condition (i) of Definition 1 assuming that conditions (ii) and (iii) are satisfied. Our adversary A, who interacts with a challenger that runs either the experiment REAL or the experiment LOSSY, proceeds to simulate the challenger in the IND-ID-CPA game with B as follows.

A forwards an identity id † to its challenger, which is some random identity in the adaptive case or corresponds to the challenge identity chosen by B in the selective case. When the challenger runs the setup and gives the output to A, A forwards this information to B together with a hash function h ← H. When B asks for a secret key for a hierarchical identity id, A forwards the query to the experiment and forwards the reply to B. At some point, B outputs (m 0 , m 1 , id ), with id † = id * in the selective case. Adversary A then forwards id to its challenger, chooses γ ← {0, 1} at random and encrypts m γ under the identity id . After some more secret key queries, B outputs a guess γ and A outputs d A = 1 if γ = γ and d A = 0 otherwise.

In the REAL setting, we will have

Pr[γ = γ| REAL] - 1 2 = Pr[d A = 1| REAL] - 1 2 ≥ ζ,
since A perfectly simulated the IND-ID-CPA game with B. This inequality can be combined with conditions (ii) and (iii) of the definition of (ω, δ)-partial lossiness (which we assume to be satisfied by HF), and we obtain

Pr[d A ¬abort = 1 | REAL] • Pr[d A = 1 | REAL ∧ d A ¬abort = 1] - 1 2 > 1 2 ζ. (3)
On the other hand, as proved in [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF], in the LOSSY setting when id is lossy, the advantage of B in guessing γ is negligible. Indeed, since we are using a pairwise independent hash function, the Leftover Hash Lemma [START_REF] Håstad | A pseudorandom generator from any one-way function[END_REF] (more precisely, its variant proved in [START_REF] Dodis | Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data[END_REF]) implies that the distribution of c 2 given c 1 is statistically close to the uniform distribution. We thus have Pr

[d A = 1| LOSSY ∧ d A ¬abort = 1] ≤ 1 2 + LHL , for some negligible function LHL . Since d A exp = d A ¬abort ∧ d A , we find Pr[d A exp = 1 | LOSSY] = Pr[d A = 1 | LOSSY ∧ d A ¬abort = 1] Pr[d A ¬abort = 1 | LOSSY] ≤ 1 2 + LHL • Pr[d A ¬abort = 1 | LOSSY] ≤ 1 2 • Pr[d A ¬abort = 1 | REAL] + Adv lossy HF,LHF,P,ω,ζ (A) + ν, (4)
for some negligible function ν ∈ negl( ). The last equality follows from the fact that we can assume that Pr

[d A ¬abort = 1| LOSSY]-Pr[d A ¬abort = 1| REAL] ≤
(A) = Pr[d A exp = 1 | REAL] -Pr[d A exp = 1 | LOSSY] ≥ Pr[d A ¬abort = 1 | REAL] • Pr[d A = 1 | REAL ∧ d A ¬abort = 1] - 1 2 (5) - 1 2 • Adv lossy HF,LHF,P,ω,ζ (A) -ν, so that there exists ν ∈ negl( ) such that Adv lossy HF,LHF,P,ω,ζ (A) ≥ 2 3 • Pr[d A ¬abort = 1 | REAL] • Pr[d A = 1 | REAL ∧ d A ¬abort = 1] - 1 2 -ν.
This means that Adv lossy HF,LHF,P,ω,ζ (A) is non-negligible since δ = 1 2 and the right-hand-side member of the above expression is at least (2/3) • δ • ζ -ν. In other words, any adversary guessing γ = γ with non-negligible advantage ζ in REAL necessarily contradicts condition (i).

Interlude: Hierarchical Predicate Encryption

In this section we propose a new hierarchical predicate encryption scheme with the attributehiding property, which will be used as an ingredient to build, in the next section, a hierarchical identity-based (lossy) trapdoor function. The syntax and security model for hierarchical predicate encryption schemes are recalled in Appendix A.1.

Some Complexity Assumptions

We consider groups (G, Ĝ, G T ) of prime order p for which an asymmetric bilinear map e : G × Ĝ → G T is efficiently computable. We will assume that the DDH assumption holds in both G and Ĝ, which implies that no isomorphism is efficiently computable between G and Ĝ. The assumptions that we need are sometimes somewhat stronger than DDH. However, they have constant size (i.e., we de not rely on q-type assumptions) and were previously used in [START_REF] Ducas | Anonymity from Asymmetry: New Constructions for Anonymous HIBE[END_REF].

The Bilinear Diffie Hellman Assumption (BDH): in bilinear groups (G, Ĝ, G T ) of prime order p, the distribution

D 1 = {(g, g a , g c , ĝ, ĝa , ĝb , e(g, ĝ) abc ) | a, b, c R ← Z p }, is computationally indistinguishable from D 2 = {(g, g a , g c , ĝ, ĝa , ĝb , e(g, ĝ) z ) | a, b, c, z R ← Z p }. The P-BDH 1 Assumption: in asymmetric bilinear groups (G, Ĝ, G T ) of prime order p, the dis- tribution D 1 = {(g, g b , g ab , g c , ĝ, ĝa , ĝb , g abc ) | a, b, c R ← Z p } is computationally indistinguishable from D 2 = {(g, g b , g ab , g c , ĝ, ĝa , ĝb , g z ) | a, b, c, z R ← Z p }. The DDH 2 Assumption: in asymmetric bilinear groups (G, Ĝ, G T ) of prime order p, the dis- tribution D 1 = {(g, ĝ, ĝa , ĝb , ĝab ) | a, b R ← Z p } is computationally indistinguishable from the distribution D 2 = {(g, ĝ, ĝa , ĝb , ĝz ) | a, b, z R ← Z p }.

A Selectively Secure Weakly Attribute-Hiding Hierarchical Predicate Encryption Scheme

The construction is inspired by the Shi-Waters delegatable predicate encryption scheme [START_REF] Shi | Delegating Capabilities in Predicate Encryption Systems[END_REF] (at a high-level, it also bears similarities with the lattice-based scheme of [START_REF] Agrawal | Functional Encryption for Inner Product Predicates from Learning with Errors[END_REF]). However, we have to turn it into a predicate encryption scheme for inner product relations (like the one of Okamoto and Takashima [START_REF] Okamoto | Hierarchical Predicate Encryption for Inner-Products[END_REF]) instead of a hidden vector encryption [START_REF] Boneh | Conjunctive, Subset, and Range Queries on Encrypted Data[END_REF]. Another difficulty to solve is that we cannot use composite order groups as in [START_REF] Shi | Delegating Capabilities in Predicate Encryption Systems[END_REF] because, in our HIB-TDF of Section 4, one of the subgroups would eventually leak information on the input in lossy mode (this is actually what happened with our initial attempt). For this reason, we chose to work with prime-order groups and used asymmetric pairing configurations to anonymize ciphertexts. As a benefit, we obtain a better efficiency than by using the techniques of [START_REF] Boneh | Conjunctive, Subset, and Range Queries on Encrypted Data[END_REF] by reducing the number of pairing evaluations.

Setup( , d, µ): given a security parameter ∈ N, the (constant) desired number of levels in the hierarchy d ∈ N and the desired length µ of the attribute vectors at each level, choose asymmetric bilinear groups (G, Ĝ, G T ) of order p, where

p > 2 . Choose g R ← G, ĝ R ← Ĝ. Then, pick α, α v , α w R ← Z *
p and set v = g αv , v = ĝαv , w = g αw and ŵ = ĝαw . For i 1 = 1, . . . , d and

i 2 = 0, . . . , µ, choose α i 1 ,i 2 R ← Z * p and compute h i 1 ,i 2 = g α i 1 ,i 2 ∈ G and ĥi 1 ,i 2 = ĝα i 1 ,i 2 ∈ G .
The master public key is defined to be mpk := v, w, e(g, v) α , {h i 1 ,i 2 } i 1 ∈{1,...,d}, i 2 ∈{0,...,µ} while the master secret key is msk := ĝ, ĝα , v, ŵ, { ĥi 1 ,i 2 } i 1 ∈{1,...,d}, i 2 ∈{0,...,µ} .

Keygen msk, ( X 1 , . . . , X ) : to generate a private key for vectors ( X 1 , . . . , X ) with ≤ d, parse msk as ĝ, v, ŵ, { ĥi 1 ,i 2 } i 1 ∈{1,...,d}, i 2 ∈{0,...,µ} . For i 1 = 1 to , parse

X i 1 as (x i 1 ,1 , . . . , x i 1 ,µ ) ∈ Z µ p . Choose r w R ← Z * p and r 1 , . . . , r R ← Z * p , for i 1 ∈ {1, . . . , }. Then, compute the decryption component SK D = (D, D w , {D i 1 } i 1 =1
) of the key as

D = ĝα • i 1 =1 µ i 2 =1 ĥx i 1 ,i 2 i 1 ,i 2 r i 1 • ŵrw , D w = vrw , D i 1 = vr i 1 .
To define the elements of its delegation component

SK DL {K j,k , L j , L j,k,i 1 , L w,j,k } j∈{ +1,...,d}, k∈{1,...,µ}, i 1 ∈{1,..., } pick s j R ← Z * p , s j,k,i 1 R ← Z * p , s w,j,k R ← Z * p for i 1 ∈ {1, . . . , }, i 2 ∈ {1, .
. . , µ} and set:

K j,k = i 1 =1 µ i 2 =1 ĥx i 1 ,i 2 i 1 ,i 2 s j,k,i 1 • ĥs j j,k • ŵs w,j,k , L j = vs j , L j,k,i 1 = vs j,k,i 1 , L w,j,k = vs w,j,k .
Output the private key SK ( X 1 ,..., X ) = SK D , SK DL .

Delegate mpk, ( X 1 , . . . , X ), SK ( X 1 ,..., X ) , X +1 : parse the key SK ( X 1 ,..., X ) as (SK D , SK DL ). Given, X +1 = (x +1,1 , . . . , x +1,µ ) ∈ Z µ p , do the following. 1. Randomize SK DL by raising all its component to some z R ← Z * p . Call this new key SK DL and write its elements with a hat (e.g., K j,k = K z j,k ).

Compute a partial decryption key

K +1 = µ k=1 K x +1,k +1,k = i 1 =1 ( µ i 2 =1 ĥx i 1 ,i 2 i 1 ,i 2 ) s +1,i 1 • µ k=1 ĥx +1,k +1,k s +1 • ŵs w, +1 , L +1, +1 = L +1 , L +1,i 1 = µ k=1 L x +1,k +1,k,i 1 = vs +1,i 1 for i 1 ∈ {1, . . . , }, L w, +1 = µ k=1 L x +1,k w, +1,k = vs w, +1
where we define the exponents s

+1,i 1 = z • µ k=1 s +1,k,i 1 • x +1,k for i 1 ∈ {1, . . . , }, and s w, +1 = z • µ k=1 s w, +1,k • x +1,k . 3.
For all j ∈ { + 2, . . . , d}, k ∈ {1, . . . , µ}, compute re-randomized versions of the partial decryption key by raising the partial decryption key to a random power τ j,k

R ← Z * p . K (j,k) +1 = K τ j,k +1 , L (j,k) w, +1 = L τ j,k w, +1 , {L (j,k) +1,i 1 = L τ j,k +1,i 1 } +1 i 1 =1 .
These values will be used to compute the delegation component of the new key at step 5.

Compute a decryption component SK

D = (D , D w , {D i 1 } +1 i 1 =1
) for the delegated key by setting

D = D • K +1 , D w = D w • L w, +1 . Then, define D +1 = L +1, +1 and, for each i 1 ∈ {1, . . . , }, set D i 1 = D i 1 • L +1,i 1 .
5. Compute a delegation component for the delegated key. For each j ∈ { + 2, . . . , d}, set L j = L j . Then, for k = 1 to µ and i 1 = 1 to + 1, set

K j,k = K j,k • K (j,k) +1 , L w,j,k = L w,j,k • L (j,k) w, +1 L j,k,i 1 = L j,k,i 1 • L (j,k) +1,i 1 ,
where L j,k, +1 = 1 for all j, k. The new delegation component SK DL is

{K j,k , L j , L j,k,i 1 , L w,j,k } j∈{ +2,...,
C 0 = M • e(g, v) α•s , C v = v s , C w = w s , {C i 1 ,i 2 = h y i 1 ,i 2 i 1 ,0 • h i 1 ,i 2 s } i 1 ∈{1,...,κ}, i 2 ∈{1,...,µ} , The ciphertext is C = C 0 , C v , C w , {C i 1 ,i 2 } i 1 ∈{1,...,κ}, i 2 ∈{1,...,µ} .
Decrypt mpk, ( X 1 , . . . , X ), SK ( X 1 ,..., X ) , C : parse the private key SK ( X 1 ,..., X ) as SK D , SK DL ,

where

SK D = (D, D w , {D i 1 } i 1 =1 ) and the ciphertext C as C 0 , C v , C w , {C i 1 ,i 2 } i 1 ∈{1,...,κ}, i 2 ∈{1,...,µ} . 1. For each i 1 ∈ {1, . . . , }, compute C i 1 = µ i 2 =1 C x i 1 ,i 2 i 1 ,i 2 = h X i 1 • Y i 1 i 1 ,0 • µ i 2 =1 h x i 1 ,i 2 i 1 ,i 2 s . 2. Return M if M = C 0 •e(C v , D) -1 •e(C w , D w )• i 1 =1 e(C i 1 , D i 1 ) is in the appropriate subspace 7 of G T . Otherwise, return ⊥.
We show that our scheme is correct in Appendix A.2. Our HIB-TDF uses the predicate-only variant of the above scheme, obtained by discarding the ciphertext component C 0 (which contains the payload) and the factor ĝα from the private key component D.

We remark that the number of pairing evaluations only depends on the depth of the predicate ( X 1 , . . . , X ) encoded in the private key and not on the dimension µ of vectors at each level. Except a recent fully secure construction [START_REF] Okamoto | Achieving Short Ciphertexts or Short Secret-Keys for Adaptively Secure General Inner-Product Encryption[END_REF], all previous schemes required O( • µ) pairing evaluations to decrypt. In our HIB-TDF of Section 4, this will make it possible to invert a function admitting n-bit inputs by computing

O( • n) pairings, instead of O( • n • µ).
The new HPE scheme is selectively weakly attribute-hiding under the BDH, P-BDH 1 and DDH 2 assumptions, as established by Theorem 2. The security of its predicate-only variant (which is the one used as a key ingredient in the design of our HIB-TDF) relies only on the latter two assumptions.

Theorem 2. The HPE scheme is selectively weakly attribute-hiding (in the sense of Definition 2 in Appendix A.1) if the BDH, P-BDH 1 and DDH 2 assumptions hold in (G, Ĝ, G T ). (The proof is given in Appendix A.3).

A Hierarchical Identity-Based (Lossy) Trapdoor Function

From the HPE scheme of Section 3.2, our lossy function is obtained by including a n × n matrix of HPE ciphertexts in the master public parameters. As in the DDH-based function of [START_REF] Peikert | Lossy trapdoor functions and their applications[END_REF], each row of the matrix is associated with an encryption exponent, which is re-used throughout the entire row. Each column corresponds to a different set of public parameters in the HPE system.

The HIB-TDF that we construct is actually an extended HIB-TDF, and so the master key generation protocol takes an auxiliary input. Depending on the value of this auxiliary input, we obtain the trapdoor (injective) function or a partially lossy function, used in the security proofs. Actually, all HPE ciphertexts in the above-mentioned matrix correspond to different hierarchical vectors (y 1 , . . . , y d ) ∈ Z d•µ p , depending on the auxiliary input. The selective weak attribute-hiding property of the HPE scheme guarantees that the two setups are computationally indistinguishable.

In order to evaluate a function for some hierarchical identity id = (id 1 , . . . , id ), the first step of the evaluation algorithm computes a transformation on HPE ciphertexts so as to obtain a matrix of HIBE ciphertexts. During this transformation, a set of inner products

{ y i 1 , id i 1 } i 1 =1
is calculated in the exponent in the diagonal entries of the matrix. The transformation provides a n × n matrix (8) of anonymous HIBE ciphertexts that are always well-formed in non-diagonal entries. As for diagonal entries, they contain "perturbed" HIBE ciphertexts: at each level, one ciphertext component contains a perturbation factor of the form y i 1 , id i 1 . In this matrix of HIBE ciphertexts, random encryption exponents are again re-used in all positions at each row.

The function evaluation is then carried out as in [START_REF] Peikert | Lossy trapdoor functions and their applications[END_REF], by computing a matrix-vector product in the exponent and taking advantage of homomorphic properties of the HIBE scheme over the randomness space. The function output can be seen as a set of n anonymous HIBE ciphertextsone for each input bit -which are well-formed ciphertexts if and only if the corresponding input bit is 0 (i.e., if and only if the perturbation factors { y i 1 , id i 1 } i 1 =1 are left out when computing the matrix-vector product in the exponent). The function is thus inverted by testing the well-formedness of each HIBE ciphertext using the private key.

v R ← Z * p , α w R ← (Z * p ) n , and α h R ← (Z * p ) d×(µ+1)×n . Define v = g αv , v = ĝαv , w = g αw ∈ G n and ŵ = ĝαw ∈ Ĝn . Likewise, set up vectors h = g α h ∈ G d×(µ+1)×n
and ĥ = ĝα h ∈ Ĝd×(µ+1)×n . Define

PP core := v, {w[l 1 ]} n l 1 =1 , {h[i 1 , i 2 , l 1 ]} i 1 ∈{1,...,d},i 2 ∈{0,...,µ}, l 1 ∈{1,...,n} 2. For i 1 = 1 to d, parse y i 1 as (y i 1 [1], . . . , y i 1 [µ]) ∈ Z µ p . For l 2 = 1 to n, do the following. a. Choose s[l 2 ] R ← Z * p and compute J[l 2 ] = v s[l 2 ]
as well as

C w [l 2 , l 1 ] = w[l 1 ] s[l 2 ] , C[i 1 , i 2 , l 2 , l 1 ] = h[i 1 , 0, l 1 ] y i 1 [i 2 ]•∆(l 2 ,l 1 ) • h[i 1 , i 2 , l 1 ] s[l 2 ]
for each i 1 ∈ {1, . . . , d}, i 2 ∈ {1, . . . , µ}, l 1 ∈ {1, . . . , n}.

b. Define a n × n matrix {CT[l 2 , l 1 ]} l 2 ,l 1 ∈{1,...,n} of HPE ciphertexts

CT[l 2 , l 1 ] = J[l 2 ], C w [l 2 , l 1 ], {C[i 1 , i 2 , l 2 , l 1 ]} i 1 ∈{1,...,d}, i 2 ∈{1,...,µ} . (6)
The master public key consists of mpk := PP core , {CT[l 2 , l 1 ]} l 2 ,l 1 ∈{1,...,n} while the master secret key is msk := v, ŵ, ĥ . For each l 1 ∈ {1, . . . , n}, it will be convenient to view (PP core , msk) as a vector of HPE master key pairs (mpk

[l 1 ], msk[l 1 ]), with mpk[l 1 ] = v, w[l 1 ], {h[i 1 , i 2 , l 1 ]} i 1 ∈{1,...,d},i 2 ∈{0,...,µ} msk[l 1 ] = v, ŵ[l 1 ], { ĥ[i 1 , i 2 , l 1 ]} i 1 ∈{1,...,d},i 2 ∈{0,...,µ} .
HF.Kg pms, msk, (id 1 , . . . , id ) : to generate a key for an identity (id 1 , . . . , id ) ∈ IdSp, parse msk as v, ŵ, ĥ and id i 1 as

id i 1 [1] . . . id i 1 [µ] for i 1 = 1 to . Choose r w , r 1 , . . . , r R ← (Z * p ) n . For each l 1 ∈ {1, . . . , n}, compute the decryption component SK D = (D, D w , {D i 1 } i 1 =1
) of the key as

D[l 1 ] = i 1 =1 µ i 2 =1 ĥ[i 1 , i 2 , l 1 ] id i 1 [i 2 ] r i 1 [l 1 ] • ŵ[l 1 ] rw[l 1 ] , D w [l 1 ] = vrw[l 1 ] , D i 1 [l 1 ] = vr i 1 [l 1 ] (7)
and the delegation component

SK DL = {K[j, k, l 1 ]} j,k,l 1 , {L[j, l 1 ]} j,l 1 , {L[j, k, i 1 , l 1 ]} j,k,i 1 ,l 1 , {L w [j, k, l 1 ]} j,k,l 1 , with j ∈ { + 1, . . . , d}, k ∈ {1, . . . , µ} and i 1 ∈ {1, . . . , } as K[j, k, l 1 ] = i 1 =1 µ i 2 =1 ĥ[i 1 , i 2 , l 1 ] id i 1 [i 2 ] s[j,k,i 1 ,l 1 ] • ĥ[j, k, l 1 ] s [j,l 1 ] • ŵ[l 1 ] sw[j,k,l 1 ] , L[j, l 1 ] = vs [j,l 1 ] , L[j, k, i 1 , l 1 ] = vs[j,k,i 1 ,l 1 ] and L w [j, k, l 1 ] = vsw[j,k,l 1 ] .
Output SK (id 1 ,...,id ) = SK D , SK DL .

HF.Del pms, mpk, (id 1 , . . . , id ), SK (id 1 ,...,id ) , id +1 : parse SK (id 1 ,...,id ) as a HF private key of the form (SK D , SK DL ), and id +1 as a string id +1 [START_REF] Agrawal | Efficient Lattice (H)IBE in the Standard Model[END_REF] . . . id +1 [µ] ∈ Σ ID .

1. For l 1 = 1 to n, define -th level HPE keys SK (id 1 ,...,id

) [l 1 ] = (SK D [l 1 ], SK DL [l 1 ])
where

SK D [l 1 ] = (D[l 1 ], D w [l 1 ], {D i 1 [l 1 ]} i 1 =1 ) SK DL [l 1 ] = {K[j, k, l 1 ]} j,k , {L[j, l 1 ]} j , {L[j, k, i 1 , l 1 ]} j,k,i 1 , {L w [j, k, l 1 ]} j,k . 2. For l 1 = 1 to n, run Delegate(mpk[l 1 ], (id 1 , . . . , id ), SK (id 1 ,...,id ) [l 1 ], id +1 ) (as specified in Section 3.2) to get SK (id 1 ,...,id ,id +1 ) [l 1 ] = (SK D [l 1 ], SK DL [l 1 ]).
Finally return

{SK (id 1 ,...,id ,id +1 ) [l 1 ]} n l 1 =1 . HF.Eval pms, mpk, (id 1 , . . . , id ), X : Given a n-bit input X = x 1 . . . x n ∈ {0, 1} n , for i 1 = 1 to , parse id i 1 as id i 1 [1] . . . id i 1 [µ].
For l 1 = 1 to n, do the following.

1. For each l 2 ∈ {1, . . . , n}, compute modified HPE ciphertexts by defining

C id [i 1 , l 2 , l 1 ] = µ i 2 =1 C[i 1 , i 2 , l 2 , l 1 ] id i 1 [i 2 ] = h[i 1 , 0, l 1 ] y i 1 ,id i 1 •∆(l 2 ,l 1 ) • µ i 2 =1 h[i 1 , i 2 , l 1 ] id i 1 [i 2 ] s[l 2 ]
for each i 1 ∈ {1, . . . , }, l 1 , l 2 ∈ {1, . . . , n}. The modified ciphertexts are

CT id [l 2 , l 1 ] = J[l 2 ], {CT id [i 1 , l 2 , l 1 ]} i 1 =1 ∈ G +1 . (8)
The resulting {CT id [l 2 , l 1 ]} l 2 ,l 1 ∈{1,...,n} thus form a n × n matrix of anonymous HIBE ciphertexts for the identity id = (id 1 , . . . , id ).

Compute

C id,v = n l 2 =1 J[l 2 ] x l 2 = v s,X , CT id,w [l 1 ] = n l 2 =1 C w [l 2 , l 1 ] x l 2 = w[l 1 ] s,X and CT id [i 1 , l 1 ] = n l 2 =1 C id [i 1 , l 2 , l 1 ] x l 2 = h[i 1 , 0, l 1 ] s[l 1 ]•x l 1 • y i 1 ,id i 1 • µ i 2 =1 h[i 1 , i 2 , l 1 ] id i 1 [i 2 ] s,X (9)
Then, output

C = C id,v , {CT id,w [l 1 ]} n l 1 =1 , {CT id [i 1 , l 1 ]} i 1 ∈{1,..., },l 1 ∈{1,...,n} ∈ G n+1+n× . ( 10
)
HF.Inv pms, mpk, (id 1 , . . . , id ), SK (id 1 ,...,id ) , C : parse the decryption component SK D of the private key as a tuple of the form (D,

D w , D w, {D i 1 } i 1 =1
) and the output C as per [START_REF] Boldyreva | On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles[END_REF]. Then, for

l 1 = 1 to n, set x l 1 = 0 if e(C id,v , D[l 1 ]) • e(CT id,w [l 1 ], D w [l 1 ]) -1 • i 1 =1 e(CT id [i 1 , l 1 ], D i 1 [l 1 ]) -1 = 1 G T . (11)
Otherwise, set x l 1 = 1. Eventually, return X = x 1 . . . x n ∈ {0, 1} n .

From [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF], we notice that, with overwhelming probability, if there exists some i 1 ∈ {1, . . . , d} such that y i 1 , id i 1 = 0, relation [START_REF] Boneh | Conjunctive, Subset, and Range Queries on Encrypted Data[END_REF] is satisfied if and only if x l 1 = 0. Indeed, in this case, the output (10) is distributed as a vector of n Boneh-Boyen HIBE ciphertexts (in their anonymous variant considered in [START_REF] Ducas | Anonymity from Asymmetry: New Constructions for Anonymous HIBE[END_REF]). These ciphertexts correspond to the same encryption exponent s, X and are generated under n distinct master public keys sharing the same component v ∈ G.

When the function is implemented in injective mode, the auxiliary input consists of a vector

y (0) = [(1, 0, . . . , 0)| . . . |(1, 0, . . . , 0)] ∈ Z d•µ
p . Since id i 1 [START_REF] Agrawal | Efficient Lattice (H)IBE in the Standard Model[END_REF] = 1 for each i 1 , this guarantees injectivity since y (0) i 1 , id i 1 = 0 for each i 1 . In the partially lossy mode, we have y i 1 , id i 1 = 0 for each i 1 ∈ {1, . . . , } with non-negligible probability, which leads to high non-injectivity.

Security Analysis

To analyze the security of the scheme (w.r.t. the new definition, in Section 2.1), in both the adaptive and the selective cases, we define two experiments, RL 0 and RL n . In both of them, HF.Setup is run and the public parameters are given to the adversary A. Algorithm HF.MKg is run with auxiliary input y (0) = [(1, 0, . . . , 0)| . . . |(1, 0, . . . , 0)] in RL 0 , and auxiliary input y (1) = [y

(1) 1 | . . . |y (1)
d ] in RL n , where y (1) is produced by an auxiliary input generator Aux(id) taking as input a special hierarchical identity id = (id 1 , . . . , id ). The master public key mpk is given to the A. A can request secret keys for identities id, which will be answered using HF.Kg and HF.Del and will be added to IS, initialized to IS = {∅}. Also, A will output a hierarchical identity id . Finally, A will output a guess d A . Both in RL 0 and RL n , the experiment will halt and output d = 0 if: a) for any id = (id 1 , . . . , id ) ∈ IS we have that y

(1)

i 1 , id i 1 = 0 for each i 1 ∈ {1, . . . , }, or b) if y (1)
i 1 , id i 1 = 0 for some i 1 ∈ {1, . . . , }. If the experiment has not aborted, it will output the bit d = d A . The result in the following lemma will be used to prove that HF enjoys partial lossiness. Lemma 1. Under the P-BDH 1 and DDH 2 assumptions, the experiments RL 0 and RL n return 1 with nearly identical probabilities. Namely, there exist PPT algorithms B 1 and B 2 such that

|Pr[RL 0 ⇒ 1] -Pr[RL n ⇒ 1]| ≤ n • (d • µ + 1) • Adv P-BDH 1 (B 1 ) + q • Adv P-DDH 2 (B 2 ) ,
where q is the number of "Reveal-key" queries made by A.(The proof is in Appendix B.1).

Adaptive-id Security. The details on the security analysis of HF with respect to selective adversaries are given in Appendix B.2. For adaptive security we consider our construction of HF with a restricted identity space, namely taking

Σ ID = {(1, x) : x ∈ {0, 1} µ-1 }. Define a sibling LHF with AuxSp = Z µ•d
p , where the auxiliary input y (1) = [y

(1) 1 | . . . |y (1)
d ], for any i 1 from 1 to d, is defined as

y i 1 R ← {0, . . . , 2q -1}, ξ i 1 R ← {0, . . . , µ + 1}, y (1)
i 1 [1] = y i 1 -2ξ i 1 q, {y (1)
i 1 [i] R ← {0, . . . , 2q -1}} µ i=2 .
The pre-output stage P associated to the scheme HF in the adaptive case will be the artificial abort used in [START_REF] Waters | Efficient Identity-Based Encryption Without Random Oracles[END_REF]: if IS is the set of queried identities (only taking into account "Reveal key" queries) and id is the challenge identity, let E(IS, id ) be the event that the REAL or the LOSSY experiments set d 1 to be 1, and let η(IS, id ) = Pr[E(IS, id )]. We prove in Appendix B.

= {(1, x) : x ∈ {0, 1} µ-1 }, IdSp = Σ (≤d)
ID . Let LHF be the sibling with auxiliary input as above, let the pre-output stage associated to HF be the one specified above. In front of adaptive-id adversaries that make a maximal number of q ≤ p/(2µ) queries, HF is (ω, δ)-partially lossy, for δ = 13/ 32 • (2qµ) d .

Specifically regarding condition (i), for any such adaptive-id adversary A there exist algorithms

B 1 and B 2 such that Adv lossy HF,LHF,ω,ζ (A) ≤ 2n • (d • µ + 1) • Adv P-BDH 1 (B 1 ) + q • Adv P-DDH 2 (B 2 )
, where the running time of B 1 and

B 2 is that of A plus a O(ζ -2 ln(ζ -1 )η -1 low ln(η -1 low )) overhead, with η low = 1/ 2 • (2qµ) d . (The proof is given in Appendix B.4).
The fact that η -1 low depends exponentially on d is what makes our adaptive-id security result valid only for hierarchies of constant depth d. Whether this restriction can be avoided at all is an interesting open question.

Delegate mpk, ( X 1 , . . . , X ), SK ( X 1 ,..., X ) , X +1 : takes in a -th level private key SK ( X 1 ,..., X ) , the corresponding vectors ( X 1 , . . . , X ) and a vector X +1 . It outputs a ( + 1)-th level private key SK ( X 1 ,..., X , X +1 ) .

Correctness mandates that, for any message M and hierarchical vectors ( X 1 , . . . , X ), ( Y 1 , . . . , Y κ ), we have Decrypt mpk, ( X 1 , . . . , X ), SK ( X 1 ,..., X ) , Encrypt(mpk, ( Y 1 , . . . , Y κ , M ) = M whenever the condition f ( X 1 ,..., X ) ( Y 1 , . . . , Y κ ) = 1 is satisfied.

Following [START_REF] Okamoto | Hierarchical Predicate Encryption for Inner-Products[END_REF], we write f ≤ f to express that the predicate vector of f is a prefix of that for f , meaning that f is at least as constraining as f . Definition 2. A Hierarchical Predicate Encryption scheme is selectively weakly attributehiding if no PPT adversary has non-negligible advantage in the following game:

1. The adversary A chooses a format hierarchy ν = (n 1 , d; ν 1 , . . . , ν d ) and vectors

( Y 0 1 , . . . , Y 0 d ), ( Y 1 1 , . . . , Y 1 d ), for some d ≤ d.
The challenger generates a master key pair (msk, mpk) ← Setup( , ν) and mpk is given to A.

2.

A is allowed to make a number of adaptive queries.

-Create-key: A provides a predicate f ∈ F and the challenger creates a private key SK f for f without revealing it to A. -Create-delegated-key: A chooses a private key that was previously created for some predicate f and also specifies another predicate f ≤ f that f is a prefix of. The challenger then computes a delegated key SK f for f without revealing it to A. -Reveal-key: A asks the challenger to give out a previously created key.

For each Reveal-key query ( X 1 , . . . , X ), it is required that

f ( X 1 ,..., X ) ( Y 0 1 , . . . , Y 0 d ) = f ( X 1 ,..., X ) ( Y 1 1 , . . . , Y 1 d ) = 0.

3.

A outputs messages M 0 , M 1 . Then, the challenger chooses β R ← {0, 1} and computes a challenge ciphertext C = Encrypt mpk, ( Y β 1 , . . . , Y β d ), M β , which is sent to A. 4. A makes further private key queries for hierarchical vectors ( X 1 , . . . , X ) under the same restriction as above. 5. A outputs a bit β ∈ {0, 1} and wins if β = β.

A's advantage is quantified as the distance Adv

(A) = | Pr[β = β] -1/2|.
A.2 Correctness of the HIPE scheme Lemma 3. The HIPE scheme of Section 3.2 is correct. Namely, for any message M and any vectors X 1 , . . . , X , Y 1 , . . . , Y κ , we have Decrypt mpk, ( X 1 , . . . , X ), SK ( X 1 ,..., X ) , Encrypt(mpk, ( Y 1 , . . . , Y κ ), M = M whenever f ( X 1 ,..., X ) ( Y 1 , . . . , Y κ ) = 1. This fact does not depend on whether the key SK ( X 1 ,..., X ) was created using Delegate or Keygen.

Proof. Let SK ( X 1 ,..., X ) = SK D , SK DL be obtained by running Keygen msk, ( X 1 , . . . , X ) , where each attribute vector is X i 1 = (x i 1 ,1 , . . . , x i 1 ,µ ) ∈ Z µ p , for each i 1 ∈ {1, . . . , }. Let us write the decryption component of the key as

SK D = (D, D w , {D i 1 } i 1 =1 ). Let C = C 0 , C v , C w , {C i 1 ,i 2 } i 1 ∈{1,...,κ}, i 2 ∈{1,.
..,µ} be the output of the encryption algorithm Encrypt mpk, ( Y 1 , . . . , Y κ ), M , for vectors Y 1 = (y 1,1 , . . . , y 1,µ ), . . . , Y κ = (y κ,1 , . . . , y κ,µ ).

Since f ( X 1 ,..., X ) ( Y 1 , . . . , Y κ ) = 1, and by the definition of hierarchical inner-product predicates, we know that ≤ κ and X i • Y i = 0 for all i ∈ {1, . . . , }. Therefore, when the decryption protocol Decrypt mpk, ( X 1 , . . . , X ), SK ( X 1 ,..., X ) , C computes C i 1 , for each i 1 ∈ {1, . . . , }, the obtained value equals

C i 1 = µ i 2 =1 h x i 1 ,i 2 i 1 ,i 2
s . The decryption protocol computes then the pairing of this element C i 1 with D i 1 = vr i 1 . Multiplying all these pairings, for indices i 1 ∈ {1, . . . , }, one obtains e v s ,

i 1 =1 µ i 2 =1 ĥx i 1 ,i 2 i 1 ,i 2 r i 1 .
This value is canceled out with one of the factors of e(C v , D), when computing the final decryption operation

C 0 • e(C v , D) -1 • e(C w , D w ) • i 1 =1 e(C i 1 , D i 1 )
. The other two factors of e(C v , D) are e(v s , ĝα ) and e(v s , ŵrw ), which cancel out the factor e(g, v) αs , contained in C 0 = M • e(g, v) αs , and the factor e(C w , D w ) = e(w s , vrw ), respectively. Therefore, the final computation of the decryption protocol results in the plaintext M contained in C 0 .

In this way, we have proved that the encryption and decryption protocols work correctly when the original secret keys (resulting from Keygen) are used. The fact that the decryption protocol works fine also with delegated secret keys (resulting from Delegate) is a consequence of Lemma 4, inside the proof of Theorem 2. If a delegated secret key could lead to an incorrect decryption, then this fact could be used to distinguish original secret keys from delegated ones, which would contradict the statement of Lemma 4.

A.3 Proof of Theorem 2

The proof considers a sequence of games starting with the real game and ending with a game where the adversary has no advantage and wins with probability exactly 1/2.

For each i, we denote by S i the event that the adversary wins in Game i . In the whole sequence of games, we call d the depth of the challenge hierarchical vectors ( Y 0 1 , . . . , Y 0 d ) and ( Y 1 1 , . . . , Y 1 d ) and

C = C 0 , C v , C w , {C i 1 ,i 2 } i 1 ∈{1,...,d },i 2 ∈{1,...,µ}
denotes the challenge ciphertext.

Game 0 : is the real attack game at the end of which the challenger outputs 1 in the event, called S 0 , that the adversary A manages to output β ∈ {0, 1} such that β = β, where β ∈ {0, 1} is the challenger's hidden bit in the challenge phase. If β = β, the challenger outputs 0. Game 1 : is identical to Game 0 with the difference that the challenger always answers private key queries by returning fresh private keys (i.e., keys produced by Keygen) instead of deriving those keys using the delegation algorithm.

Game 2 : is like Game 1 but the challenge ciphertext C is now an encryption under ( Y β 1 , . . . , Y β d ) of a random plaintext M R ← G T ,
which is chosen independently of M 0 and M 1 . Game 3 : is identical to Game 2 with the difference that, in the challenge ciphertext, C w is replaced by a random group element chosen uniformly and independently in G. Game 4,i,j (1 ≤ i ≤ d , 1 ≤ j ≤ µ): is identical to Game 3 with the difference that, in the challenge ciphertext, C i 1 ,i 2 are replaced by random elements of G if i 1 < i or (i = i 1 ) ∧ (i 2 ≤ j). Other group elements (i.e., for which i > i 1 or (i = i 1 ) ∧ (i 2 > j)) are still computed as in a normal challenge ciphertext.

In Game 4,d ,µ , it is easy to see that the adversary A cannot guess β ∈ {0, 1} with higher probability than Pr[S 4,d ,µ ] = 1/2 since the challenge ciphertext C is completely independent of β ∈ {0, 1}.

Lemma 4. Game 0 and Game 1 are computationally indistinguishable if the DDH 2 assumption holds in (G, Ĝ).

Proof. The lemma will be proved by a hybrid argument. We define Game 0,i for all 0 ≤ i ≤ q. Game 0,i differs from Game 0 in the fact that, when the adversary issues the first i delegation queries, instead of generating the delegated keys faithfully using the Delegate algorithm, the challenger calls the Keygen algorithm to generate these delegated keys. For all the remaining queries, the challenger computes keys and responds faithfully as in Game 0 . Under the above definition, Game 0,0 is the same as Game 0 and Game 0,q is the same as Game 1 . We will prove that Game 0,κ is indistinguishable from Game 0,κ+1 for all 0 ≤ κ ≤ q -1. To this end, we will proceed similarly to [START_REF] Shi | Delegating Capabilities in Predicate Encryption Systems[END_REF] and rely on a generalized version (called GDDH hereafter) of the DDH problem in Ĝ. Given a group generator GG, define the following distribution P ( ):

p, (G, Ĝ, G T ), e R ← -GG( , 1), g R ← -G, ĝ R ← -Ĝ, ĥ1 , ĥ2 , . . . , ĥ R ← - Ĝ τ R ← -Z p X ← p, (G, Ĝ, G T
), e , g, ĝ, ĥ1 , ĥ2 , . . . , ĥ

Q ← ĥτ 1 , ĥτ 2 , . . . , ĥτ , Output (X, Q)
For an algorithm A, define A's advantage in solving the above problem:

-GDDH Adv GG,A ( ) := |Pr [A(X, Q) = 1] -Pr [A(X, R)]|
where (X, Q) ← P ( ) and R ← Ĝ . It is immediate 8 that GDDH is not easier than DDH 2 and that the latter advantage function is negligible if the DDH 2 assumption holds in (G, Ĝ).

To prove that Game 0,κ is indistinguishable from Game 0,κ+1 we will use another hybrid argument. We define Game 0,κ , which differs from Game 0,κ in that, for the (κ + 1)-th delegation query, SK DL is the delegation component of a fresh key, instead of a delegation component obtained by raising every element in SK DL to the same random power z ∈ R Z p . We show that a PPT adversary cannot distinguish between the two games.

We also define Game 0,κ , which differs from Game 0,κ in that, for the (κ + 1)-th delegation query, instead of re-randomizing the components of the partial decryption key with the same exponent

τ j.k , {L (j,k) +1,i 1 } +1 i 1 =1 , L (j,k)
w, +1 are randomized with different independently chosen exponents, while K j,k is chosen in such a way that the resulting key is still valid. We also prove that no PPT adversary can notice the difference. 8 The straightforward reduction computes a GDDH instance from a DDH2 instance g, ĝ, ĝa , ĝb , η ? = ĝab by setting ĥi = ĝα i • (ĝ b ) β i and Qi = (ĝ a ) α i • ηβ i for i = 1 to with α1, . . . , α R ← Zp, β1, . . . , β R ← Zp. If η = ĝab , we have Q = ( ĥa 1 , . . . , ĥa ) whereas, if η ∈R Ĝ, Q is a random vector of Ĝ .

We will argue that Game 0,κ =Game 0,κ+1 . Indeed, in the first step, we change SK DL so that, in step 2 of the Delegate algorithm, we obtain a randomized decryption key (except for the g α term). When multiplied by SK D , it gives a randomized decryption key for ( X 1 , . . . , X +1 ). On the other hand, in step 2 of the hybrid proof we change the partial decryption keys so that they also are randomized keys except the g α term.

Claim. Game 0,κ is computationally indistinguishable from Game 0,κ .

Proof. Let q 0 denote the maximum number of secret key queries (taking into account both the "Create-key" and "Create-delegated-key" queries) made by the adversary. We build a simulator B that uses A to break the following (q 0 dµ(d + 1))-GDDH assumption.

(p, G, Ĝ, G T , e) R ← -GG( , 1), g R ← -G, ĝ R ← - Ĝ {v i,i 1 ,i 2 ,k ← Ĝ} i∈{1,...,q 0 },i 1 ∈{1,...,d},i 2 ∈{0,...,µ},k∈{1,...,d+1} τ R ← -Z p X ← (p, G, Ĝ, G T , e), g, ĝ, {v i,i 1 ,i 2 ,k } i∈{1,.
..,q 0 },i 1 ∈{1,...,d},i 2 ∈{1,...,µ},k∈{1,...,d+1} Q ← ({v τ i,i 1 ,i 2 ,k } i∈{1,...,q 0 },i 1 ∈{1,...,d},i 2 ∈{1,...,µ},k∈{1,...,d+1} )

Then, the challenger randomly decides to give (X,

Q = Q) or (X, Q = R),
where R is a random vector of elements in Ĝ of the size of Q. The simulator will use A as a subroutine to break the above problem.

Init and Setup. At the beginning of the security game, the adversary commits to two hierarchical vectors ( Y 1 0 , . . . , Y 0 d ) and ( Y 1 1 , . . . , Y 1 d ), where d ≤ d. The simulator chooses the public and the secret key as usual according to the Setup algorithm. Let c = log v (w) and a i 1 ,i 2 = log v (h i 1 ,i 2 ). Note that these values are known to the simulator since they are easily computable from msk.

Secret key queries. We distinguish three cases:

• When a "create-key" query or one of the first κ delegated secret key queries is made, the simulator computes and saves a private key, which is given to A when a "reveal-key" query is made. To compute this secret key, the simulator uses the elements from the GDDH instance, in such a way that the exponents are distributed at random. In particular, if it is the i-th query, the simulator defines the components of the decryption component of the key as:

D = g α i 1 =1 D ( µ i 2 =1 a i 1 ,i 2 x i 1 ,i 2 ) i 1 • D c w , D w = vi,0,1,d+1 , D i 1 = vi,0,1,i 1 i 1 ∈ {1, . . . , }.
For the delegation component of the key, for all j ∈ { +1 . . . d}, all k ∈ {1, . . . , µ}, the simulator lets:

L j = vi,j,1, +1 , L j,k,i 1 = vi,j,k,i 1 i 1 ∈ {1, . . . , }, L w,j,k = vi,j,k,d+1 .
As the simulator knows the discrete logarithms c = log v( ŵ) and a i 1 ,i 2 = log v( ĥi 1 ,i 2 ), for each j ∈ { + 1, . . . d} and all k ∈ {1, . . . , µ}, it can compute the remaining components of the key as follows:

K j,k = i 1 =1 L ( k i 2 =1 a i 1 ,i 2 •x i 1 ,i 2 ) j,k,i 1 • L a j,k j • L c w,j,k . (12)
• When the adversary makes the (κ + 1)-th delegation query, it specifies a parent key and asks to fix the level of the hierarchy to some vector X +1 . In particular, assume that the parent key was created in the i-th query. When performing Step 1 of the Delegate algorithm, for all j ∈ { + 2, . . . d}, k ∈ {1, . . . , µ}, the simulator sets

L j = Q i,j,1, +1 , L j,k,i 1 = Q i,j,k,i 1 i 1 ∈ {1, . . . , }, L w,j,k = Q i,j,k,d+1
and computes K j,k , for each j ∈ { + 2, . . . d}, k ∈ {1, . . . , µ} exactly in the same way as in expression [START_REF] Boyen | Anonymous Hierarchical Identity-Based Encryption (Without Random Oracles)[END_REF]. • For all the remaining queries, the simulator responds faithfully as in the real game.

Clearly, if Q = Q in the GDDH instance, then the above simulation is identical to Game 0,κ . Otherwise, it is identical to Game 0,κ since, in the the (κ + 1)-th delegation query, Q = R implicitly defines a set of fresh random values for s j , s j,k,i 1 , s w,j,k , for the appropriate values of j, k, i 1 .

Challenge The simulator generates the challenge ciphertext as normal.

Guess If the adversary has a difference of in its advantage in Game 0,κ and Game 0,κ , the simulator has a comparable advantage in solving the GDDH instance.

Claim. Game 0,κ is computationally indistinguishable from Game 0,κ .

Proof. To prove this claim, we will appeal to a nested hybrid argument. Let Game 0,κ,0,0 =Game 0,κ , and for 1 ≤ η ≤ (d--1), 1 ≤ ν ≤ µ, define Game 0,κ,η,ν as the game that differs from Game 0,κ in the following: in the step of the delegation algorithm where the components {L

(j,k) +1,i 1 } i 1 ∈{1,..., +1} , L (j,k) w, +1
are created by re-randomizing the partial decryption key with some exponent τ j,k , we re-randomize instead each of these components with a different exponent chosen uniformly and independently at random whenever (j, k) ≤ (η + + 1, ν) (in lexicographic order). Observe that, by definition, Game 0,κ,d--1,µ =Game 0,κ . We will show that an adversary cannot distinguish between one game and the next. That is, if we define and Game 0,κ,η,µ+1 =Game 0,κ,η+1,0 to simplify the notation, what we we will show is that no polynomial time adversary can distinguish between Game 0,κ,η,ν and Game 0,κ,η,ν+1 . The simulator tries to solve the following (µ(d + 1))-GDDH instance.

(p, G, Ĝ, G T , e) R ← -GG( , 1), g R ← -G, ĝ R ← - Ĝ {v i,k ← Ĝ} i∈{1,...,µ},k∈{1,...,d+1} τ R ← -Z p X ← ((n, G, Ĝ, G T , e), g, ĝ, {v i,k } i∈{1,...,µ},k∈{1,...,d+1} ) Q ← ({v τ i,k } i∈{1,...,µ},k∈{1,...,d+1} )
The simulator tries to distinguish between (X, Q = Q) and (X, Q = R) where R is a random vector from Ĝ. The simulator uses as a subroutine an adversary A who can distinguish between Game 0,κ,η,ν and Game 0,κ,η,ν+1 .

The simulator runs the Setup algorithm as usual in such a way that it knows the discrete logarithms c = log v (w) = log v( ŵ) and

a i 1 i 2 = log v (h i 1 ,i 2 ) = log v( ĥi 1 ,i 2 ) for any 1 ≤ i 1 ≤ d, 0 ≤ i 2 ≤ µ.
To answer secret key queries, the simulator proceeds as follows:

• For the first κ-th delegation queries and all of the "create-key" queries, the simulator computes the keys freshly at random. • At the (κ + 1)-th delegation query, the adversary specifies a parent key and requests to fix the ( + 1)-th level of the hierarchy to X +1 . To answer this query, the simulator first generates some components of SK DL simply by choosing at random the values L j , L w,j,k for all j ∈ { + 2, . . . , d}, k ∈ {1, . . . , µ}, i 1 ∈ {1, . . . , }. To compute the remaining components and the decryption key component, the simulator sets

L +1,i 1 = µ k=1 L x +1,k +1,k,i 1 = µ k=1 (v k,i 1 ) x +1,k i 1 ∈ {1, . . . , } L +1, +1 = L +1 = v1, +1 L w, +1 = µ k=1 L x +1,k w, +1,k = µ k=1 (v k,d+1 ) x +1,k .
Since the simulator knows the discrete logarithms c = log v( ŵ) and a i 1 ,i 2 = log v( ĥi 1 ,i 2 ), the remaining components of SK DL and those of the partial decryption key can be generated efficiently in the same way as in the proof of indistinguishability of Game 0,κ and Game 0,κ . In particular, the simulator can compute

K +1 = i 1 =1 µ i 2 =1 L a i 1 ,i 2 +1,i 1 • L µ k=1 a +1,k +1, +1 • L c w, +1 . To create K (j,k) +1 , {L (j,k) +1,i 1 } i 1 ∈{1,..., +1} , L (j,k)
w, +1 , if (j, k) ≤ (η + + 1, ν) (in lexicographic order), the values are chosen as fresh random delegation keys. For the (η + +1, ν +1) partial decryption key, the simulator lets

L (η+ +1,ν+1) +1,i 1 = µ k=1 (Q k,i 1 ) x +1,k i 1 ∈ {1, . . . , } L (η+ +1,ν+1) +1, +1 = Q 1, +1 L (η+ +1,ν+1) w, +1 = µ k=1 (Q k,d+1 ) x +1,k .
Again, as the simulator knows the discrete logarithm of ŵ, ĥi 1 ,i 2 w.r.t. the base v, the remaining terms -including K (η+ +1,ν+1) +1

-can be generated efficiently. For the remaining partial decryption keys, the simulator generates them faithfully using the Delegate algorithm.

• The remaining delegated key queries are generated faithfully.

Clearly, if Q = Q in the GDDH instance, then the above simulation is identically distributed as Game 0,κ,η,ν , otherwise it is identically distributed as Game 0,κ,η,ν+1 .

The simulator generates the challenge ciphertext as normal and sends it to the adversary. If the adversary has difference in its advantage in Game 0,κ,η,ν and Game 0,κ,η,ν+1 , it is not hard to see that the simulator has a comparable advantage in solving the GDDH instance.

Lemma 5. Game 1 and Game 2 are computationally indistinguishable if the BDH assumption holds in (G, Ĝ, G T ).

Proof. Assume that there's an adversary A that can distinguish between Game 1 and Game 2 . We build an adversary B that uses A as a subroutine to break the BDH assumption. The simulator B receives as input (g, g a , g c , ĝ, ĝa , ĝb , Q ),

where Q is either e(g, ĝ) abc or an element chosen uniformly at random in G T . The adversary A commits to two vectors

( Y 0 1 , . . . , Y 0 d ) and ( Y 1 1 , . . . , Y 1 d ). The challenger B picks β R ← {0, 1}. If d < d, the simulator picks at random d -d vectors Y β d +1 , . . . , Y β d ∈ Z µ p .
The simulator B runs the Setup algorithm as usual except that it implicitly sets α to be ab by defining e(g, v) α = e(g a , ĝb ) αv , and then, for i 1 = 1, . . . , d and i 2 = 1, . . . , µ, it defines h i 1 ,i 2 = (g a ) z i 1 y i 1 ,i 2 g t i 1 ,i 2 for i 1 ∈ {1 . . . , d}, i 2 ∈ {1, . . . , µ} and h i 1 ,0 = (g a ) -z i 1 , for some random exponents z i 1 , t i 1 ,i 2 . The values of ĥi 1 ,i 2 for i 1 ∈ {1 . . . , d}, i 2 ∈ {0, . . . , µ} are defined similarly from the value ĝa of the BDH instance. Observe that β remains hidden from A and that the parameters are correctly distributed.

For the secret key queries, in the last lemma we have just proven that delegated keys are indistinguishable from freshly generated ones. Therefore, B will generate the secret keys using algorithm Keygen when a reveal query is made. Note that α is defined as ab, which is not known to B. However, B needs to simulate secret keys for ( X 1 , . . . , X ) as long as f ( X 1 ,..., X ) ( Y β 1 , . . . , Y β d ) = 0. As α does not appear in the delegating component of the key, the delegation component of the secret keys SK DL can be created using the parameters as usual. Therefore, from now on we focus on how to create the decryption component of the secret key. Denote by the index of the smallest element of the vector ( X 1 , . . . , X ) for which X • Y β = 0. This value always exists if ≤ d by hypothesis and exists with overwhelming probability if > d , since the vectors Y β d +1 , . . . , Y β d ∈ Z µ p are completely hidden from A's view. The simulator creates the decryption component of the secret key as follows:

D = ĝab i 1 =1 µ i 2 =1 ĥx i 1 ,i 2 i 1 ,i 2 r i 1 ŵrw
where the term ĝab

µ i 2 =1 ĥx ,i 2 ,i 2 r is computed as µ i 2 =1 ĥx ,i 2 ,i 2 r (ĝ b ) -( µ i 2 =1 x ,i 2 t ,i 2 )/(z X • Y β ) ,
while the other terms in the product are just computed as usual. It is not hard to see that, if we define r = r -b/(z X • Y β ), then the computation is correct. All the other terms in the decryption component can be computed efficiently, since the simulator knows all the parameters needed and it also knows ĝb . At the challenge step, the adversary A gives B two messages, M 0 and M 1 . B then computes

C 0 = M β • (Q ) αv , C v = (g c ) αv , C w = (g c ) αw , {C i 1 ,i 2 = (g c ) t i 1 ,i 2 } i 1 ∈{1,...,d }, i 2 ∈{1,...,µ}
It is not hard to check that the challenge ciphertext is correctly distributed.

Finally, when the adversary A outputs a guess β , if β = β , then B guesses that Q = e(g, ĝ) abc and if β = β guesses that Q = R. If A has advantage in distinguishing between the two cases, then B also has advantage in solving the assumption G3DH instance, except in the case that A managed to output some secret key query for vector ( X 1 , . . . , X ) for which X i • Y β i = 0 for all i = d + 1, . . . , d was zero for all i ∈ {1, . . . , d}, which occurs only with negligible probability. Lemma 6. Game 2 and Game 3 are computationally indistinguishable if the P-BDH 1 assumption holds in (G, Ĝ).

Proof. Assuming that the adversary A outputs β = β with noticeably different probabilities in Game 2 and Game 3 , we build an distinguisher B for the P-BDH 1 assumption .

Namely, algorithm B receives as input a tuple g, g b , g ab , g c , ĝ, ĝa , ĝb , g z , where a, b, c R ← Z p . Its goal is to decide if z = abc or z ∈ R Z p . To this end, B interacts with A as follows. It first receives the vectors ( Y 0 0 , . . . , Y 0 d ), ( Y 1 0 , . . . , Y 1 d ), at some depth d ≤ d, that A wishes to be challenged upon. We may assume w.l.o.g. that B chooses its challenge bit β R ← {0, 1} at the beginning of the game. Also, if d < d, for each i ∈ {d +1, . . . , d}, B defines the vector Y β i as a random vector of Z µ p . It defines the master public key by setting e(g, v) α = e(g, ĝ) α•γv and

v = g γv , h i 1 ,0 = (g b ) γ i 1 ,0 i 1 ∈ {1, . . . , d} h i 1 ,i 2 = (g b ) -γ i 1 ,0 •y β i 1 ,i 2 • g γ i 1 ,i 2 i 1 ∈ {1, . . . , d}, i 2 ∈ {1, . . . , µ} (13)
w = g y • (g ab ) x , where α, γ v , x, y R ← Z p and γ i 1 ,i 2 R ← Z p , for each i 1 ∈ {1, . . . , d}, i 2 ∈ {0, . . . , µ}. For each i 1 , we also define the vector γ i 1 = (γ i 1 ,1 , . . . , γ i 1 ,µ ) ∈ Z µ p . We observe that B does not know ŵ (which depends on the unavailable term ĝab ) but can compute { ĥi 1 ,i 2 } i 1 ∈{1,...,d},i 2 ∈{1,...,µ} .

When the adversary A requests a key for a hierarchical vector X = ( X 1 , . . . , X ), B parses X i 1 as (x i 1 ,1 , . . . , x i 1 ,µ ) ∈ Z µ p for each i 1 ∈ {1, . . . , }. Then, B responds as follows.

= r i + a • r w • x γ i,0 • X i • Y β i and can compute ( µ i 2 =1 ĥx i,i 2 i,i 2 ) ri • ŵrw = µ i 2 =1 ĥx i,i 2 i,i 2 r i • (ĝ b ) -γ i,0 • X i • Y β i • ĝ γ i • Y β i a• rw •x γ i,0 • X• Y β i •(ĝ ab ) rw•x • ĝrw•y (14) = µ i 2 =1 ĥx i,i 2 i,i 2 r i • (ĝ a ) γ i • Y β i • rw •x γ i,0 • X• Y β i • ĝrw•y
without knowing ĝab . Similarly, it can compute

D i = vr i = ĝγv•r i • (ĝ a ) γv•rw•x/(γ i,0 • X• Y β i )
as well as D w = vrw . We now turn to indices i 1 ∈ {1, . . . , }\{i}, for which B can trivially compute (

µ i 2 =1 ĥx i,i 2 i,i 2 ) r i 1 and D i 1 = vr i 1 • S v,i 1 since it knows { ĥi 1 ,i 2 } µ i 2 =0
and v. This suffices for computing the whole decryption component SK D of the private key.

As for the delegation component SK DL , B can compute {K j,k } j∈{ +1,...,d},k∈{1,...,µ} , {L j } d j= +1

and {L w,j,k } j,k by applying exactly the same procedure as for D, D i and D w (and taking advantage of the fact that X i • Y β i = 0 for at least one i ∈ {1, . . . , }). Remaining pieces of SK DL are then trivially computable since B has { ĥi 1 ,i 2 } µ i 2 =0 and v at disposal. • If > d , it can be the case that X i • Y β i = 0 for i = 1 to . However, with overwhelming probability, there must exist i ∈ {d + 1, . . . , } such that X i • Y β i = 0 since the vectors Y d +1 , . . . , Y d have been chosen at random and, due to the generation of the public key as per [START_REF] Boyen | Shrinking the Keys of Discrete-Log-Type Lossy Trapdoor Functions[END_REF], they are completely independent of A's view. It comes that B can generate a private key in the same way as in the case < d (see equation ( 14)).

When B has to construct the challenge ciphertext, B sets C 0 = M • e(g c , ĝγv ) α , where M R ← G T , and

C v = (g c ) γv , C w = (g c ) y • (g z ) x , C i 1 ,i 2 = (g c ) γ i 1 ,i 2 i 1 ∈ {1, . . . , d }, i 2 ∈ {1, . . . , µ}
We observe that, if z = abc, (C 0 , C v , C w , {C i 1 ,i 2 } i 1 ∈{1,...,d },i 2 ∈{1,...,µ} ) corresponds to a valid ciphertext with the encryption exponent s = c. In this situation, B is playing Game 2 with A.

In contrast, if z ∈ R Z p , we have z = c with overwhelming probability. In this case, we have g z = g abc+θ , for some θ = 0, and we can thus write C w = w c • g θ•x . This means that C w looks uniformly random and independent from A's view. Indeed, until the challenge phase, A has no information about θ ∈ Z p (recall that public parameters do not depend on c) and the value x ∈ Z p 1 is also independent of A's view. We conclude that, if g z is such that z ∈ R Z p , we are in Game 3 . Lemma 7. For each δ 1 ∈ {1, . . . , d} and each δ 2 ∈ {2, . . . , µ}, Game 4,δ 1 ,δ 2 -1 and Game 4,δ 1 ,δ 2 are computationally indistinguishable if the P-BDH 1 assumption holds in (G, Ĝ).

Proof. Towards a contradiction, we assume there exists δ 1 , δ 2 such that the adversary A outputs β = β with significantly different probabilities in Game 4,δ 1 ,δ 2 -1 and Game 4,δ 1 ,δ 2 . We show that A implies a distinguisher B against P-BDH 1 .

Our distinguisher B receives as input g, g b , g ab , g c , ĝ, ĝa , ĝb , g z , with a, b, c R ← Z p . It aims to decide if z = abc or z ∈ R Z p .

To do this, B runs the adversary A as follows. It first receives the challenge vectors ( Y 0 0 , . . . , Y 0 d ), ( Y 1 0 , . . . , Y 1 d ), at some depth d ≤ d, that are chosen by A. We assume that B chooses its challenge bit β R ← {0, 1} at the outset of the game. Also, if d < d, for each i ∈ {d + 1, . . . , d}, B defines the vector Y β i as a random vector of Z µ p . It defines the master public key by setting e(g, v) α = e(g, ĝ) α•γv and

v = g γv , h i 1 ,0 = g γ i 1 ,0 p 1 for i 1 ∈ {1, . . . , d} h i 1 ,i 2 = g -γ i 1 ,0 •y β i 1 ,i 2 • g γ i 1 ,i 2 if i 1 ∈ {1, . . . , d}\{δ 1 } or i 2 ∈ {1, . . . , µ}\{δ 2 } h δ 1 ,δ 2 = g -γ δ 1 ,0 •y β δ 1 ,δ 2 • (g ab ) γ δ 1 ,δ 2 (15)
w = g y • (g b ) x , where α, γ v , y R ← Z p , x R ← Z * p and γ i 1 ,i 2 R
← Z p , for each i 1 ∈ {1, . . . , d}, i 2 ∈ {0, . . . , µ}. For each i 1 , we also define the vector γ i 1 = (γ i 1 ,1 , . . . , γ i 1 ,µ ) ∈ Z µ p . Note that, in the implicitly defined master secret key msk, the distinguisher B knows all the components but ĥδ 1 ,δ 2 , which depends on the unknown term ĝab .

When the adversary A requests a key for a hierarchical vector X = ( X 1 , . . . , X ), B parses X i 1 as (x i 1 ,1 , . . . , x i 1 ,µ ) ∈ Z µ p for each i 1 ∈ {1, . . . , }. Then, B responds as follows.

• If ≥ δ 1 , B chooses r w R ← Z p and r δ 1 R ← Z p , B implicitly defines the exponent r w = r w - a • r δ 1 • γ δ 1 ,δ 2 x (16)
and can compute the product

ĥy β δ 1 ,δ 2 δ 1 ,0 • ĥδ 1 ,δ 2 r δ 1 • ŵrw = (ĝ ab ) γ δ 1 ,δ 2 •r δ 1 • ŵr w • ĝy (ĝ b ) x -a•r δ 1 •γ δ 1 ,δ 2 /x (17)
= ŵr w • (ĝ a ) -y•r δ 1 •γ δ 1 ,δ 2 /x , which is the only factor of D that it cannot trivially compute without knowing ĝab . Similarly, it can compute

D w = v rw = ĝγv•r w • (ĝ a ) -γv•r δ 1 •γ δ 1 ,δ 2 /x .
To generate the delegation component SK DL of the key, the reduction B is able to compute {K j,k , L w,j,k } j∈{ +1,...,d},k∈{1,...,µ} by repeating (d -) • µ times the same procedure as for computing D and D w .

• If < δ 1 , B can directly compute (D, D w , {D i 1 } i 1 =1 ) since it knows { ĥi 1 ,i 2 } i 1 ∈{1,..., },i 2
∈{1,...,µ} , v and ŵ. The difficulty is to compute the delegation components {K δ 1 ,k } µ k=1 without knowing ĝab . In fact, among these components, the only factor of K δ 1 ,δ 2 that B cannot trivially compute is ĥs δ 1 δ 1 ,δ 2 . However, similarly to ( 16)-( 17

), it can choose s δ 1 , s w,δ 1 ,δ 2 R ← Z p , define s w,δ 1 ,δ 2 = s w,δ 1 ,δ 2 - a•s δ 1 •γ δ 1 ,δ 2 x
and compute the product

h s δ 1 δ 1 ,δ 2 • ŵs w,δ 1 ,δ 2 = (ĝ -γ δ 1 ,0 •y β δ 1 ,δ 2 •s δ 1 ) • (ĝ ab ) γ δ 1 ,δ 2 •s δ 1 • ĝy (ĝ b ) x -a•s δ 1 •γ δ 1 ,δ 2 /x • ŵs w,δ 1 ,δ 2 = (ĝ -γ δ 1 ,0 •y β δ 1 ,δ 2 •s δ 1 ) • ŵs w,δ 1 ,δ 2 • (ĝ a ) -y•s δ 1 •γ δ 1 ,δ 2 /x (
[RL k ⇒ 1] -Pr[RL k-1 ⇒ 1]| ≤ (d • µ + 1) • Adv P-BDH 1 (B 1 ) + q • Adv P-BDH 2 (B 2 ),
where q is the number of "Reveal-key" queries made by A.

Proof. For the sake of contradiction, let us assume that there exist two auxiliary hierarchical vector

y (0) = [y (0) 1 | . . . |y (0) d ], y (1) = [y (1) 1 | . . . |y (1)
d ] and an index k ∈ {1, . . . , n} such that the adversary A has noticeably different behaviors in experiments RL k and RL k-1 . Using A, we construct a selective weakly attribute-hiding adversary B against the HPE scheme described in Section 3.2 (in its predicate-only variant).

Our adversary B first declares y (0) , y (1) ∈ Z d•µ p as the vectors that it wishes to be challenged upon. Then, the HPE challenger provides B with public parameters , which it uses to compute

mpk HPE = v, w, {h i 1 ,i 2 } i 1 ∈{1,...,
w[l 1 ] = v ζ[l 1 ] for l 1 ∈ {1, . . . , n}\{k} h[i 1 , i 2 , l 1 ] = v γ[i 1 ,i 2 ,l 1 ]
for i 1 ∈ {1, . . . , d}, i 2 ∈ {0, . . . , µ}, l 1 ∈ {1, . . . , n}\{k}.

It also sets w[k] = w as well as

h[i 1 , i 2 , k] = h i 1 ,i 2 for i 1 ∈ {1, . . . , d}, i 2 ∈ {0, . . . , µ}.
Then, B defines core public parameters

PP core = v, {w[l 1 ], {h[i 1 , i 2 , l 1 ]} i 1 ∈{1
,...,d},i 2 ∈{0,...,µ}, l 1 ∈{1,...,n} , that correspond to the master secret key msk = (v, ŵ, ĥ), which is not completely known to B (specifically, v, ŵ[k] and ĥ[., ., k] are not available). Then, B notifies its HPE challenger that it wishes to directly enter the challenge phase without making any pre-challenge query. The challenger replies with the challenge ciphertext

C = C v , C w , {C i 1 ,i 2 } i 1 ∈{1,...,d}, i 2 ∈{1,...,µ} ,
where

C v = v s , C w = w s , { C i 1 ,i 2 = h y (β) i 1 ,i 2 i 1 ,0 • h i 1 ,i 2 s } i 1 ∈{1,...,d}, i 2 ∈{1,...,µ} ,
for a random element s R ← Z * p and a random bit β ∈ {0, 1}. Here we are using, for β ∈ {0, 1}, the notation y

(β) = [y (β) 1 | . . . |y (β) d ] ∈ Z d•µ
p , where each y (β)

i 1 = (y (β) i 1 ,1 , . . . , y (β)
i 1 ,µ ) ∈ Z µ p , for i 1 ∈ {1, . . . , d}. At this point, B constructs the matrix {CT[i 1 , i 2 ]} l 1 ,l 2 ∈{1,...,n} of HPE ciphertexts by setting

J[k] = C v C w [k, k] = C w C[i 1 , i 2 , k, k] = C i 1 ,i 2
for i 1 ∈ {1, . . . , d}, i 2 ∈ {1, . . . , µ}.

prefixes of id , then the condition is satisfied. This implies that d 1 = 1 with overwhelming probability. Also, the pre-output stage P in this case simply outputs d 2 = 1, always. This implies that d A ¬abort is 1 with overwhelming probability and, as a consequence, Pr

[d A ¬abort = 1 | REAL A HF,LHF,ω,ζ ] is negligibly close to 1 and Pr[d A = 1 | REAL A HF,LHF,ω,ζ ∧ d A ¬abort = 1] -1 2 is negligibly close to Pr[d A = 1 | REAL A HF,LHF,ω ] -1 2 .
These are precisely the requirements for HF to fulfill conditions (ii) and (iii), with δ = 1.

B.3 Adaptive Security: Proof of Lemma 2

Fix the view of the adversary A, which implies fixing the queried identities id (1) , . . . , id (q) , id . Although we are assuming that the adversary A makes the maximum number of queries, with a smaller number of queries we would have the same bounds. We abbreviate η = η(IS, id ), y = y (1) and also call the depth of the challenge identity id . For an integer t, define the event

E t : q i=1   (i) i 1 =1 id (i) i 1 , y i 1 = 0 mod t   ∧ i 1 =1 id i 1 , y i 1 = 0 mod t
We denote Y = {y 1 , . . . , y d , y 1 , . . . , y d , ξ 1 , . . . , ξ d }. For all i 1 ∈ {1, . . . , }, we have

id i 1 , y i 1 = y i 1 + µ k=2 y i 1 [k]id i 1 [k] -2ξ i 1 q for some 0 ≤ ξ i 1 ≤ µ -1. In particular, observe that 0 ≤ y i 1 + µ k=2 y i 1 [k]id i 1 [k] < 2qµ < p.
Let us define the value ξ i

1 := (y i 1 + µ k=2 y i 1 [k]id i 1 [k]
)/2q . If we have the two conditions ξ i 1 = ξ i 1 for each i 1 ∈ {1, . . . , } id i 1 , y i 1 = 0 mod 2q, then clearly id i 1 , y i 1 = 0 mod p. Also, if id i 1 , y i 1 = 0 mod 2q, then we also have id i 1 , y i 1 = 0 mod p . Using these observations, we have

η ≥ Pr[ξ i 1 = ξ i 1 ∀i 1 ∈ {1, . . . , }] Pr Y [E p | ξ i 1 = ξ i 1 ∀i 1 ∈ {1, . . . , }] = 1 µ Pr Y [E p | ξ i 1 = ξ i 1 ∀i 1 ∈ {1, . . . , }] ≥ 1 µ Pr Y [E 2q | ξ i 1 = ξ i 1 ∀i 1 ∈ {1, . . . , }] = 1 µ Pr Y [E 2q | ξ i 1 = ξ i 1 ∀i 1 ∈ {1, . . . , }]
where Y contains {y 1 , . . . , y d } and y i 1 = (y i 1 , y i 1 [START_REF] Agrawal | Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE[END_REF], . . . , y i 1 [µ]) for all i ∈ {1, . . . , d}. Note that the second inequality above holds because of the condition ξ i 1 = ξ i 1 . If we now define η 2q = Pr Y [E 2q | ξ i 1 = ξ i 1 ∀i 1 ∈ {1, . . . , }], we just showed that η ≥ 1 µ • η 2q . Now, we observe some facts about id i 1 , y i 1 . First, observe that id i 1 , y i 1 and id i 1 , y i 1 are independent for i 1 = i 1 . This is because of the way Y is chosen. Also, note that for any id i 1 , a ∈ Z, Pr Y [ id i 1 , y i 1 = a mod 2q] = 1/2q. This is because for any choice of y i 1 [START_REF] Agrawal | Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE[END_REF], . . . , y i 1 [µ], there is only one value of y i 1 for which the equality holds.

Consider id = (id 1 , . . . , id ) = id = (id 1 , . . . , id ) and id not being a prefix of id and a, b ∈ Z. First, if > , for each i 1 ∈ { + 1, . . . , } such that id i 1 = id i 1 , we have On the other hand, for all i 1 ≤ , Pr Y [ id i 1 , y i 1 = a mod 2q| k=1 id k , y k = b mod 2q] is either 0, if id i 1 = id i 1 or 1/2q, if id i 1 = id i 1 . The second fact is because, if id i 1 = id i 1 , there exists an index j for which id i 1 [j] = 1 and id i 1 [j] = 0 or the other way around. We see that, if we fix all y i 1 [i] for i = j so that id i 1 , y i 1 = b mod 2q, then there is only one value for y i 1 [j] so that id i 1 , y i 1 = a mod 2q.

With all these observations, we calculate the following bound on η 2q :

η 2q = Pr Y   q i=1   (i) i 1 =1 id (i) i 1 , y i 1 = 0 mod 2q   | i 1 =1 id i 1 , y i 1 = 0 mod 2q   • • Pr Y i 1 =1 id i 1 , y i 1 = 0 mod 2q = 1/(2q) Pr Y   q i=1   (i) i 1 =1 id (i) i 1 , y i 1 = 0 mod 2q   | i 1 =1 id i 1 , y i 1 = 0 mod 2q   = 1/(2q)   1 -Pr Y   q i=1   (i) i 1 =1 id (i) i 1 , y i 1 = 0 mod 2q   | i 1 =1 id i 1 , y i 1 = 0 mod 2q     (21)
≥ 1/(2q)

  1 - q i=1 Pr Y   (i) i 1 =1 id (i) i 1 , y i 1 = 0 mod 2q | i 1 =1 id i 1 , y i 1 = 0 mod 2q    
We now focus on how to bound

Pr Y   (i) i 1 =1 id (i) i 1 , y i 1 = 0 mod 2q | i 1 =1 id i 1 , y i 1 = 0 mod 2q   .
First, observe that id (i) i 1 , y i 1 = 0 mod 2q is independent to id (i) i 1 , y i 1 = 0 mod 2q if i 1 = i 1 . As a consequence, we only need to compute Pr Y id (i) i 1 , y i 1 = 0 mod 2q| k=1 ( id k , y k = 0 mod 2q) . To this end, we consider two cases: that (i) > or (i) ≤ . In the first case, for each i 1 ∈ { + 1, . . . , (i) } such that Pr Y id (i) We can conclude that η 2q ≥ 1/(2 +1 q ). Combining this bound with the bound on η, we get the statement of the Lemma.

B.4 Adaptive Security: Proof of Theorem 3

Regarding condition (i) of partial lossiness, let RL 0 and RL n be the games specified in Section 4.2. Let RL 0 and RL n be the games which are the same as RL 0 and RL n except that they include the artificial abort stage described above. First, we claim that

Pr[ RL 0 ⇒ 1] -Pr[ RL n ⇒ 1] ≤ n • (d • µ + 1) • Adv P-BDH 1 (B 1 ) + q • Adv P-DDH 2 (B 2 )
The proof for this statement is almost identical to the proof for Lemma 1. We now claim that both Pr These statements imply condition (i) of partial lossiness. The proof of the last two statements is identical to the proof for Theorem 4: when using the auxiliary input y (0) , HF.Eval will always be injective. On the other hand, when using y (1) , HF.Eval will be lossy for identities (id 1 , . . . , id ) such that y (1) i 1 , id i 1 = 0 for all i 1 ∈ {1, . . . , }, with lossiness λ HF.Eval pms, mpk, (id 1 , . . . , id ), . ≥ n -log p = ω, and HF.Eval will be injective for the other identities.

Seeing that condition (ii) is fulfilled is straightforward: from Lemma 2, we know that η low ≤ Pr , which is non-negligible. However, the value of 1 will not be this lower bound. Instead, we will show that another condition (which we give at the end of this proof) is satisfied and guarantees the existence of 1 and 2 . The proof for this is actually very similar to the proof in [START_REF] Waters | Efficient Identity-Based Encryption Without Random Oracles[END_REF]. Here, we briefly outline the details. First, due to Chernoff bounds we have the following: We refer the reader to [START_REF] Waters | Efficient Identity-Based Encryption Without Random Oracles[END_REF] for details on how to compute these bounds.

Pr[d A ¬abort = 1 | d A = 1 ∧ REAL] ≥ η low (1 -
Let us now assume the existence of a PPT adversary A such that

Pr[d A = 1 | REAL] - 1

4. 1

 1 Description HF.Setup( , d, n, µ): given a security parameter ∈ N, the (constant) desired number of levels in the hierarchy d ∈ N and integers µ, n ∈ poly( ) specifying the length of identities and that of function inputs, respectively, choose asymmetric bilinear groups (G, Ĝ, G T ) of prime order p > 2 . Define InpSp = {0, 1} n , Σ ID = {(1, x) : x ∈ Z µ-1 p }, IdSp = Σ (≤d) ID and AuxSp = Z d•µ p . The public parameters are pms = p, (G, Ĝ, G T ), d, n, µ, InpSp, IdSp, AuxSp . Since HF is an extended HIB-TDF, the master key generation algorithm of our HIB-TDF receives an auxiliary input y ∈ AuxSp. Here, it is seen as a concatenation of d row vectors y 1 , . . . , y d ∈ Z µ p . HF.MKg(pms, y): parse the auxiliary input as y = [y 1 | . . . |y d ] ∈ Z d•µ p , and proceed as follows. 1. Choose α

3 :Theorem 3 .

 33 Lemma 2. η low = 1/ 2 • (2qµ) d ≤ η(IS, id ) P computes an approximation η (IS, id ) of η(IS, id ), by using O(ζ -2 ln(ζ -1 )η -1 low ln(η -1 low )) samples, for a non-negligible ζ, which is part of the input to P. If η (IS, id ) ≤ η low , then d 2 is always set to 1. If η (IS, id ) > η low , then d 2 = 0 with probability 1 -η low /η (IS, id ) and d 2 = 1 with probability η low /η (IS, id ). Adaptive security of HF is established in the following theorem. Let n > log p and let ω = n -log p. Let HF be the HIB-TDF with parameters n, d, µ, Σ ID

PrY[

  id i 1 , y i 1 = a mod 2q| k=1 id k , y k = b mod 2q] = Pr Y [ id i 1 , y i 1 = a mod 2q] = 1/2q.This happens because k=1 id k , y k = b mod 2q does not impose any condition on id i 1 , y i 1 and we can apply the same arguments as previously.

i 1 ,i 1 ,i 1 ,i 1 ,

 1111 y i 1 = 0 mod 2q| k=1 ( id k , y k = 0 mod 2q) y i 1 = 0 mod 2q = 1/2q.For all indices i 1 ∈ , the same probability is either 1 or 1/(2q).If (i) ≤ , for each i 1 ∈ {1, . . . , (i) }, y i 1 = 0 mod 2q| k=1 ( id k , y k = 0 mod 2q) y i 1 = 0 mod 2q| id i 1 , y i 1 = 0 mod 2q which is 1 if id (i)i 1 = id i 1 and 1/(2q) otherwise due to the fact stated above. Define χ(i) 1 = max( (i) -, 0) and χ (i) 2 = #{1 ≤ i 1 ≤ min( , (i) )|id

i 1 = 2 ≥i 1 , 1 =1id i 1 , y i 1 =

 121111 id i 1 }. Note that, by the restrictions imposed on id (i) , we have χ 1 for all i ∈ {1, . . . , q}. Putting it all together, y i 1 = 0 mod 2q | i

[d A exp = 1 |

 1 REAL] = Pr[ RL 0 ⇒ 1] and | Pr[d A exp = 1 | LOSSY] -Pr[ RL n ⇒ 1]| ∈ negl( ).

[d 1 = 1 |

 11 REAL] and, by construction, η low ≤ Pr[d 2 = 1 | d 1 = 1 ∧ REAL]. This gives us the lower bound η 2 low on Pr[d ¬abort = 1 | REAL]

  A ¬abort = 1 | d A = 0 ∧ REAL] ≤ η low (1

  for some non-negligible ζ. This implies that we can write Pr[d A = 1 | REAL] > 1/2 + ζ and Pr[d A = 0 | REAL] < 1/2 -ζ.Combining these inequalities with the two inequalities above (from Chernoff bounds) we obtainPr[d A = 1 | REAL] • Pr[d A ¬abort = 1 | d A = 1 ∧ REAL] -Pr[d A = 0 | REAL] • Pr[d A ¬abort = 1 | d A = 0 ∧ REAL] > 2δζ (22)with δ = 13η low /16 = 13/ 32 • (2qµ) d . Now, let us observe thatPr[d A = 1 | REAL] • Pr[d A ¬abort = 1 | d A = 1 ∧ REAL] = Pr[d A ¬abort = 1 ∧ d A = 1 | REAL]andPr[d A = 0 | REAL] • Pr[d A ¬abort = 1 | d A = 0 ∧ REAL] = = Pr[d A ¬abort = 1 ∧ d A = 0 | REAL] = Pr[d A ¬abort = 1 | REAL] • Pr[d A = 0 | d A ¬abort = 1 ∧ REAL] = Pr[d A ¬abort = 1 | REAL] • (1 -Pr[d A = 1 | d A ¬abort = 1 ∧ REAL]) = Pr[d A ¬abort = 1 | REAL] -Pr[d A ¬abort = 1 ∧ d A = 1 | REAL]Combining these two equalities with inequality[START_REF] Gentry | Hierarchical ID-Based Cryptography[END_REF], we obtain 2δζ < 2 Pr[d A ¬abort = 1 ∧ d A = 1 | REAL] -Pr[d A ¬abort = 1 | REAL].

  it is created by running LHF.Kg(pms, msk 1 , id). The list QS is updated as QS = QS ∪ {id}.-Create-delegated-key: A provides id = (id 1 , . . . , id ) and id +1 such that id ∈ QS. The challenger C then computes SK id for id = (id 1 , . . . , id +1 ) by running the delegation algorithm HF.Del pms, mpk β , SK id , id +1 . The list QS is updated asQS = QS ∪ {id }. -Reveal-key: A provides id with the restriction that if A is selective, then id ≤ id † . C returns ⊥ if id ∈ QS.Otherwise, SK id is returned to A and the list IS is updated as IS = IS ∪ {id}.3. The adversaryA outputs a hierarchical identity id = (id 1 , . . . , id ) and a bit d A ∈ {0, 1}. If A is selective, then id = id † . In the adaptive case, no element of IS can be a prefix of id . Let d 1 be the bit d 1 := ∀ id ∈ IS, λ (HF.Eval(pms, mpk 1 , id, •)) = 0 ∧ λ (HF.Eval(pms, mpk 1 , id , •)) ≥ ω . 4. C sets d 2 to be the output of the pre-output stage P with input ζ, pms, mpk 1 , msk 1 , IS, id . 5. The final output of the experiment consists of {d A , d A ¬abort }, where d

  d}, k∈{1,...,µ}, i 1 ∈{1,..., } Return the delegated private key SK ( X 1 ,..., X +1 ) = (SK D , SK DL ).Encrypt mpk, ( Y 1 , . . . , Y κ ), M : given mpk, a plaintext M ∈ G T as well as a hierarchy of vectors Y

1 = (y 1,1 , . . . , y 1,µ ), . . . , Y κ = (y κ,1 , . . . , y κ,µ ), choose s R ← Z * p and compute

  • If ≤ d , let i ∈ {1, . . . , } be the smallest index such that X i • Y β i = 0 (by hypothesis, this index must exist). By choosing r w

	R ← Z p and r i	R ← Z p , B implicitly defines the exponent
	ri

18 )

 18 Lemma 8. If the HPE scheme described in Section 3.2 is selectively weakly attribute-hiding, then Game RL k is indistinguishable from Game RL k-1 for each k ∈ {1, . . . , n}. Namely, for each k, there exist algorithms B 1 and B 2 such that |Pr

  d},i 2 ∈{0,...,µ} .

	Then, B chooses a vector ζ R ← Z n p and a matrix γ ∈ Z d×(µ+1)×n p

See[START_REF] Xie | Deterministic Public Key Encryption and Identity-Based Encryption from Lattices in the Auxiliary-Input Setting[END_REF] for a recent and independent construction, in the (non-hierarchical) IBE case.

The cases of deterministic HIBE and hedged HIBE are discussed in Appendices C and D.

This distinguisher A1 is obtained from A by ignoring dA ∈ {0, 1} and replacing it by a 1, so that d A ¬abort = d A exp .

As in[START_REF] Boneh | Conjunctive, Subset, and Range Queries on Encrypted Data[END_REF][START_REF] Katz | Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products[END_REF], the plaintext space is restricted to have a size much smaller than |GT | to make sure that the decryption algorithm returns ⊥ if an unauthorized key is used to decrypt.

Informally, a block source is a distribution of message vectors where each component has high min-entropy conditionally on previous ones.

A Deferred Definitions and Proofs for Hierarchical Predicate Encryption

A.1 Definitions for Hierarchical Predicate Encryption

A tuple of integers ν = (µ 1 , d; ν 1 , . . . , ν d ) such that ν 0 = 0 ≤ ν 1 < ν 2 < • • • , < ν d = µ 1 is called a format hierarchy of depth d. Such a hierarchy is associated with attribute spaces {Σ i } d i=0 . In our setting, we set Σ i = Z ν i -ν i-1 p \{ 0} for i = 1 to d, for some p ∈ N, and also define the universe of hierarchical attributes as

For vectors { X i ∈ Σ i } i∈{1,...,d} , we will consider the (inner-product) hierarchical predicate f ( X 1 ,..., X ) ( Y 1 , . . . , Y κ ) = 1 iff ≤ κ and X i • Y i = 0 for all i ∈ {1, . . . , }. The space of hierarchical predicates is defined to be F = {f ( X 1 ,..., X ) |{ X i ∈ Σ i } i∈{1,..., } } and the integer κ (resp. ) is called the depth (resp. the level) of ( Y 1 , . . . , Y κ ) (resp. ( X 1 , . . . , X )). Most of the time we will assume that ν i /ν i-1 = µ for any i, and to specify the format hierarchy we will only have to give µ and d.

Let ν = (µ 1 , d; ν 1 , . . . , ν d ) be a format hierarchy. A hierarchical predicate encryption (HPE) scheme for a predicate family F consists of these algorithms.

Setup( , ν): takes as input a security parameter ∈ N and a format hierarchy ν = (n 1 , d; ν 1 , . . . , ν d ).

It outputs a master secret key msk and a master public key mpk that includes the description of a hierarchical attribute space Σ. Keygen msk, ( X 1 , . . . , X ) : takes as input predicate vectors ( X 1 , . . . , X ) ∈ Σ 1 × • • • × Σ and the master secret key msk. It outputs a private key SK ( X 1 ,..., X ) .

Encrypt mpk, ( Y 1 , . . . , Y κ ), M : takes as input attribute vectors ( Y 1 , . . . , Y κ ) ∈ Σ 1 × • • • × Σ k , the master public key mpk and a message M . It outputs a ciphertext C. Decrypt mpk, ( X 1 , . . . , X ), SK ( X 1 ,..., X ) , C : takes in a private key SK ( X 1 ,..., X ) for the vectors ( X 1 , . . . , X ), the master public key mpk and a ciphertext C. It outputs a plaintext M or ⊥.

In the same way, B computes

Note that, for each k ∈ {1, . . . , µ}\{δ 2 }, B has to generate K δ 1 ,k by computing ĥs δ 1 δ 1 ,k using the same random exponent s δ 1 as in [START_REF] Dodis | Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data[END_REF]. This is always possible since B knows that exponent.

When it comes to construct the challenge ciphertext, algorithm B first sets

as well as

We observe that, in the situation where z = abc,

In contrast, if z ∈ R Z p , we have z = c with overwhelming probability. In this case, C δ 1 ,δ 2 looks random to the adversary and B is thus playing Game 4,δ 1 ,δ 2 .

B Deferred Proofs for the Security of HF

B.1 Proof of Lemma 1

We consider a sequence of n + 1 hybrid experiments RL 0 , . . . , RL n . For each k ∈ {0, . . . , n}, RL k is defined to be an experiment where public parameters are generated as follows. First, the simulator

)×n , ĥ R ← Ĝd×(µ+1)×n and computes PP core in the same way as in the real scheme.

In the second step of the setup procedure, the simulator B chooses a vector s R ← (Z * p ) n . For l 1 , l 2 ∈ {1, . . . , n}, it first computes

Then, for each pair (l 1 , l 2 ) such that l 1 = l 2 , B sets

Finally, for each l ∈ {1, . . . , n}, i 1 ∈ {1, . . . , d} and i 2 ∈ {1, . . . , µ}, B defines

Lemma 8 below demonstrates that, for each k ∈ {1, . . . , n}, experiment RL k is computationally indistinguishable from experiment RL k-1 .

If we assume that the statement of Lemma 1 is false, there must exist k ∈ {1, . . . , n} such that the adversary can distinguish RL k from RL k-1 and we obtain a contradiction. and, for each l 1 ∈ {1, . . . , n}\{k},

Note that this implicity sets s[k] = s, where s is the encryption exponent chosen by the HPE challenger to compute C . Then, for each l 2 ∈ {1, . . . , n}\{k}, B chooses a random exponent s[l 2 ] R ← Z * p and computes

for

for i 1 ∈ {1, . . . , d}, i 2 ∈ {1, . . . , µ},

As for entries of the form {C[i 1 , i 2 , l, l]} i 1 ,i 2 ,l =k , B computes them as

if l > k.

using the exponents s[l] ∈ Z * p that were chosen in [START_REF] Dodis | Entropic Security and the Encryption of High Entropy Messages[END_REF]. Finally, our adversary B defines the

Finally, B defines mpk := PP core , {CT[l 2 , l 1 ]} l 2 ,l 1 ∈{1,...,n} and sends it to the adversary A.

When it comes to answer A's private key queries for hierarchical identities (id 1 , . . . , id ), B first encodes each level's identity id i 1 ∈ {0, 1} µ as a µ-vector

of the private key are always directly computable when

← Ĝ, for i 1 = 1 to , and computes

) forms a decryption component of the form [START_REF] Bellare | Deterministic Encryption: Definitional Equivalences and Constructions without Random Oracles[END_REF]. Moreover, the delegation components can be obtained exactly in the same way.

As for the remaining coordinate l 1 = k, the simulator B aborts if, for any γ ∈ {0, 1}, the obtained hierarchical vector ( X 1 , . . . , X ) is one for which y

d ) = 1 in the predicate encryption language). Otherwise, B can obtain the missing private key components by invoking its HPE challenger to obtain a complete private key SK (id 1 ,...,id ) = (SK D , SK DL ).

It is easy to check that, if the HPE challenger's bit is β = 0, mpk is distributed as in Game RL k . In contrast, if β = 1, mpk has the same distribution as in Game RL k-1 .

B.2 Selective Security of HF

We consider our HF with µ = 2, Σ ID = {(1, x) : x ∈ Z * p } and IdSp = (Σ ID ) (≤d) . Let (id 1 , . . . , id ) ∈ IdSp be the identity chosen by the adversary. Define the sibling LHF with AuxSp = Z 2d p and auxiliary input y (1) = [y

p where y

i 1 = (-id i 1 , 1) for all i 1 ∈ {1, . . . , } and y

(1)

Selective security is established in the following theorem. In this selective setting, we will omit ζ in the notation, because the trivial pre-output stage that always outputs d 2 = 1 will be enough in this case and, as a consequence, the experiments do not depend on ζ. (≤d) . Let LHF be the sibling associated with it as above. Then HF is (ω, 1)-partially lossy against selective-id adversaries.

Specifically regarding condition (i), for any selective-id adversary A there exist algorithms B 1 and B 2 such that

The running time of B 1 and B 2 are comparable to the running time of A.

Proof. Let RL 0 and RL n be the games specified above. We claim that both

), which implies condition (i) of partial lossiness, when combined with Lemma 1.

To prove that, we just need to justify that, when using y (0) as the auxiliary input, the function HF.Eval is injective for all identities id. On the other hand, when using y (1) , the function HF.Eval will be lossy for identities id = (id 1 , . . . , id ) such that y

(1) i 1 , id i 1 = 0 for all i 1 ∈ {1, . . . , } and injective for all other identities.

To see that, note that all the terms of the output of HF.Eval are determined by s, X except the term CT id [i 1 , l 1 ], which is also determined by s[l 1 ] • x l 1 • y i 1 , id i 1 . Therefore, when y i 1 , id i 1 = 0 for all i 1 ∈ {1, . . . , }, the function will be determined only by s, X , which can take only p values, so HF.Eval will be lossy with lossiness λ HF.Eval pms, mpk, (id 1 , . . . , id ), . ≥ n -log p = ω. On the other hand, if there is at least one index i 1 for which y i 1 , id i 1 = 0, then HF.Eval will be injective with overwhelming probability and HF.Inv will be its inverse, also with overwhelming probability. Finally, observe that when the auxiliary input is y (0) , then for all identities (id 1 , . . . , id ) and for all i 1 ∈ {1, . . . , }, y

With this, we conclude that y (0) makes HF.Eval injective for all identities and y (1) makes HF.Eval lossy only for identities such that y i 1 , id i 1 = 0 for all i 1 ∈ {1, . . . , }, and in this case the lossiness is n -log p (where when we claim that HF.Eval is injective, it holds with overwhelming probability). This concludes the proof of condition (i).

Regarding conditions (ii) and (iii), when the auxiliary input is y (1) , then HF.Eval is injective for all valid queried id in "Reveal key" queries and HF.Eval is lossy for id = (id 1 , . . . , id ). Indeed, we are setting y

(1) i 1 = (-id i 1 , 1) for all i 1 ∈ {1, . . . , } and y

(1)

This implies that if id = (id 1 , . . . , id ) is an identity, then y i 1 , id i 1 = 0 for all i 1 ∈ {1, . . . , } if and only if id is a prefix of id . As the adversary is not allowed to make "Reveal key" queries for Dividing this inequality by 2 and using the fact that

Finally, this shows that there exist 1 and 2 such that (ii) and (iii) are satisfied and that their product is δ. The setup algorithm HIB-DE.Setup takes as input a security parameter ∈ N, the (constant) number of levels in the hierarchy d ∈ N, the length of the identities µ ∈ poly( ) and the length of the plaintexts s ∈ poly( ), and outputs a set of global public parameters pms, which specifies an identity space IdSp and the necessary mathematical objects and hash functions. The master key generation algorithm HIB-DE.MKg takes as input pms and outputs a master public key mpk and a master secret key msk. The key generation algorithm HIB-DE.Kg takes as input pms, msk and a hierarchical identity (id 1 , . . . , id ) ∈ IdSp, for some ≥ 1 and outputs a secret key SK (id 1 ,...,id ) . The delegation algorithm HIB-DE.Del takes as input pms, msk, a hierarchical identity (id 1 , . . . , id ), a secret key SK (id 1 ,...,id ) for it, and an additional identity id +1 ; the output is a secret key SK (id 1 ,...,id ,id +1 ) for the hierarchical identity (id 1 , . . . , id , id +1 ) iff (id 1 , . . . , id , id +1 ) ∈ IdSp. The evaluation algorithm HIB-DE.Enc takes as input pms, msk, a hierarchical identity id = (id 1 , . . . , id ) and a value m ∈ {0, 1} s ; the result of the evaluation is denoted as C. Finally, the inversion algorithm HIB-DE.Dec takes as input pms, msk, a hierarchical identity id = (id 1 , . . . , id ), a secret key SK id for it and an evaluation C, and outputs a value m ∈ {0, 1} s .

C Adaptive-id Secure Deterministic (H)IBE

A Bellare et al. [START_REF] Bellare | Deterministic Encryption: Definitional Equivalences and Constructions without Random Oracles[END_REF] gave several definitions for deterministic encryption and proved them equivalent. In the case of block sources 9 [10], Boldyreva et al. [START_REF] Boldyreva | On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles[END_REF] proved that single-challenge security (called PRIV1 security in [START_REF] Bellare | Deterministic Encryption: Definitional Equivalences and Constructions without Random Oracles[END_REF][START_REF] Boldyreva | On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles[END_REF]) is equivalent to multi-challenge security (referred to as PRIV security [START_REF] Bellare | Deterministic Encryption: Definitional Equivalences and Constructions without Random Oracles[END_REF], where the adversary is given a vector of challenge ciphertexts) in the sense of indistinguishabilitybased definitions. The simplified indistinguishability-based notion, called PRIV1-IND hereafter, is somewhat handier to work with and we thus use this one.

We define PRIV1-IND-ID security, the natural analogue of PRIV1-IND security in the IBE scenario. The security notion is defined via the following experiment between a challenger and an adversary. Some instructions depend on whether we are in the selective or adaptive security case. Definition 3. We define Guess A HIB-DE (M ), for a random variable M as follows:

0. The challenger C chooses global parameters pms by running HIB-DE.Setup. The parameters pms are given to A, who replies by choosing a hierarchical identity id † = (id † 1 , . . . , id † † ), for some † ≤ d. 1. The challenger runs (mpk, msk) ← HIB-DE.MKg(pms) and sends mpk to A. Also, two lists QS ← ∅, IS ← ∅ are initialized. 2. A is allowed to make a number of adaptive queries for hierarchical identities id = (id 1 , . . . , id )

(where hierarchical identities are encoded as hierarchical vectors ( X 1 , . . . , X )).

-Create-key: A provides id and the challenger C creates a private key SK id by running HIB-DE.Kg(pms, msk, id). The list QS is updated as QS = QS ∪ {id}. -Create-delegated-key: A provides id = (id 1 , . . . , id ) and id +1 such that id ∈ QS. The challenger C then computes SK id for id = (id 1 , . . . , id +1 ) by running the delegation algorithm HIB-DE.Del pms, mpk β , SK id , id +1 . The list QS is updated as QS = QS ∪ {id }. -Reveal-key: A provides id with the restriction that if A is selective, then id ≤ id † . C returns ⊥ if id ∈ QS. Otherwise, SK id is returned to A and the list IS is updated as IS = IS ∪ {id}.

3.

The adversary A outputs a hierarchical identity id = (id 1 , . . . , id ). In the selective setting, we impose = † and id j = id † j for each j ∈ {1, . . . , }. In the adaptive case, no element of IS is a prefix of id . 4. The challenger encrypts a message m sampled from the given message distribution M . The resulting ciphertext is sent to A. 5. A outputs a bit b ∈ {0, 1}, which is the output of the experiment.

Recall that a random variable X over {0, 1} s is called a (t, s)-source if H ∞ (X) ≥ t, where H ∞ (X) is the min-entropy of X; H ∞ (X) = -log(max x P X (x)). We now give the identity-based version of IND-PRIV1 security of [START_REF] Boldyreva | On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles[END_REF]. Definition 4. An s-bit encryption scheme HIB-DE is PRIV1-IND-ID secure for (t, s)-sources if for any (t, s)-sources M 0 and M 1 and all polynomial time adversaries A, the PRIV1-IND-ID advantage

of A against HIB-DE is negligible.

C.1 Universal HF implies deterministic encryption

As it can be seen from the definition, a hierarchical identity-based encryption scheme is very close to an HIB-TDF, even syntactically. Indeed, as shown in [START_REF] Boldyreva | On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles[END_REF], in the public key setting a natural way to construct a deterministic DE encryption scheme is by defining the algorithms of DE as their natural counterparts in some lossy LTDF. Boldyreva et al. [START_REF] Boldyreva | On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles[END_REF] show that if the lossy function is also universal, this construction is PRIV1-IND secure. For functions not satisfying this property, the result follows also directly by an extension of the Crooked Leftover Hash Lemma of Dodis and Smith [START_REF] Dodis | Entropic Security and the Encryption of High Entropy Messages[END_REF] given by Boldyreva et al. for this purpose. Similarly, in the identity-based setting, one can construct a hierarchical deterministic identity-based encryption scheme HIB-DE from HF, a lossy HIB-TDF, by defining the algorithms of HIB-DE from those of HF in the natural way (in this case, we say that HIB-DE is defined by HF). We will show that with the additional requirement of universality, such a construction is secure in some natural extension of PRIV1-IND security. To do without this extra condition, it is possible to use the same techniques of Boldyreva et al.. More specifically, universality requires that if LHF is the lossy sibling of a (ω, δ)-lossy HIB-TDF function, then HF.Setup, LHF.MKg and HF.Eval(pms, mpk, id , •) induce a universal hash function when we have a lossy function for id , i.e., λ HF.Eval pms, mpk 1 , (id 1 , . . . , id ), • ≥ ω. It is not difficult to see that both [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF] and our construction induce a universal hash in the lossy mode.

Theorem 5. If HF is a universal (ω, δ)-lossy HIB-TDF function with input {0, 1} n , then the hierarchical deterministic encryption function HIB-DE defined by it is secure for poly-time sampleable (t, s)-sources such that t ≥ n -ω + 2 log(1/ ) for some negligible . In particular, for any two (t, s)-sources M 0 and M 1 and for every PRIV1-IND-ID adversary B against HIB-DE there exists a PPT adversary A against HF such that Adv lossy HF,LHF,P,ω,ζ (A) ≥

Proof. We use similar ideas as those of [START_REF] Boldyreva | On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles[END_REF]. Namely, our proof goes as follows: assume that there is an adversary B that breaks PRIV1-ID-IND security of the deterministic encryption scheme. Namely, there exist two (t, s)-sources M 0 , M 1 and a non-negligible ζ such that

Then, we build an adversary A that breaks the security of the underlying HF, that is, A will interact with a challenger according to the lossy or the real experiment and will tell the difference between both scenarios with non-negligible probability.

A forwards an identity id † to its challenger, which is some random identity in the adaptive case. When the challenger runs the setup and gives the output to A, A forwards this information to B. When B asks for a secret key for a hierarchical identity id, A forwards the query to the experiment and forwards the reply to B. At some point, B outputs id . Adversary A then forwards id to its challenger, chooses γ ← {0, 1} at random and encrypts m γ R ← M γ under the identity id . Note that this corresponds to an execution of Guess B HIB-DE (M γ ). After some more secret key queries, B outputs a bit γ ∈ {0, 1} and A outputs d A = 1 if γ = γ and d A = 0 otherwise.

The security analysis is very similar to the one in Section 2.2. A simple argument shows that

since A perfectly simulated the experiment Guess B HIB-DE (M γ ) with B. On the other hand, in the LOSSY setting when id is lossy, the advantage of B in guessing γ is negligible because the universality property means that the output distribution of the encryption algorithm is independent of the input distribution, and this holds regardless of whether d A ¬abort = 1, therefore:

for some negligible ν. At this point the analysis follows as in the analysis of the IND-ID-CPA case (proof of Theorem 1).

Related Work

In a recent, independent work [START_REF] Xie | Deterministic Public Key Encryption and Identity-Based Encryption from Lattices in the Auxiliary-Input Setting[END_REF], Xie, Xue and Zhang gave a lattice-based deterministic IBE construction in the auxiliary input setting [START_REF] Brakerski | Better Security for Deterministic Public-Key Encryption: The Auxiliary-Input Setting[END_REF]. While their scheme does provide adaptive security in the auxiliary input setting, it was described as a single-level IBE. Our results are incomparable to theirs: on one hand, we do not consider auxiliary inputs; on the other hand, we are concerned with pairing-based schemes in a hierarchical setting and focus on a more powerful primitive.

D On Hedged (H)IBE

Bellare et al. [START_REF] Bellare | Hedged Public-Key Encryption: How to Protect against Bad Randomness[END_REF] studied the problem of designing hedged public key encryption schemes, which remain secure even if the randomness used for encryption is relatively bad. They consider two notions of hedged security: non-adaptive and adaptive. A non-adaptive attacker can make only a single challenge encryption query, whereas an adaptive attacker can make up to q challenge adaptive encryption queries, all of them for the same public key. Bellare et al. give in [START_REF] Bellare | Hedged Public-Key Encryption: How to Protect against Bad Randomness[END_REF] different constructions of public key encryption scheme enjoying nonadaptive hedged security. For instance, their construction RtD combines an IND-CPA secure encryption scheme and a deterministic PRIV1-IND secure encryption scheme to achieve non-adaptive hedged security. Then they prove a general result stating that a public key encryption scheme which enjoys both anonymity and non-adaptive hedged security, already enjoys adaptive hedged security. They show how to provide the necessary anonymity property by using universal lossy trapdoor functions.

The notion of non-adaptive hedged security, with only one challenge encryption query, can be easily extended to the identity-based setting, as well as the non-adaptively secure constructions in [START_REF] Bellare | Hedged Public-Key Encryption: How to Protect against Bad Randomness[END_REF]. In particular, since our new notion of partial lossiness for (H)IB-TDFs implies both IND-CPA secure IBE and PRIV1-IND secure (H)IB deterministic encryption, we have that the existence of (H)IB-TDFs enjoying partial lossiness implies (through the identity-based version of RtD) nonadaptive hedged (H)IBE secure against adversaries who choose the challenge identity in an adaptive way.

Regarding the notion of adaptive hedged security, the extension to the identity-based setting is more challenging, because the adversary could choose different identities for each of the q challenge adaptive encryption queries. The partial lossiness definitions in [START_REF] Bellare | Identity-Based (Lossy) Trapdoor Functions and Applications[END_REF] and in this paper do not seem to imply any positive result in that case, because these definitions consider only one challenge (lossy) identity. Maybe more general definitions for the partial lossiness notion of (H)IB-TDFs are needed to overcome this obstacle, in the line of all-but-N trapdoor functions [START_REF] Hemenway | Lossy encryption: constructions from general assumptions and efficient selective opening chosen ciphertext security[END_REF] and all-but-many trapdoor functions [START_REF] Hofheinz | All-But-Many Lossy Trapdoor Functions[END_REF]. We leave the problem of designing (H)IBE schemes with adaptive hedged security as an interesting open problem.