CS395T Advanced Cryptography 2/05/09Lecture 6: Boneh-Boyen IBEInstructor: Brent Waters Scribe: Jimmy Yang1 ReviewHere’s another way to think about the encryption/decryption operations in Boneh-Franklin:e(H(ID), gy)s= e(H(ID)y, gs)The left side corresponds to computing the blinding factor during encryption, and theright side corresponds to computing the blindin g factor during decryption. During encryp -tion, s is known, but we can only make use of y through gy. During decryption, we no longerknow s, bu t we are able to compute the same blinding factor by pairing gsand H(ID)y,namely, e(H(ID), g)ys.To finish off, we show the success probability of breaking decisional-BDH, given an IBEattacker with advantage ǫ.P r[success] = P r[success|abort]P r[abort] + P r[success|abort]P r[abort]=121 −1QH+ P r[abort]12P r[success|abort ∧ γ = 0] +12P r[success|abort ∧ γ = 1]=121 −1QH+1QH1212+ ǫ+12·12=12+ǫ2QHWhere QHis the number of key generation queries the attacker makes. Note that whenwe have guessed the wrong ID the attacker tries to attack, or when γ = 1 (the attacker isnot given a valid encryption), the probability of success is set to 1/2.2 Aside: Random OraclesWhy are random oracles used in cryptography? Clearly they do not correspond toanything in real life. One reason they are useful is that they are stepping stones towardscreating systems that do not m ake use of random oracles (as we will see, the next IBEsystem does not invoke them). Often, proofs in the random oracle model are simpler thanproofs without them. Lastly, many systems used in practice (eg: SSL, PGP) are actuallyshown to be secure only in the random oracle mo del. When considering proofs of security,one should always be aware of the risks in using random oracles.6-13 Boneh-Boyen IBE [BB04]The first step towards IBE without random oracles was given by Dan Boneh and XavierBoyen in 2004. The security game they use, called Selective-ID, has the following modifi-cation: the attacker specifies beforehand which ID she plans to attack. Thus, before seeingthe IBE’s public parameters or the keys for any IDs, the attacker announces which ID shewill use when requesting the encryption of M0or M1.3.1 Algorithms• Setup(λ)– randomly pick g, h ∈ G, and a, b ∈ Zp– the public parameters are: g, h, u = ga, e(g, g)ab(and the hash function f )– let the hash function f : Zp→ G be defined as f (ID) = uID· h– the master secret key is gab• KeyGen(ID, MSK)– randomly pick r ∈ Zp– KID= (K1, K2) = (gab· f (ID)r, gr)– think of this as encrypting the MSK using the secret f(ID)r• En cryption(P P, M, ID)– randomly pick s ∈ Zp– CT = (C0, C1, C2) = (M · (e(g, g)ab)s, gs, f(ID)s)• Decryption(KID, CT )– M = C0· e(K1, C1)−1· e(K2, C2)– This requires a bit of explanation. Note that in order to recover the plaintextM, one must be able to compute the blind e(g , g)abs. Consider the computationof e(K1, C1):e(K1, C1) = e(gab· f(ID)r, gs)= e(gab, gs) · e(f(ID)r, gs)= e(g, g)abs· e(f(ID), g)rsThis gives us the blind... if we could compute e(f(ID), g)rs. However, that isnot hard because e(K2, C2) = e(gr, f(ID)s) = e(g, f (ID))rs.6-23.2 Randomness necessary for KeyGen?Here we argue that it is important to choose a fresh random r for each KeyGen operation.Consider what happens if we use the same ˜r each time. Suppose we have 2 keys KIDalice=(gab(uIDalice· h)˜r, g˜r) and KIDbob= (gab(uIDbob· h)˜r), g˜r). If we divide the first element ofBob’s key into Alice’s key, we get u(IDalice−IDbob)· ˜r. By raising this value to1IDalice−IDbob,we obtain u˜r. This can be multiplied into KIDto obtain a valid key for ID + 1. (Do yousee how to obtain a valid key for any ID?)In the next lecture, we show how to rerandomize keys. T hat is, given a valid key, producethe same valid key u nder a different randomness without using knowledge of any secret.3.3 Proof of SecurityAs with Boneh-Franklin, the proof of security is with respect to decisional-BDH.Theorem 3.1 (Boneh-Boyen IBE) decisional-BDH is hard ⇒ Boneh-Boyen IBE is CPAselective-ID secureAs usual, the proof is by contradiction. We show that an attacker who can break Boneh-Boyen IBE with ǫ advantage can be used to distinguish decisional-BDH with non-negligibleprobability. The reduction (roughly) pr oceeds as follows:• Receive the decisional-BDH challenge: g, ga, gb, gc, T , where T = e(g, g)abcwhen γ = 0and T = random when γ = 1• Since this is the selective-ID mod el, the IBE attacker now announces ID⋆, the ID shewishes to attack.• The next step is to simulate the Setup ph ase for the attacker, which requires carefulconsideration. We need to not only utilize the decisional-BDH parameters, but alsoID⋆. Otherwise, we aren’t r eally using the attacker’s power to help us solve thedecisional-BDH ins tance.Here is one possible setup: u = ga, h = u−ID⋆, e(g, g)ab= e(ga, gb).Under this setting, applying the hash function to ID⋆yields f(ID⋆) = uID⋆·u−ID⋆=1. This is a prob lem because had g, h, a (and thus u) been chosen randomly as specifiedby the setup algorithm, it is unlikely that ID⋆hashes to th e identity element. Thus,there is n o guarantee that our IBE attacker will still work correctly with ǫ ad vantage.It turns out we just need to add a blind to h. Randomly pick y ∈ Zp, and use thefollowing: u = ga, h = u−ID⋆· gy, e(g, g)ab= e(ga, gb).In this case, f (ID⋆) = gy(which is random), while for ID 6= ID⋆we have f(ID) =uID−ID⋆· gy.• The next step to consider is KeyGen. This is not trivial because we need to be ableto generate valid keys without knowing a or b. Consider what happens if we were touse r =−bID−ID⋆(we can’t actually compute this directly, because we don’t know b):6-3K1= gab· f (ID)r= gab·uID· u−ID⋆· gy−bID−ID⋆= gab· g−ab· g−byID−ID⋆= (gb)−yID−ID⋆K2can be computed as gr= g−bID−ID⋆= (gb)−1ID−ID⋆.Since we can compute−yID−ID⋆and−1ID−ID⋆, we are able to generate these keys underthe randomness r =−bID−ID⋆. However, we h ave the same problem as in the Setupphase: there is no inherent randomness in our values of r! The solution is simple: weactually use r =−bID−ID⋆+ ˜r, where ˜r is fresh randomness chosen f or each ID.• The last important step is to send proper parameters to the attacker when she requeststhe encryption of M0or M1.In the next lecture we will finish the
View Full Document
Unlocking...