a random DBDH challenge (g, g a , g b , g c , Z), where Z is either e(g, g)abc or a

random element of GT . Algorithm B proceeds as follow.

Setup: B randomly generates ±, v, x, y, t, w, t , w ∈R Zp and sets g1 = g ± , g2 =

g v , g2 = g x , g2 = g y . B also chooses two hash functions H, H : {0, 1}— ’ Zp

from a family of universal one-way hash functions.

The public parameters param are (H, H , g, g1 , g2 , g2 , g2 ) while the master

secret key msk is ±. B also sets h1 = g a , h2 = g b , h3 = g t , h4 = g w , h3 =

g t , h4 = g w as the challenged public key P K. B also constructs some binary

string as the identi¬cation information ». (param, msk, », P K) are given to the

adversary A2 . Obviously the public parameters and the challenged public key

have a distribution identical to that in the actual construction.

Oracle Queries:

“ Decryption Query: To respond to a decryption query on C = (C1 , C2 , C3 , C4),

B ¬rst computes φ = H (C1 , C2 , C3 ) and

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

C4 · C3 · C2

v

x+yφ+tw+t w φ

C2

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

=

e(g, g x )s · e(g, g y )sφ · e(g t , g w )s · e(g t , g w )sφ

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

=m

It then generates the certi¬cate (r1 , r2 , r1 , r2 , r1 , r2 ) using the knowledge of

±, and further checks

φ

m · e(C1 , r2 r2 ) · (C2 )r1 +r1 φ+tw+t w φ’v

?

C4 =

C3

It outputs m if it is equal, otherwise outputs ⊥.

Challenge: A2 outputs two messages m0 , m1 . B randomly chooses a bit b ∈R

{0, 1}, computes h = H(h1 , h2 , h3 , h4 , h3 , h4 , ») and sets

— —

C3 = mb · e(g c , g ’v ) · Z ’1

C1 = (g c )±’h C2 = e(g, g c )

C4 = e(g c , g x ) · e(g c , g v )φ · Z · e(g c , g tw ) · e(g c , g t w )φ

where φ = H (C1 , C2 , C3 ). The challenged ciphertext C — = (C1 , C2 , C3 , C4 ) is

— — — — — — —

sent to A. It can be easily seen that if Z = e(g, g)abc , C — is a valid, appropriately-

distributed challenge ciphertext.

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

that Z = e(g, g)abc . Otherwise it outputs 0.

Probability Analysis: Similar to Game 1, the simulation remains perfect except

with probability qd /p that the decryption oracle will not reject all invalid ci-

phertext.

Time Complexity: The time complexity for B depends only on A. Thus we have

t = t.

4.3 E¬ciency Analysis

Previous generic constructions [18,7,2] are not comparable to our scheme in terms

of e¬ciency. When compare to the one in [16] (the only concrete implementation

that is fully secure in the standard model), we enjoy a great improvement in

terms of space e¬ciency. First, our scheme requires just 5 group elements (about

800 bits, assuming each group element costs 160 bits in the optimal case) in the

public parameters. But the scheme in [16] needs 164 group elements (about 26240

bits) in order to achieve the same level of security.

Second, the message space of our scheme is in GT , which is about 1024 bits.

The message space of the scheme in [16] is around 576 bits only. The main

154 J.K. Liu and J. Zhou

reason for this di¬erence is that. Although the chosen plaintext secure (CPA)

version of the scheme in [16] allows the message space to be in GT , in order

achieve CCA security, it requires an additional encapsulation scheme and the

Boneh-Katz transform. The transform modi¬es the scheme a bit, by encrypting

M = m||dec where m is the original message, dec is the decommitment string

and M is the combined message which should be in GT . According to [6], the

suggested length of dec should be at least 448 bits. That is, the message space

of the original message is reduced to 1024 ’ 448 = 576 bits. If we want to

encrypt a message of 1024 bits, we need to split it into two parts and encrypt

it part by part. It results in a double increase of both computation cost and

ciphertext size, and maybe security reduction as well. This di¬erence becomes

signi¬cant if we want to encrypt a large message. On the other side, as we do

not require any transformation or encapsulation scheme to achieve CCA security,

our message space can be remained as 1024 bits, without su¬ering any e¬ciency

reduction.

In terms of computation cost, although we require some pairing operations

in the encryption algorithm, they can be pre-computed by the CA and given as

part of the public parameters. For those pairing operations related to the public

key of the intended receiver, they can be pre-computed by the receiver and given

as part of the public key as well. In this way, the encryptor does not need to

compute any pairing operation. For the decryption algorithm, we require two

pairing operations.

5 Concluding Remarks

In this paper, we propose a new CBE scheme which is motivated from Gentry™s

IBE scheme [11]. Our scheme is fully CCA secure in the standard model. We

do not require any MAC or encapsulation scheme to achieve CCA security. This

facilitates us to achieve signi¬cant improvement in e¬ciency when compared to

[16]. We believe the concept of certi¬cate-based encryption with our e¬cient

implementation allows it to be used in some practical applications, and particu-

larly suitable to be employed in computation limited devices, or wireless sensor

network.

We also remark that our scheme does not support malicious CA security.

That is, we assume that the CA generates the public parameters according to

the algorithm honestly. This is the same as all CBE schemes in the literature.

However, recently Au et al. [3] pointed out that a malicious KGC in certi¬cateless

cryptography (with respect to CA in certi¬cate-based setting) may pose some

security risks to the system, by generating the public parameters in a malicious

way. We note that our system (and all previous CBE schemes) may su¬er similar

attack. We have not discussed those risks in this paper. We leave it as an open

problem to future research.

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

References

1. Al-Riyami, S.S., Paterson, K.: Certi¬cateless public key cryptography. In: Laih, C.-S.

(ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 452“473. Springer, Heidelberg (2003)

2. Al-Riyami, S.S., Paterson, K.G.: CBE from CL-PKE: A generic construction and

e¬cient schemes. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 398“415.

Springer, Heidelberg (2005)

3. Au, M., Chen, J., Liu, J., Mu, Y., Wong, D., Yang, G.: Malicious KGC attacks

in certi¬cateless cryptography. In: ASIACCS 2007, pp. 302“311. ACM Press, New

York (2007)

4. Au, M., Liu, J., Susilo, W., Yuen, T.: Certi¬cate based (linkable) ring signature. In:

Dawson, E., Wong, D.S. (eds.) ISPEC 2007. LNCS, vol. 4464, pp. 79“92. Springer,

Heidelberg (2007)

5. Boneh, D., Franklin, M.K.: Identity-Based Encryption from the Weil Pairing. In: Kil-

ian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213“229. Springer, Heidelberg (2001)

6. Boneh, D., Katz, J.: Improved e¬ciency for cca-secure cryptosystems built using

identity-based encryption. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376,

pp. 87“103. Springer, Heidelberg (2005)

7. Dodis, Y., Katz, J.: Chosen-ciphertext security of multiple encryption. In: Kilian,

J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 188“209. Springer, Heidelberg (2005)

8. Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryp-

tion schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 537“554.

Springer, Heidelberg (1999)

9. Galindo, D., Morillo, P., R`fols, C.: Breaking Yum and Lee generic constructions

a

of certi¬cate-less and certi¬cate-based encryption schemes. In: Atzeni, A.S., Lioy,

A. (eds.) EuroPKI 2006. LNCS, vol. 4043, pp. 81“91. Springer, Heidelberg (2006)

10. Gentry, C.: Certi¬cate-based encryption and the certi¬cate revocation problem. In:

EUROCRYPT 2003. LNCS, vol. 2656, pp. 272“293. Springer, Heidelberg (2003)

11. Gentry, C.: Practical identity-based encryption without random oracles. In: Vau-

denay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 445“464. Springer, Hei-