The Type-I’ game can be obtained by adding Aux = {pk— , · · · pk—K } and the

1 q

above restriction to De¬nition 3, but with a restriction on UskO as in De¬nition 4.

Implicit public key replacement. In our generalization of CLE, we “remove”

(i.e. make implicit) the oracle for replacing the public key corresponding to an

identi¬er. This change may a¬ect the following choices:

1. The adversary™s choice of the victim user it wishes to be challenged with,

2. The choice of user in decryption oracle queries.

However, there are other “interfaces” in our model such that the adversary can

still make the above choices. Our model still allows the adversary to choose which

identi¬er/public key it wants to attack. For decryption queries, the adversary

can just supply di¬erent combination of identi¬er and public key to the DecOS

and DecOU oracles. In this way, implicit replacement is done. In other words,

when compared with the original model [1], the security model is not weakened,

but generalized to cover applications of CLE such as TRE.

Reason for “removing” public key request and replacement oracles.

In traditional de¬nitions of CLE [1], oracles for retrieving and replacing public

key depend upon the fact that an identi¬er is always bound to a particular

user. Replacing a user™s public key means changing the public key associated

with a certain identi¬er. In TRE, identi¬ers correspond to policies governing the

decryption, so a single identi¬er may be “shared” among multiple users. For this

reason, our model must be free from the concept of “user = identi¬er”.

Alternative de¬nition of public key replacement. What about allowing

a restricted public key replacement, such that a public key associated with an

identi¬er can be replaced by a public key associated with another identi¬er, but

not an arbitrary one supplied by the adversary? This de¬nition still requires an

identi¬er to belong to a single user. Moreover, this de¬nition makes the treatment

of a strong decryption oracle complicated: the idea of restricted replacement

among a ¬xed set of public keys does not match well with decrypting under

adversarially chosen public keys.

SMCLE is more general than plain CLE. The two separate decryption

oracles in the SMCLE model provide a more general notion than CLE:

1. Some CLE schemes are not CCA-secure when the adversary has access to a

partial decryption oracle (see [12]).

134 S.S.M. Chow, V. Roth, and E.G. Rie¬el

2. Since the decryption oracle is separated in two, the SMCLE model does not

have the notion of a “full” private key which is present in previous CLE

models (a full private key is a single secret for the complete decryption of

the ciphertext). On the ground that separated secrets can always be concate-

nated into a single full one, this simpli¬cation (of private key) has already

been adopted in more recent models [22].

Di¬erence with the previous SMCLE de¬nition. Our user decryption

oracle DecOU returns di¬erent invalid ¬‚ags for the cases of invalid token from

the SEM or invalid ciphertext. This distinction was not captured in [12].

User decryption oracle in SMCLE. To exclude trivial attacks, our Type-II

adversary model disallows the challenge ciphertext C — to be decrypted by the

decryption oracle under the challenge public key and a token D obtained from the

algorithm (not the oracle) DecS (C — , ID— ), where ID— is the challenge identi¬er.

To implement this restriction, our new SMCLE de¬nition checks whether a token

D is a valid token, corresponding to a ciphertext and an identi¬er.

While our security de¬nition is tightly coupled with the ability to check the

token, we think that it is natural for the user to be able to perform such a test

(especially if the user pays for each token). Even without an explicit testing

algorithm, the challenger may do the test as well since it simulates the scheme™s

execution. It gives a weaker de¬nition if we prohibit any decryption query for

the challenge ciphertext under the challenge public key, irrespective of the token.

Justi¬cations for our de¬nition of hierarchical CLE. In the hierarchical

scheme of [1], an entity at level k derives a trapdoor for its children at level

k + 1 using both its trapdoor and its secret key. In our proposed model, a level

k entity uses only the trapdoor obtained from its parent at level k ’ 1 to derive

keys for its children. We do not see any practical reason for requiring the secret

key in the trapdoor derivation. Our de¬nition avoids certain complications: for

example, in [1], the decryption requires the public keys of all the ancestors.

#»

We do allow the decryption of the ciphertext under ID which is a pre¬x of

#»

ID— . This is stronger than the counterpart in some hierarchical IBE models [20].

Theorem 1. If there exists a secure 1-level SMCLE scheme under De¬nition 3

and 4, there exists a CLE scheme which is secure under the de¬nition of [1].

Proof. Our aim is to build a simulator B which uses an adversary A of CLE

to break the security of our 1-level SMCLE scheme. The simulator basically

forwards everything (the system parameters, the oracle queries and responses,

and the guess) back and forth between its own SMCLE challenger and the CLE

adversary. Faced with a Type-II adversary of CLE, the simulator acts as a Type-

II security of 1-level SMCLE. For a Type-I adversary of CLE, B ¬‚ips a fair coin to

#»

determine its guess whether A will issue an ExtractO query of ID— . If it guesses

not, B just plays the Type-I game as usual. If it guesses so, B will try to use A to

win the Type-II game of SMCLE instead. The ExtractO query can be answered

by B because it owns Msk now. The reduction tightness is reduced by a factor

of 2. This simple trick is also used in [17, Appendix B, Game 4].

General Certi¬cateless Encryption and Timed-Release Encryption 135

We omit the details for most queries, but focus on the distinctions that involve

public key requests and replacement. The simulator must maintain a table to

store the binding between an identi¬er and a public key. Whenever a Type-I

$

adversary issues a public key request query, B executes (pk, sk) ← KGen, stores

sk (so B can reply if A asks for it), and returns pk. For a Type-II adversary,

B picks a random public key from {pk— , · · · , pk—K } and assigns it as the public

1 q

key of the queried ID. When A makes a key replacement query, the simulator

updates its own table. For every other request regarding a particular identi¬er,

the simulator retrieves the corresponding public key from its table and queries

its own challenger accordingly. Finally, decryption queries of the CLE adversary

are answered by combining results from the two partial decryption oracles.

4 Our Proposed Construction

4.1 Preliminaries

Let G and GT be multiplicative groups of prime order p for which there exists

an e¬ciently computable bilinear map e : G — G ’ GT such that

ˆ

1. Bilinearity: For all u, v ∈ G and r, s ∈ Zp , e(ur , v s ) = e(u, v)rs .

ˆ ˆ

2. Non-degeneracy: e(u, v) = 1GT for all u, v ∈ G \ {1G }.

ˆ

Our scheme™s security relies on the intractability of the following problems:

De¬nition 5. The Decision 3-Party Di¬e-Hellman Problem (3-DDH) in G is

to decide if T = g βγδ given (g, g β , g γ , g δ , T ) ∈ G5 . Formally, de¬ning the advan-

tage of a PPT algorithm D, AdvD 3’DDH

(»), as

$ $

| Pr[1 ← D(g, g β , g γ , g δ , T )|T ← g βγδ § β, γ, δ ← Z— ]

p

$ $ $

’ Pr[1 ← D(g, g β , g γ , g δ , T )|T ← G § β, γ, δ ← Z— ]|.

p

(») is negligible in » for all PPT D.

3’DDH

We say 3-DDH is intractable if AdvD

Compared with the Bilinear Di¬e-Hellman (BDH) problem, the problem in-

stance of 3-DDH is purely in G while that of BDH contains an element t ∈ GT . ˆ

βγδ

If BDH problem is solvable, one can solve 3-DDH by feeding (g, g , g , g , e(g, T ))

ˆ

to a BDH oracle. The above assumption has been employed in [17].

We introduce a variant of the weak Bilinear Di¬e-Hellman Inversion— (wBDHI— )

assumption [4] below in the favor of 3-DDH. The original h-wBDHI— problem in

h+1

(G, GT ) [4] is to decide whether t = e(g, g γ )± . The term “inversion” comes from

ˆˆ

ˆˆ

the equivalence to the problem of deciding whether t = e(g, g γ )1/± .

De¬nition 6. The h-Weak Di¬e-Hellman Exponent Problem (h-wDHE) in G

h+1 2 h

given (g, g γ , g ± , g ± , · · · , g ± , T ) ∈ Gh+3 . Formally,

is to decide if T = g γ±

de¬ning the advantage of a PPT algorithm D as

2 h h+1

§ ±, γ ← Z— ]

$ $

(») = | Pr[1 ← D(g, g γ , g ± , g ± , · · · , g ± , T )|T← g γ±

h’wDHE

AdvD p

2 h

’ Pr[1 ← D(g, g γ , g ± , g ± , · · · , g ± , T )|T ← G § ±, γ ← Z— ]|.