We present an identity-based cryptosystem that features fully anonymous ciphertexts and hierarchical key delegation. We give a proof of security in the standard model, based on the mild Decision Linear complexity assumption in bilinear groups. The system is efficient and practical, with small ciphertexts of size linear in the depth of the hierarchy. Applications include search on encrypted data, fully private communication, etc. Our results resolve two open problems pertaining to anonymous identity-based encryption, our scheme being the first to offer provable anonymity in the standard model, in addition to being the first to realize fully anonymous HIBE at all levels in the hierarchy. The cryptographic primitive of identity-based encryption allows a sender to encrypt a message for a receiver using only the receiver's identity as a public key. Recently, there has been interest in "anonymous" identity-based encryption systems, where the ciphertext does not leak the identity of the recipient. In addition to their obvious privacy benefits, anonymous IBE systems can be leveraged to construct Public key Encryption with Keyword Search (PEKS) schemes, as was first observed by Boneh et al. [10] and later formalized by Abdalla et al. [1] . Roughly speaking, PEKS is a form of public key encryption that allows an encryptor to make a document serarchable by keywords, and where the capabilities to search on particular keywords are delegated by a central authority. Anonymous HIBE further enables sophisticated access policies for PEKS and ID-based PEKS. Prior to this paper, the only IBE system known to be inherently anonymous was that of Boneh and Franklin [11] . Although they did not state it explicitly, the anonymity of their scheme followed readily from their proof of semantic security. One drawback of the Boneh-Franklin IBE paradigm is that its security proofs are set in the random oracle model. More recently, efficient IBE schemes due to Boneh and Boyen [5] and Waters [29] have been proven secure outside of the random oracle model, but these schemes are not anonymous when implemented using "symmetric" bilinear pairings e : G × G → G T , because one can test if a given ciphertext was encrypted for a candidate identity. In retrospect, one notes that with minor modifications Boneh and Boyen's two schemes * Voltage Inc., Palo Alto -xb@boyen.org † SRI International -bwaters@csl.sri.com 1 "BB 1 " and "BB 2 ", and Waters' by extension, may in fact become anonymous when implemented with an "asymmetric" pairing e : G ×Ĝ → G T under strong additional assumptions (such as hardness of DDH in G), but this is not easy to prove. Furthermore, for a fundamental reason this observation applies only to non-hierarchical IBE, and it would be nice not to rely on such "risky" assumptions which are patently false in the symmetric setting. At any rate, and even if one were to consider the use of random oracles, there simply does not exist any known hierarchical identity-based encryption scheme which is also anonymous. (In particular, the Gentry-Silverberg [19] HIBE scheme is not.) In their recent CRYPTO'05 paper, Abdalla et al. [1] cite the creation of an anonymous IBE system without random oracles and an anonymous HIBE system with or without random oracles as important open problems. We present an Anonymous IBE and HIBE scheme without random oracles, therby solving both open problems from CRYPTO'05. Our scheme is very efficient for pure IBE, and reasonably efficient for HIBE with shallow hierarchies of practical interest. We prove it secure based solely on Boneh's et al. [9] Decision Linear assumption, which is one of the mildest useful complexity assumptions in bilinear groups. At first sight, our construction bears a superficial resemblance to Boneh and Boyen's "BB 1 " HIBE scheme [5, §4] -but with at least two big differences. First, we perform "linear splittings" on various portions of the ciphertext, to thwart the trial-and-error identity guessing to which other schemes fell prey. This idea gives us provable anonymity, even under symmetric pairings. Second, we use multiple parallel HIBE systems and constantly re-randomize the keys between them. This is what lets us use the linear splitting trick at all levels of the hierarchy, but also poses a technical challenge in the security reduction which mist now simulate multiple interacting HIBE systems at once. Solving this problem was the crucial step that gave us a hierarchy without destroying anonymity. Building a "flat" anonymous IBE system turns out to be reasonably straightforward using our linear splitting technique to hide the recipient identity behind some randomization. Complications arise when one tries to support hierarchical key generation. In a nutshell, to prevent collusion attacks in HIBE, "parents" must independently re-randomize the private keys they give to their "children". In all known HIBE schemes, re-randomization is enabled by a number of supplemental components in the public system parameters. Why this breaks anonymity is because the same mechanism that allows private keys to be publicly re-randomized, also allows ciphertexts to be publicly tested for recipient identities. Random oracles offer no protection against this. To circumvent this obstable, we need to make the re-randomization elements non-public, and tie them to each individual private key. In practical terms, this means that private keys must convey extra components (although not too many). The real difficulty is that each set of re-randomization components constitutes a full-fledged HIBE in its own right, which must be simulated together with its peers in the security proof (their number grows linearly with the maximal depth). Because these systems are not independent but interact with each other, we are left with the task of simulating multiple HIBE subsystems that are globally constrained by a set of linear relations. A novelty of our proof technique is a method to endow the simulator with enough degrees of freedom to reduce a system of unknown keys to a single instance of the presumed hard problem. A notable feature of our construction is that it can be implemented using all known instantiations of the bilinear pairing (whether symmetric or asymmetric, with our without a computable or 2 invertible homomorphism, etc.). To cover all grounds, we describe both a symmetric IBE version for simplicitly, and a fully general asymmetric HIBE without homomorphisms for generality. The concept of identity-based encryption was first proposed by Shamir [26] two decades ago. However, it was not until much later that Boneh and Franklin [11] and Cocks [17] presented the first practical solutions. The Boneh-Franklin IBE scheme was based on groups with efficiently computable bilinear maps, while the Cocks scheme was proven secure under the quadratic residuosity problem, which relies on the hardness of factoring. The security of either scheme was only proven in the random oracle model. Canetti, Halevi, and Katz [14] suggested a weaker security notion for IBE, known as selective identity or selective-ID, relative to which they were able to build an inefficient but secure IBE scheme without using random oracles. Boneh and Boyen [5] presented two very efficient IBE systems ("BB 1 " and "BB 2 ") with selective-ID security proofs, also without random oracles. The same authors [6] then proposed a coding-theoretic extension to their "BB 1 " scheme that allowed them to prove security for the full notion of adaptive identity or adaptive-ID security without random oracles, but the construction was impractical. Waters [29] then proposed a much simpler extension to "BB 1 " also with an adaptive-ID security proof without random oracles; its efficiency was further improved in two recent independent papers, [16] and [24] . The notion of hierarchical identity-based encryption was first defined by Horwitz and Lynn [20] , and a construction in the random oracle model given by Gentry and Silverberg [19] . The first HIBE scheme to be provably secure without random oracles is the "BB 1 " system of Boneh and Boyen; subsequent improvements include the HIBE scheme by Boneh, Boyen, and Goh [7] , which features shorter ciphertexts and private keys. We note that the selective-ID vs. adaptive-ID distinction is not very important for any of the HIBE systems known to date, since in all of them the adaptive-ID security degrades exponentially with the depth of the hierarchy: the two models are equivalent up to a constant factor inside the exponential. An important open problem in identity-based cryptography is to devise an adaptive-ID secure HIBE scheme whose security degrades polynomially with the depth of the hierarchy (under reasonable assumptions). Song, Wagner, and Perrig [28] presented the first scheme for searching on encrypted data. Their scheme is in the symmetric-key setting where the same party that encrypted the data would generate the keyword search capabilities. Boneh et al. [10] introduced Public Key Encryption with Keyword Search (PEKS), where any party with access to a public key could make an encrypted document that was searchable by keyword; they realized their construction by applying the BonehFranklin IBE scheme. Abdalla et al. [1] recently formalized the notion of Anonymous IBE and its relationship to PEKS. Additionally, they formalized the notion of Anonymous HIBE and mentioned different applications for it. Using the GS system as a starting point, they also gave an HIBE scheme that was anonymous at the first level, in the random oracle model. Another view of Anonymous IBE is as a combination of identity-based encryption with the property of key privacy, which was introduced by Bellare et al. [4]. In this section we discuss various applications of our fully anonymous HIBE system. The main applications can be split into several broad categories. Fully Private Communication. The first compelling application of anonymous IBE is for fully private communication. Bellare et al. [4] argue that public key encryption systems that have the "key privacy" property can be used for anonymous communication: for example, if one wishes to hide the identity of a recipient one can encrypt a ciphertext with an anonymous IBE system and post it on a public bulletin board. By the anonymity property, the ciphertext will betray neither sender nor recipient identity, and since the bulletin board is public, this method will also be resistant to traffic analysis. To compound this notion of key privacy, identity-based encryption is particularly suited for untraceable anonymous communication, since, contrarily to public-key infrastructures, the sender does not even need to query a directory for the public key of the recipient. For this reason, anonymous IBE provides a very convincing solution to the problem of secure anonymous communication, as it makes it harder to conduct traffic analysis attack on directory lookups. Search on Encrypted Data. The second main application of anonymous (H)IBE is for encrypted search. As mentioned earlier, anonymous IBE and HIBE give several application in the Public-key Encryption with Keyword Search (PEKS) domain, proposed by Boneh et al. [10], and further discussed by Abdalla et al. [1] . As a simple example of real-world application of our scheme, PEKS is a useful primitive for building secure audit logs [30, 18] . Furthermore, one can leverage the hierarchical identities in our anonymous HIBE in several interesting ways. For example, we can use a two-level anonymous HIBE scheme where the first level is an identity and the second level is a keyword. This gives us the first implementation of the Identity-Based Encryption with Keyword Search (IBEKS) primitive asked for in [1] . With this primitive, someone with the private key for an identity can delegate out search capabilities for encryptions to their identity, without requiring a central authority to act as the delegator. Conversely, by using certain keywords such as "Top Secret" at the first level of the hierarchy, it is possible to broadcast innocent-looking ciphertexts that require a certain clearance to decrypt, without even hinting at the fact that their payload might be valuable. We can create more refined search capabilities with a deeper hierarchy. As the last applications we mention, forward-secure public-key encryption [14] and forwardsecure HIBE [31] are straightforward to construct from HIBE systems [31, 7] . We can implement Anonymous fs-HIBE with our scheme by embedding a time component within the hierarchy, while preserving the anonymity property. Recall that a pairing is an efficiently computable [23], non-degenerate function, e : G ×Ĝ → G T , with the bilinearity property that e(g r ,ĝ s ) = e(g,ĝ) r s . Here, G,Ĝ, and G T are all multiplicative groups of prime order p, respectively generated by g,ĝ, and e(g,ĝ). We assume an efficient generation procedure that on input a security parameter Σ ∈ N outputs G $ ← Gen(1 Σ ) where log 2 (p) = Θ(Σ). We write Z p = Z/pZ for the set of residues modp and Z × p = Z p \ {0} for its multiplicative group. Since bilinear groups first appeared in cryptography half a decade ago [21] , several years after their first use in cryptanalysis [22] , bilinear maps or pairings have been used in a large variety of ways under many different complexity assumptions. Some of them are very strong; others are weaker. Informally, we say that an assumption is mild if it is tautological in the generic group model [27] , and also "efficiently falsifiable" [25] in the sense that its problem instances are stated non-interactively and concisely (e.g., independently of the number of adversarial queries or such large quantity). Most IBE and HIBE schemes mentioned in Introduction (except "BB 2 " and the Factoring-based system by Cocks) are based on mild bilinear complexity assumptions, such as BDH [21, 11] and Linear [9] . In this paper, our goal is to rely only on mild assumptions. Decision BDH: The Bilinear DH assumption was first used by Joux [21] , and gained popularity for its role in the Boneh-Franklin IBE system [11] . The decisional assumption posits the hardness of the D-BDH problem, which we state in asymmetric bilinear groups as: Decision Linear: The Linear assumption was first proposed by Boneh, Boyen, and Shacham for group signatures [9] . Its decisional form posits the hardness of the D-Linear problem, which can be stated in asymmetric bilinear groups as follows: "Hard" means algorithmically non-solvable with probability 1 /2 + Ω(poly(Σ) −1 ) in time O(poly(Σ)) for efficiently generated random "bilinear instances" These assumptions allow but not require the groups G andĜ to be distinct, and similarly we make no representation one way or the other regarding the existence of computable homomorphisms between G andĜ, in either direction. This is the most general formulation. It has two main benefits: (1) since it comes with fewer restrictions, it is potentially more robust and increases our confidence in the assumptions we make; and (2) it gives us the flexibility to implement the bilinear pairing on a broad variety of algebraic curves with attractive computational characteristics [2], whereas symmetric pairings tend to be confined to supersingular curves, to name this one distinction. Note that if we let G =Ĝ and g =ĝ, our assumptions regain their familiar "symmetric" forms: As a rule of thumb, the remainder of this paper may be read in the context of symmetric pairings, simply by dropping all "hats" (ˆ) in the notation. Also note that D-Linear trivially implies D-BDH. We briefly precise the security notions that are implied by the concept of Anonymous IBE or HIBE. We omit the formal definitions, which may be found in the literature [11, 1] . Confidentiality: This is the usual security notion of semantic security for encryption. It means that no non-trivial information about the message can be feasibly gleaned from the ciphertext. Anonymity: Recipient anonymity is the property that the adversary be unable to distinguish the encryption of a chosen message for a first chosen identity from the encryption of the same message for a second chosen identity. Equivalently, the adversary must be unable to decide whether a ciphertext was encrypted for a chosen identity, or for a random identity. 5 Before we present our scheme we first explain why it is difficult to implement anonymous IBE without random oracles, as well as any form of anonymous HIBE even in the random oracle model. We also give some intuition behind our solution. Recall that in the basic Boneh-Franklin IBE system [11] , an encryption of a message Msg to some identity Id, takes the following form, where H is a random oracle, r is a random exponent, and g and Q are public system parameters. A crucial observation is that the one element of the ciphertext in the bilinear group G, namely, g r , is just a random element that gives no information about the identity of the recipient. The reason why only one element in G is needed is because private keys in the Boneh-Franklin scheme are deterministic -there will be no randomness in the private key to cancel out. Since the proof of semantic security is based on the fact that C 2 is indistinguishable from random without the private key for ID, it follows that the scheme is also anonymous since C 2 is the only part of the ciphertext on which the recipient identity has any bearing. More recently, there have been a number of IBE schemes proven secure without random oracles, such as BTE from [14] , BB 1 and BB 2 from [5] , and Waters' [29]. However, in all these schemes the proof of security requires that randomness be injected into the private key generation. Since the private keys are randomized, some extra information is needed in the ciphertext in order to cancel out the randomness upon decryption. To illustrate, consider the encryption of a message Msg to an identity Id in the BB 1 Boneh-Boyen system, where r is chosen by the encryptor and g, g 1 , g 3 , and e(g 1 ,ĝ 2 ) are public system parameters. Notice, there are now two elements in G, and between them there is enough redundancy to determine whether a ciphertext was intended for a given identity Id, simply by testing whether the tuple [g, g Id 1 g 3 , C 1 , C 2 ] is Diffie-Hellman, using the bilinear map, We see that the extra ciphertext components which are seemingly necessary in IBE schemes without random oracles, in fact contribute to leaking the identity of the intended recipient of a ciphertext. A similar argument can be made for why existing HIBE schemes are not anonymous, regardless of their lack of use of random oracles. Indeed, all known HIBE schemes, including the GentrySilverberg system in the random oracle model, rely on randomization in order to properly delegate private keys down the hierarchy in a collusion-resistant manner. Because of this, we similarly have the property that the extra components needed to cancel the randomization will also provide a test for the addressee's identity. Since having randomized keys seems to be fundamental to designing (H)IBE systems without random oracles, we aim to design a system where the necessary extra information will be hidden to a computationally bounded adversary. Thus, even though we cannot prevent the ciphertext from containing information about the recipient, we can design our system such that this information cannot be easily tested from the public parameters and ciphertext alone.  We start by describing an Anonymous IBE scheme that is semantically secure against selective-ID chosen plaintext attacks. This construction will illustrate our basic technique of "splitting" the bilinear group elements into two pieces to protect against the attacks described in the previous section. In the next section we will describe our full Anonymous HIBE scheme, as well as mention how to achieve adaptive-ID and chosen ciphertext security. For simplicity, and also to show that we get anonymity even when using symmetric pairings, we describe the IBE system (and the IBE system only) in the special case where G =Ĝ: Setup The setup algorithm chooses a random generator g ∈ G, random group elements g 0 , g 1 ∈ G, and random exponents ω, t 1 , t 2 , t 3 , t 4 ∈ Z p . It keeps these exponents as the master key, Msk. The corresponding system parameters are published as: Extract(Msk, Id) To issue a private key for identity Id, the key extraction authority chooses two random exponents r 1 , r 2 ∈ Z p , and computes the private key, , as: Encrypt(Pub, Id, M ) Encrypting a message Msg ∈ G T for an identity Id ∈ Z × p works as follows. The algorithm chooses random exponents s, s 1 , s 2 ∈ Z p , and creates the ciphertext as: Decrypt(Pvk Id , C) The decryption algorithm attempts to decrypt a ciphertext CT by computing: Proving Security. We prove security using a hybrid experiment. Let [C ′ , C 0 , C 1 , C 2 , C 3 , C 4 ] denote the challenge ciphertext given to the adversary during a real attack. Additionally, let R be a random element of G T , and R ′ , R ′′ be random elements of G. We define the following hybrid games which differ on what challenge ciphertext is given by the simulator to the adversary: We remark that the challenge ciphertext in Γ 3 leaks no information about the identity since it is composed of six random group elements, whereas in Γ 0 the challenge is well formed. We show that the transitions from Γ 0 to Γ 1 to Γ 2 to Γ 3 are all computationally indistinguishable. Lemma 1 (semantic security). Under the (t, ǫ)-Decision BDH assumption, there is no adversary running in time t that distinguishes between the games Γ 0 and Γ 1 with advantage greater than ǫ. Proof. The proof from this lemma essentially follows from the security of the Boneh-Boyen selective-ID scheme. Suppose there is an adversary that can distingiush between game Γ 0 and Γ 1 with advantage ǫ. Then we build a simulator that plays the Decison BDH game with advantage ǫ. The simulator receives a D-BDH challenge [g, g z 1 , g z 2 , g z 3 , Z] where Z is either e(g, g) z 1 z 2 z 3 or a random element of G T with equal probability. The game proceeds as follows: ⋄ Init: The adversary announces the identity Id * it wants to be challenged upon. ⋄ Setup: The simulator chooses random exponents t 1 , t 2 , t 3 , t 4 , y ∈ Z p . It retains the generator g, and sets g 0 = (g z 1 ) −Id g y and g 1 = g z 1 . The public parameters are published as: Note that this implies that ω = z 1 z 2 . ⋄ Phase 1: Suppose the adversary requests a key for identity Id = Id * . The simulator picks random exponents r 1 , r 2 ∈ Z p , and issues a private key as: This is a well formed secret key for random exponentsr 1 = r 1 − z 2 /(Id − Id * ) andr 2 = r 2 . ⋄ Challenge: Upon receiving a message Msg from the adversary, the simulator chooses s 1 , s 2 ∈ Z p , and outputs the challenge ciphertext as: We can let s = z 3 and see that if Z = e(g, g) z 1 z 2 z 3 the simulator is playing game Γ 0 with the adversary, otherwise the simulator is playing game Γ 1 with the adversary. The simulator answers the queries in the same way as Phase 1. ⋄ Guess: The simulator outputs a guess γ, which the simulator forwards as its own guess for the D-BDH game. Since the simulator plays game Γ 0 if and only the given D-BDH instance was well formed, the simulator's advantage in the D-BDH game is exactly ǫ. Lemma 2 (anonymity, part 1). Under the (t, ǫ)-Decision linear assumption, no adversary that runs in time t can distinguish between the games Γ 1 and Γ 2 with advantage greater than ǫ. Proof. Suppose the existence of an adversary A that distinguishes between the two games with advantage ǫ. Then we construct a simulator that wins the Decision Linear game as follows. The simulator takes in a D-Linear instance [g, g z 1 , g z 2 , g z 1 z 3 , g z 2 z 4 , Z], where Z is either g z 3 +z 4 or random in G with equal probability. For convenience, we rewrite this as [g, g z 1 , g z 2 , g z 1 z 3 , Y, g s ] for s such that g s = Z, and consider the task of deciding whether Y = g z 2 (s−z 3 ) which is equivalent. The simulator plays the game in the following stages. ⋄ Init: The adversary A gives the simulator the challenge identity Id * . ⋄ Setup: The simulator first chooses random exponents α, y, t 3 , t 4 , ω. It lets g in the simulation be as in the instance, and sets v 1 = g z 2 and v 2 = g z 1 . The public key is published as: 8 If we pose t 1 = z 1 and t 2 = z 2 , we note that the public key is distributed as in the real scheme. ⋄ Phase 1: To answer a private key extraction query for an identity Id = Id * , the simulator chooses random exponents r 1 , r 2 ∈ Z p , and outputs a key given by: If, instead of r 1 and r 2 , we consider this pair of uniform random exponents, then we see that the private key is well formed, since it can be rewritten as: −r 2 t 3 . ⋄ Challenge: The simulator gets from the adversary a message M which it can discard, and responds with a challenge ciphertext for the identity Id * . Pose s 1 = z 3 . To proceed, the simulator picks a random exponent s 2 ∈ Z p and a random element R ∈ G T , and outputs the ciphertext as: 2 ; all parts of the challenge but C ′ are thus well formed, and the simulator behaved as in game Γ 1 . If instead Y is independent of z 1 , z 2 , s, s 1 , s 2 , which happens when Z is random, then the simulator responded as in game Γ 2 . ⋄ Phase 2: The simulator answer the query in the same way as Phase 1. ⋄ Output: The adversary outputs a bit γ to guess which hybrid game the simulator has been playing. To conclude, the simulator forwards γ as its own answer in the Decision-Linear game. By the simulation setup the advantage of the simulator will be exactly that of the adversary. Lemma 3 (anonymity, part 2). Under the (t, ǫ)-Decision linear assumption, no adversary that runs in time t can distinguish between the games Γ 2 and Γ 3 with advantage greater than ǫ. Proof. This argument follows almost identically to that of Lemma 2, except where the simulation is done over the parameters v 3 and v 4 in place of v 1 and v 2 . The other difference is that the g ω term that appeared in d 1 , d 2 without interfering with the simulation, does not even appear in d 3 , d 4 . The Scheme : Anonymous HIBE We now describe our full Anonymous HIBE scheme without random oracles. Anonymity is provided by the splitting technique and hybrid proof introduced in the previous section. In addition, to thwart the multiple avenues for user collusion enabled by the hierarchy, the keys are re-randomized between all siblings and all children. Roughly speaking, this is done by using several parallel HIBE systems, which are recombined at random every time a new private key is issued. In the proof of security, this extra complication is handled by a "multi-secret simulator", that is able to simulate multiple interacting HIBE systems under a set of constraints. This is an information theoretic proof that sits on top of the hybrid argument, which is computational. For the most part, we focus on security against selective-identity, chosen plaintext attacks. In Appendix A we mention how to secure the scheme against adaptive-ID and CCA2 adversaries. Setup(1 Σ , D) To generate the public system parameters and the corresponding master secret key, given a security parameter Σ ∈ N in unary, and the hierarchy's maximum depth D ∈ N, the setup algorithm first generates a bilinear instance 1. Select 7 + 5 D + D 2 random integers modulo p (some of them forcibly non-zero): 2. Publish G and the system parameters Pub ∈ G T × G 2 (1+D) (2+D) given by: 3. Retain the master secret key Msk ∈Ĝ 1+(3+D) (2+D) comprising the elements: Extract(Pub, Msk, Id) To extract a private key for an identity Id where L ∈ {1, . . . , D} and by convention I 0 = 1, using the master key Msk: 3. The re-randomization part: Pvk The full private key is issued as the concatenation: Pvk Id = Pvk  Each row on the left can be viewed as a private key in an independent HIBE system (with generalized linear splitting as in Section 4). The main difference is that only Pvk  where L ∈ {2, . . . , D} and I 0 = 1, given a private key of the parent. Let that be 2. Compute for the decryption portion: . 3. For re-randomization: Pvk . The subordinate private key is the concatenation: Derive and Extract create private keys with the same structure and distribution. The derivation process in Derive merges two distinct operations: delegation and re-randomization. -Re-randomization occurs first, conceptually speaking. Very simply, we take a random linear combination of all the rows of the big array on page 10. The first row is treated a bit differently: it does not intervene into any other row's re-randomization, and its own coefficient is set to 1. -Delegation targets the leftmost elements of Pvk  We now turn to the encryption and decryption methods. Encrypt(Pub, Id, Msg) To encrypt a message encoded as a group element Msg ∈ G T for a given identity Id = [I 0 (= 1), I 1 , . . . , I L ] at level L, the encryption algorithm proceeds as follows: ∈ G T × G 5+2 D . Encryption is very cheap with a bit of caching since the exponentiations bases never change. Decrypt(Pub, Pvk Id , CT) To decrypt a ciphertext CT, using (the decryption portion of) a private key Pvk (a) , k n,(b) ] n=0,...,1+D ] , the decryption algorithm outputs: Msg ← E · e(c 0 , k 0 ) 1+D n=0 e(c n,(a) , k n,(a) ) e(c n,(b) , k n,(b) ) ∈ G T . All the pairings in the product can be computed at once using the "multi-pairing" trick which is similar to multi-exponentiation. One can also exploit the fact that all the k ··· are fixed for a given recipient to perform advantageous pre-computations [3] . The following theorems show that extracted and delegated private keys are identically distributed, and that extraction, encryption, and decryption, are consistent. Proofs are given in Appendix B. Theorem 4. Private keys calculated by Derive and Extract have the same distribution. Theorem 5. The Anonymous HIBE scheme is internally consistent. We state the security theorems for the A-HIBE scheme. The reductions are essentially tight and hold in the standard model. Informal arguments and full proofs may be found in Appendix C. First, we show semantic security against a selective-identity, chosen plaintext adversary. Theorem 6 (Confidentiality). Suppose that G upholds the (τ, ǫ)-Decision BDH assumption. Then, against a selective-ID adversary that makes at most q private key extraction queries, the HIBE scheme of Section 5 is (q,τ ,ǫ)-IND-sID-CPA secure in G withτ ≈ τ andǫ = ǫ−(3 + D) q/p. The next theorem shows that the scheme is recipient anonymous under a selective identity, chosen plaintext attack. (Sender anonymity is a trivial property of unauthenticated encryption.) Theorem 7 (Anonymity). Suppose that G upholds the (τ, ǫ)-Decision Linear assumption. Then, against a selective-ID adversary that makes q private key extraction queries, the HIBE scheme of Section 5 is (q,τ ,ǫ)-ANON-sID-CPA secure in G withτ ≈ τ andǫ = ǫ − (2 + D) (7 + 3 D) q/p. Active Attacks. We mention how to secure the scheme against active adversaries -in the adaptive identity (ID) and the adaptive chosen ciphertext (CCA2) attack models -in Appendix A. 12 We presented a provably anonymous IBE and HIBE scheme without random oracles, which resolves an open question from CRYPTO 2005 regarding the existence of anonymous HIBE systems. Our constructions make use of a novel "linear-splitting" technique which prevents an attacker from testing the intended recipient of ciphertexts yet allows for the use of randomized private IBE keys. In the hierarchical case, we add to this a new "multi-simulation" proof device that permits multiple HIBE subsystems to concurrently re-randomize each other. Security is based solely on the Linear assumption in bilinear groups. Our basic scheme is very efficient, within a factor two of (non-anonymous) Boneh-Boyen, and much faster than Boneh-Franklin encryption. The full hierarchical scheme remains practical with its quadratic private key size, and its linear ciphertext size, encryption time, and decryption time, as functions of the depth of the hierarchy.
Boyen and Waters constructed the first anonymous HIBE scheme REF .
Anonymous Hierarchical Identity-Based Encryption (without Random Oracles)
In CRYPTO
Computer Science