De¬nition 2 (Decisional Bilinear Di¬e-Hellman (DBDH) Assum ption).

The Decisional Bilinear Di¬e-Hellman (DBDH) problem in G is de¬ned as fol-

lows: On input (g, g a , g b , g c ) ∈ G4 and Z ∈ GT , output 1 if Z = e(g, g)abc and 0

otherwise. We say that the (t, )-DBDH assumption holds in (G, GT ) if no t-time

algorithm has advantage at least over random guessing in solving the DBDH

problem in (G, GT ).

3 Security Model

We use the simpli¬ed model of [2] in the de¬nition of our scheme and the security

model.

De¬nition 3. A certi¬cate-based encryption (CBE) scheme is de¬ned by six

algorithms:

“ Setup is a probabilistic algorithm taking as input a security parameter. It

returns the certi¬er™s master key msk and public parameters param. Usually

this algorithm is run by the CA.

“ UserKeyGen is a probabilistic algorithm that takes param as input. When

run by a client, it returns a public key P K and a secret key usk.

“ Certify is a probabilistic algorithm that takes as input (msk, „, param, », P K)

where » is a bit string containing user identi¬cation information. It returns

Cert„ which is sent to the client. Here „ is a string identifying a time period.

“ Consolidate is a deterministic certi¬cate consolidation algorithm taking as

input (param, „, Cert„ ) and optionally Cert„ ’1 . It returns Cert„ , the cer-

ti¬cate used by a client in time period „ .

“ Encrypt is a probabilistic algorithm taking as input („, param, », P K, m)

where m is a message. It outputs a ciphertext C.

“ Decrypt is a deterministic algorithm taking (param, Cert„ , usk, C) as input

in time period „ . It returns either a message m or the special symbol ⊥

indicating a decryption failure.

We require that if C is the result of applying algorithm Encrypt with intput

(„, param, P K, m) and (usk, P K) is a valid key-pair, then m is the result of

applying algorithm Decrypt on input (param, Cert„ , usk, C), where Cert„ is the

output of Certify and Consolidate algorithms on input (msk, param, „, P K). That

is, we have

DecryptCert„,usk (Encrypt„,P K (m)) = m

We also note that a concrete CBE scheme may not involve certi¬cate consolida-

tion. In this situation, algorithm Consolidate will simply output Cert„ = Cert„ .

In the rest of this paper, for simplicity, we will omit Consolidate and the time

identifying string „ in all notations.

The security of CBE is de¬ned by two di¬erent games and the adversary

chooses which game to play. In Game 1, the adversary models an uncerti¬ed

entity while in Game 2, the adversary models the certi¬er in possession of the

master key msk attacking a ¬xed entity™s public key.

148 J.K. Liu and J. Zhou

De¬nition 4 (CBE Game 1). The challenger runs Setup, gives param to the

adversary A1 and keeps msk to itself. The adversary then interleaves certi¬cation

and decryption queries with a single challenge query. These queries are answered

as follows:

“ On certi¬cation query (», P K, usk), the challenger checks that (P K, usk)

is a valid key-pair. If so, it runs Certify on input (msk, param, », P K) and

returns Cert. Else it returns ⊥.

“ On decryption query (», P K, usk, C), the challenger checks that (P K, usk) is

a valid key-pair. If so, it generates Cert by using algorithm Certify with inputs

(msk, param, », P K) and outputs DecryptCert,usk (C). Else it returns ⊥.1

“ On challenge query (»— , P K — , usk — , m0 , m1), the challenger checks that (P K — ,

usk — ) is a valid key-pair. If so, it chooses a random bit b ∈R {0, 1} and

returns C — = Encrypt»— ,P K — (mb ). Else it returns ⊥.

Finally A1 outputs a bit b ∈ {0, 1}. The adversary wins the game if b = b

and (»— , P K — , usk — , C — ) was not submitted to the decryption oracle after the

challenge, and (»— , P K — , usk — ) was not submitted to the certi¬cation query. We

de¬ne A1 ™s advantage in this game to be Adv(A1 ) = 2| Pr[b = b ] ’ 1 |. 2

De¬nition 5 (CBE Game 2). The challenger runs Setup, gives param and

msk to the adversary A2 . The challenger then runs UserKeyGen to obtain a

key-pair (P K — , usk — ) and gives »— , P K — to the adversary A2 . The adversary

interleaves decryption queries with a single challenge query. These queries are

answered as follows:

“ On decryption query (C), the challenger generates Cert, by using algorithm

Certify with inputs (msk,param,»— , PK —). It then outputs DecryptCert,usk— (C).

“ On challenge query (m0 , m1 ), the challenger randomly chooses a bit b ∈R

{0, 1} and returns C — = Encrypt»— ,P K — (mb ).

Finally A2 outputs a guess b ∈ {0, 1}. The adversary wins the game if b = b

and C — was not submitted to the decryption oracle after the challenge. We de¬ne

A2 ™s advantage in this game to be Adv(A2 ) = 2| Pr[b = b ] ’ 1 |.

2

We note that our model does not support security against Malicious Certi¬er.

That is, we assume that the certi¬er generates all public parameters honest,

according to the algorithm speci¬ed. The adversarial certi¬er is only given the

master secret key, instead of allowing to generate all public parameters. Although

malicious certi¬er has not been discussed in the literature, similar concept of

Malicious Key Generation Centre (KGC) [3] has been formalized in the area of

certi¬cateless cryptography.

De¬nition 6 (Secure CBE). A CBE scheme is said to be (t, qc , qd , )-secure

against adaptive chosen ciphertext attack if all t-time adversary making at most

1

Note that in the decryption oracle of Game 1, we need to take the user secret key

as input. This is the same as all previous CBE schemes [10,2].

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

qc certi¬cation query (for Game 1 only) and at most qd chosen ciphertext decryp-

tion queries have advantage at most in either CBE Game 1 or CBE Game 2.

4 The Proposed Scheme

4.1 Construction

Our scheme is motivated by Gentry™s identity based encryption scheme [11].

Details are as follow.

Setup. Let e : G — G ’ GT be a pairing. Let p be the group order of G and GT .

The CA chooses generators g, g2 , g2 , g2 ∈ G and randomly selects ± ∈R Zp . It

computes g1 = g ± . It also chooses two hash functions H, H : {0, 1}— ’ Zp from

a family of universal one-way hash functions. The master secret msk is ± while

the public parameters param are (H, H , e, p, g, g1, g2 , g2 , g2 ).

UserKeyGen. The user randomly selects β, γ, δ, ξ, δ , ξ ∈R Zp and computes h1 =

g β , h2 = g γ , h3 = g δ , h4 = g ξ , h3 = g δ , h4 = g ξ . The public key P K is

(h1 , h2 , h3 , h4 , h3 , h4 ) and the user secret key usk is (β, γ, δ, ξ, δ , ξ ).

Certify. Suppose a user with public key P K and identi¬cation information » ∈

{0, 1}— wants to be certi¬ed. He sends pk = (h1 , h2 , h3 , h4 , h3 , h4 ) and » to the

CA. The CA randomly selects r1 , r1 , r1 ∈R Zp and computes h = H(h1 , h2 , h3 ,

h4 , h3 , h4 , ») and

1 1 1

r2 = (g2 g ’r1 ) ±’h r2 = (g2 g ’r1 ) ±’h r2 = (g2 g ’r1 ) ±’h

The certi¬cate Cert is (r1 , r2 , r1 , r2 , r1 , r2 ). Similar to [11], we require that the

CA always uses the same random values r1 , r1 , r1 for this user. This can be

accomplished, for example, by using an internal log to ensure consistency.

Encrypt. To encrypt a message m ∈ GT using public key (h1 , h2 , h3 , h4 , h3 , h4 )

and », randomly selects s ∈R Zp , computes h = H(h1 , h2 , h3 , h4 , h3 , h4 , ») and

C1 = g1 g ’sh C3 = m · e(g, g2 )’s · e(h1 , h2 )’s

s

C2 = e(g, g)s

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

where φ = H (C1 , C2 , C3 ). Outputs the ciphertext C = (C1 , C2 , C3 , C4 ).

Decrypt. To decrypt ciphertext C = (C1 , C2 , C3 , C4) with certi¬cate (r1 , r2 ,

r1 , r2 , r1 , r2 ) and secret key (β, γ, δ, ξ, δ , ξ ) with respect to public key (h1 , h2 , h3 ,

h4 , h3 , h4 ) and », computes

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

and φ = H (C1 , C2 , C3 ). Outputs m if

φ

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

Otherwise outputs ⊥.

150 J.K. Liu and J. Zhou

Correctness. If the ciphertext is well formed, we have

φ

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

φ

1

= e g1 g ’sh , (g2 g ’r1 ) ±’h (g2 g ’r1 ) ±’h

s

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