φ

· e(g β , g γ )s · e(g δ , g ξ )s · e(g δ , g ξ )sφ

= e(g, g2 )s · e(g, g2 )sφ · e(h1 , h2 )s · e(h3 , h4 )s · e(h3 , h4 )sφ

= C4

On the other side, we have

C3 · e(C1 , r2 ) · (C2 )r1 +βγ

1

= m · e(g, g2 )’s · e(h1 , h2 )’s · e g1 g ’sh , (g2 g ’r1 ) ±’h

s

· e(g, g)sr1 · e(g, g)sβγ

1

= m · e(g, g2 )’s · e(h1 , h2 )’s · e g s(±’h) , (g2 g ’r1 ) ±’h

· e(g, g)sr1 · e(g β , g γ )s

= m · e(g, g2 )’s · e(h1 , h2 )’s · e(g, g2 )s · e(g, g)’sr1 · ·e(g, g)sr1 · e(h1 , h2 )s

= m.

4.2 Security Analysis

Theorem 1. Let q = qc +1 where qc is the number of certi¬cation query allowed.

Assume thetruncated decision (t, , q)-ABDHE assumption holds for (G, GT , e).

Then our proposed CBE scheme is (t , , qc , qd ) secure against Game 1 adversary,

where

t = t ’ O(texp · q 2 ) = + qd /p

where texp is the time required for an exponentiation in G.

Proof. The Game 1 security of our scheme is more or less similar to the IND-ID-

CCA security of Gentry™s IBE scheme [11]. In this extended abstract, we may

omit some of the details here. Readers may refer to [11] for the full explanation

of some steps.

Let A1 be an adversary that (t , , qc , qd )-wins Game 1. We construct an

algorithm B that solves the truncated decision q-ABDHE problem, as follows. B

takes an input a random truncated decision q-ABDHE challenge (˜, g(q+2) , g, g(1) ,

g˜

. . . , g(q) , Z), where Z is either e(g(q+1) , g) or a random element of GT (we denote

˜

i

g(i) = g (± ) ). Algorithm B proceeds as follow.

Setup: B generates random polynomials f (x), f (x), f (x) ∈ Zp [x] of degree q.

It sets g1 = g(1) and g2 = g f (±) , computing g2 from (g, g(1) , . . . , g(q) ). Similarly,

E¬cient Certi¬cate-Based Encryption in the Standard Model 151

it also sets g2 = g f (±) and g2 = g f (±) . B also chooses two hash functions

H, H : {0, 1}— ’ Zp from a family of universal one-way hash functions.

It sends the public parameters (H, H , g, g1 , g2 , g2 , g2 ) to A1 . Since g, ±, f (x),

f (x), f (x) are chosen uniformly at random, g2 , g2 , g2 are also uniformly random

and the public parameters have a distribution identical to that in the actual

construction.

Oracle Queries:

“ Certi¬cation Query: B responds to a query on public key P K = (h1 , h2 ,

h3 , h4 , h3 , h4 ), user identi¬cation information » and secret key usk = (β, γ, δ,

ξ, δ , ξ ). B checks whether P K is corresponding to usk. If it is not, output

⊥. Then it computes h = H(h1 , h2 , h3 , h4 , h3 , h4 , »). If h = ±, B uses ± to

solve truncated decision q-ABDHE immediately. Else, to generate let Fh (x)

denote the (q ’ 1)-degree polynomial (f (x) ’ f (h))/(x ’ h). B sets (r1 , r2 ) =

(f (h), g Fh (±) ). These are valid certi¬cate values for h, since

g Fh (±) = g (f (±)’f (h))/(±’h) = (g2 g ’f (h) )1/(±’h)

as required. It computes the remainder of the certi¬cate in a similar way.

“ Decryption Query: To respond to a decryption query on (», P K, usk, C), B

generates a certi¬cate for P K as above. It then decrypts C by performing

the usual Decrypt algorithm with the certi¬cate and the secret key usk.

— —

Challenge: A1 outputs a challenged public key P K — = (h— , h— , h— , h— , h 3 , h 4 ),

1 2 3 4

— —

— — — ———

user identi¬cation information » , secret key usk = (β , γ , δ , ξ , δ , ξ ) and

two messages m0 , m1 . Again, B checks whether P K — , usk — is a valid key pair.

— —

It outputs ⊥ if it is not. Else, B computes h— = H(h— , h— , h— , h— , h 3 , h 4 , »— ).

1 2 3 4

If h— = ±, B uses ± to solve truncated decision q-ABDHE immediately. Else B

chooses a random bit b ∈R {0, 1}, and computes a certi¬cate (r1 , r2 , r1 , r2 , r1 , r2 )

for P K — as in the certi¬cation query. Let f2 (x) = xq+2 and let F2,h— (x) =

(f2 (x) ’ f2 (h— ))/ (x ’ h— ), which is a polynomial of degree q + 1. B sets

q

mb

f2 (±)’f2 (h— ) i

— — —

= Z · e(˜, g F2,h— ,i ± ) ; C3 =

C1 =g

˜ ; C2 g — , r )(C — )r1 (C — )β — γ —

e(C1 2 2 2

i=0

— — —

where F2,h— ,i is the coe¬cient of xi in F2,h— (x). After setting φ = H (C1 , C2 , C3 ),

B sets ——

—— ——

— — —

φ

C4 = e(C1 , r2 r2 )(C2 )r1 +r1 φ+β γ +δ ξ +δ ξ φ

— — — —

It sends (C1 , C2 , C3 , C4 ) to A1 as the challenge ciphertext.

—

—

Let s = (logg g)F2,h— (±). If Z = e(g(q+1) , g), then C1 = g s(±’h ) and

˜ ˜

—

γ—

— — — —

= e(g, g2 )s e(h— , h— )s

mb /C3 = e(C1 , r2 )(C2 )r1 (C2 )β 1 2

Thus (C1 , C2 , C3 , C4 ) is a valid ciphertext for (P K — , mb ) under randomness s.

— — — —

— — — —

Since logg g is uniformly random, s is random, and so (C1 , C2 , C3 , C4 ) is a valid,

˜

appropriately-distributed challenge to A1 .

152 J.K. Liu and J. Zhou

Output: Finally A1 outputs a bit b ∈ {0, 1}. If b = b , B outputs 1 indicating

that Z = e(g(q+1) , g ). Otherwise it outputs 0.

˜

Probability Analysis: When B™s input is sampled according to the problem in-

stance, B™s simulation appears perfect to A1 if A1 makes only certi¬cation

queries. B™s simulation still appears perfect if A1 makes decryption queries only

on public keys for which it queries the certi¬cate, since B™s responses give A1

no additional information. Furthermore, querying well-formed ciphertexts to the

decryption oracle does not help A1 distinguish between the simulation and the

actual construction, since by the correctness of Decrypt, well-formed ciphertexts

will be accepted. Finally querying a non-well-formed ciphertext does not help

A1 distinguish, since this ciphertext will fail the Decrypt check under every valid

certi¬cate. Thus, by following the approach of Lemma 1 of [11], we claim that

the decryption oracle, in the simulation and in the actual construction, rejects

all invalid ciphertexts under public keys not queried by A1 , except with proba-

bility qd /p.

Time Complexity: In the simulation, B™s overhead is dominated by computing

g Fh (±) in response to A1 ™s certi¬cation query on P K, where Fh (x) is a polynomial

of degree q ’1. Each such computation requires O(q) exponentiations in G. Since

A1 makes at most q ’ 1 such queries, t = t + O(texp · q 2 ).

Theorem 2. Assume (t, )-DBDH assumption holds for (G, GT , e). Then our

proposed CBE scheme is (t , , qc , qd ) secure against Game 2 adversary, where

t =t = + qd /p

Proof. Let A2 be an adversary that (t , , qc , qd )-wins Game 2. We construct