Cryptography and Security Department

Institute for Infocomm Research

Singapore

{ksliu,jyzhou}@i2r.a-star.edu.sg

Abstract. In this paper, we propose a new Certi¬cate-Based Encryp-

tion (CBE) scheme which is fully secure in the standard model. We

achieve chosen ciphertext (CCA) security directly without any transfor-

mation. When compared to all previous generic constructions (in either

random oracle or standard model), our scheme is far more e¬cient than

those schemes. When compared to the CBE scheme in [16] (which is the

only concrete implementation secure in the standard model), we enjoy

a great improvement in terms of space e¬ciency. Their scheme requires

more than 160 group elements for the public parameters in order to gain

an acceptable security. Our scheme just requires 5 group elements. In

addition, the message space of our scheme is almost double as the one in

[16]. A larger message space implies that it requires a smaller number of

encryption operations of the same plaintext, resulting in a smaller overall

ciphertext and overhead as well.

1 Introduction

Public Key Infrastructure (PKI). In traditional public key cryptography

(PKC), a user Alice signs a message using her private key. A veri¬er Bob veri¬es

the signature using Alice™s public key. However, the public key is just a random

string and it does not provide authentication of the signer by itself. This problem

can be solved by using a certi¬cate generated by a trusted party called the Cer-

ti¬cate Authority (CA) that provides an unforgeable signature and trusted link

between the public key and the identity of the signer. The hierarchical framework

is called public key infrastructure (PKI) to issue and manage certi¬cate (chain).

In this case, before the veri¬cation of a signature, Bob needs to obtain Alice™s

certi¬cate in advance and verify the validity of her certi¬cate. If it is valid, Bob

extracts the corresponding public key which is then used to verify the signature.

In the point of view of a veri¬er, it takes two veri¬cation steps for independent

signatures. It seems not e¬cient and not practical enough, especially when the

number of users is very large.

This work is partially funded by the EU project SMEPP-033563.

R. Ostrovsky, R. De Prisco, and I. Visconti (Eds.): SCN 2008, LNCS 5229, pp. 144“155, 2008.

c Springer-Verlag Berlin Heidelberg 2008

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

Identity-Based cryptography (IBC). Identity-based cryptography (IBC),

invented by Shamair [17] in 1984, solves this problem by using Alice™s identity

(or email address) which is an arbitrary string as her public key while the cor-

responding private key is a result of some mathematical operation that takes

as input the user™s identity and the master secret key of a trusted authority,

referred as “Private Key Generator (PKG)”. In this way, the certi¬cate is im-

plicitly provided and it is no longer necessary to explicitly authenticate public

keys. The main disadvantage of identity-based cryptography is an unconditional

trust to the PKG. This is even worse than traditional PKC since the secret key

of every user is generated by the PKG, it can impersonate any user, or decrypt

any ciphertext.

Certi¬cate-Based cryptography (CBC). To integrate the merits of IBC

into PKI, Gentry [10] introduced the concept of Certi¬cate-Based encryption

(CBE). A CBE scheme combines a public key encryption scheme and an identity

based encryption scheme between a certi¬er and a user. Each user generates his

own private and public key and request a certi¬cate from the CA while the

CA uses the key generation algorithm of an identity based encryption (IBE) [5]

scheme to generate certi¬cate. Unlike traditional PKI, the certi¬cate in CBC

is implicitly used as part of the user private key for decryption, which requires

both the user-generated private key and the certi¬cate. Although the CA knows

the certi¬cate, it does not have the user private key. Thus it cannot decrypt

anything. In addition to encryption, several certi¬cate-based signature schemes

[12,13,15] and ring signature scheme [4] were also proposed.

In parallel to CBC, certi¬cateless cryptography [1] and self-generated-certi¬cate

public key cryptography [14] are another solutions to the key escrow problem in-

herited by IBC.

1.1 Related Works

The original scheme of Gentry relied on the original identity-based encryption

(IBE) scheme of Boneh-Franklin [5] and then on the Fujisaki-Okamoto transform

[8] to obtain full security in the random oracle model. Some generic constructions

were proposed in [18,7] for constructing a CBE from an IBE (although Yum-

Lee construction [18] was broken by Galindo et al. [9]) while another generic

construction was given in [2] from a certi¬cateless encryption (CLE) scheme. A

concrete construction in the standard model was also proposed in [16].

1.2 Contribution

In this paper, we propose a new CBE scheme that is fully chosen ciphertext

(CCA) secure in the standard model. Although there are some previous results

for generic construction of a CBE from either existing IBE or CLE scheme,

they are not comparable in e¬ciency to our scheme. When compare to the one

proposed in [16], we enjoy a number of e¬ciency improvements:

1. We greatly reduce the size of public parameters. Their scheme requires the

size of public parameters to be n + 4 group elements, where n is the length

146 J.K. Liu and J. Zhou

of a bitstring representing the user public information (e.g. hash of public

key). n should be at least 160 in order to claim a reasonable security. On

the other side, we just need 5 group elements, no matter how large the user

public information is.

2. Their scheme requires Boneh-Katz transform [6] to achieve CCA security. It

needs a message authentication code (MAC) and an encapsulation scheme

in addition to the basic scheme. One of the main drawback is the reduction

of message space. Normally for a pairing e : G — G ’ GT , usually the

size of a group element in GT representation is about 1024 bits. Without

the Boneh-Katz transform, the message space of their scheme is GT , that is,

1024 bits. However, after applying the transform, it is reduced by at least 448

bits [6] due to the additional encapsulation information. Thus it only allows

to encrypt a 576 bits message for a single encryption operation. In contrast,

our scheme achieves CCA security directly without any transformation. Our

message space remains 1024 bits. A larger message space implies that it

requires a smaller number of encryption operations (which includes pairings

and exponentiations) for the same plaintext, resulting in a smaller overall

ciphertext as well.

Organization. In the rest of the paper, it is organized as follow. We review some

preliminaries in Section 2. Security model is given in Section 3. Our proposed CBE

scheme is presented in Section 4. Finally a concluding remarks is given in Section 5.

2 Preliminaries

2.1 Notations

Pairing. Let e be a bilinear map such that e : G — G ’ GT such that it has

the following properties:

G and GT are cyclic multiplicative groups of prime order p.

“

each element of G and GT has unique binary representation.

“

g is a generator of G.

“

(Bilinear) ∀x, y ∈ G and a, b ∈ Zp , e(xa , y b ) = e(x, y)ab .

“

“ (Non-degenerate) e(g, g) = 1.

2.2 Mathematical Assumptions

De¬nition 1 (Truncated Decision q-Augmented Bilinear Di¬e-Hellman

Exponent Assumption (q-ABDHE)). We de¬ne the truncated decision q-

ABDHE problem [11] as follows: Given a vector of q + 3 elements:

q+2 2 q

∈ Gq+3

g, g (±) , g, g ± , g (±) , . . . , g (±)

˜˜

q+1

and an element Z ∈ GT as input, output 1 if Z = e(g (±) , g ) and output 0

˜

otherwise. We say that the decision (t, , q)-ABDHE assumption holds in (G, GT )

if no t-time algorithm has advantage at least over random guessing in solving

the decision q-ABDHE problem in (G, GT ).

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