against an adversary with adaptive trapdoor extraction capabilities for arbitrary

identi¬ers (instead of selective identi¬ers, e.g. [4,27]), decryption capabilities for

arbitrary public keys (as considered in strongly-secure CLE [17]) and partial

decryption capabilities (as considered in security-mediated CLE [12]). Our model

also supports hierarchical identi¬ers which have not been considered formally for

CLE and TRE. Design choices behind our formulation are justi¬ed.

All previous concrete TRE schemes [3,7,8,9,10,15,18,21,23], and the only con-

crete SMCLE scheme [12], were proven in the random oracle model. Our model is

strong but achievable: our proposed scheme is the ¬rst strongly-secure SMCLE.

With our security-preserving transformation from a general CLE to a TRE, it

also yields the ¬rst TRE in the standard model.

This work enriches the study of SMCLE by providing a novel partial decryp-

tion technique which is di¬erent from that in [12], and enriches TRE by sup-

porting a new business model for the time-server. Finally, hierarchy of identi¬ers

makes decryption of ciphertext for passed periods more manageable.

2 Related Work

2.1 Timed-Release Encryption

Early TRE schemes require interaction with the time-server. Rivest, Shamir and

Wagner™s idea [28] require senders to reveal the release-time of the messages

in their interactions with the server, so the senders cannot be anonymous to

the server. In Di Crescenzo, Ostrovsky and Rajaopalan ™s scheme [15], it is the

receiver who interacts with the time-server by invoking a “conditional oblivious

transfer protocol”, which is computationally intensive.

Blake and Chan made the ¬rst attempt to construct a non-interactive TRE

[3]. The formal security model of message con¬dentiality was later considered

independently by Cheon et al. [10] and Cathalo, Libert and Quisquater [7]. The

former focuses on authenticated TRE. The latter also formalizes the release-time

con¬dentiality. The recovery of past time-dependent trapdoors from a current

trapdoor was studied in [9] and [26], which employs a hash chain and a tree

structure [6] respectively. The study of the pre-open capability in TRE was

initiated in [23] and improved by [18]. Recently, Chalkias, Hristu-Varsakelis and

Stephanides proposed an e¬cient TRE scheme [8] with random oracles.

2.2 Certi¬cateless Encryption

Al-Riyami and Paterson [1] proposed certi¬cateless encryption in 2003. Exten-

sive surveys of CLE security models and constructions can be found in [14,16].

Two types of adversaries are considered in certi¬cateless encryption. A Type-I

adversary models coalitions of rogue users without the master secret. Due to the

lack of a certi¬cate, the adversary is allowed to replace the public keys of users.

A Type-II adversary models a curious KGC who has the master key but cannot

replace the public keys of any users. In Al-Riyami and Paterson™s security model

General Certi¬cateless Encryption and Timed-Release Encryption 129

for encryption [1], a Type-I adversary can ask for the decryption of a cipher-

text under a replaced public key. Schemes secure against such attacks are called

“strongly-secure” [17], and the oracle is termed a “strong decryption oracle”. A

weaker type of adversary, termed Type-I’ , can only obtain a correct plaintext

if the ciphertext is submitted along with the corresponding user secret key.

The Al-Riyami and Paterson scheme [1] is secure against both Type-I and

Type-II adversaries in the random oracle model. It was believed [24,25,27] that

[25] gave the ¬rst CLE in the standard model. However, it is possible to in-

stantiate a prior generic construction in [12] with a PKE and an IBE in the

standard model to obtain a secure CLE without random oracles. Both [25] and

the instantiation of [12] are only secure against Type-I’ attacks. Based on [19], a

selective-ID secure CLE without random oracles was proposed [27]. This scheme

cannot be e¬ciently extended to a TRE since the user™s public key is depen-

dent on the identity, which is never coupled with a ¬xed time-identi¬er in TRE.

Recently, the ¬rst strongly-secure CLE in the standard model is proposed [17].

Al-Riyami and Paterson give an extension for hierarchical CLE [1]. However,

no security model is given. We are not aware of any literature with formal work

on hierarchical CLE, particularly none proven secure in the standard model.

Baek et al. proposed the ¬rst CLE that does not use pairings [2]. The CLE

proposal [24] uses similar ideas, but their security proof ignores the public key

replacement of the target user being attacked. This limitation is removed in Sun,

Zhang and Baek™s work [30]. To replace the pairing, these schemes make part of

the user™s public key dependent on the identity-speci¬c trapdoor given by the

KGC, which means TRE cannot be obtained trivially from these constructions.

Security-mediated certi¬cateless encryption (SMCLE), introduced by Chow,

Boyd and Gonz´lez Nieto [12], adds a security-mediator (SEM) who performs

a

partial decryption for the user by request. This idea gives a more general treat-

ment of the decryption queries in the CLE paradigm: the adversary can ask for

partial decryption results under either the SEM trapdoor generated by the KGC

or the user secret key A concrete construction in the random oracle model and

a generic construction in the standard model are proposed in [12]. Prior to our

work, no strongly-secure SMCLE existed in the standard model.

3 General Security-Mediated Certi¬cateless Encryption

3.1 Notation

#»

We use an ID-vector ID = (ID1 , ID2 , · · · , IDL ) to denote a hierarchy of identi¬ers

#» #» #»

(ID1 , ID2 , · · · , IDL ). The length of ID is denoted by |ID| = L. Let ID||IDr denote

#» #»

the vector (ID1 , ID2 , · · · , IDL , IDr ) of length |ID| + 1. We say that ID is a pre¬x

#» #»

#» #»

of ID if |ID| ¤ |ID | and IDi = IDi for all 1 ¤ i ¤ |ID|. We use … to denote

an empty ID-vector where |…| = 0 and …||IDr = IDr . Finally, we use the notation

({0, 1}n)¤h to denote the set of vectors of length less than or equal to h, where

each component is a n-bit long bit-string.

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

3.2 Syntax

We propose a new de¬nition of the (security-mediated) certi¬cateless encryption,

which also extends the de¬nition of a 1-level SMCLE scheme in [12] to h levels.

De¬nition 1. An h-level SMCLE scheme for identi¬ers of length n is de¬ned

by the following sextuple of PPT algorithms:

“ Setup (run by the server) is a probabilistic algorithm which takes a security

parameter 1» , outputs a master secret key Msk (which can also be denoted as

d… ), and the global parameters Pub (which include h = h(») and n = n(»)

implicitly) We assume all other algorithms take Pub implicitly as an input.

“ Extract (run by the server or any one who holds a trapdoor) is a possibly

#»

probabilistic algorithm which takes a trapdoor dID corresponding to an h-level

#»

identi¬er ID ∈ ({0, 1}n)¤h , and a string IDr ∈ {0, 1}n, outputs a trapdoor

#»

#»

key dID||IDr associated with the ID-vector ID||IDr . The master secret key

Msk is a trapdoor corresponding to a 0-level identi¬er.

“ KGen (run by a user) is a probabilistic algorithm which generates a pub-

lic/private key pair (pku , sku ).

“ Enc (run by a sender) is a probabilistic algorithm which takes a message m

#»

from some implicit message space, an identi¬er ID ∈ ({0, 1}n)¤h , and the

receiver™s public key pku as input , returns a ciphertext C.

“ DecS (run by any one who holds the trapdoor, either a SEM in SMCLE or a

receiver in CLE) is a possibly probabilistic algorithm which takes a ciphertext

#»

C and a trapdoor key dID , returns either a token D which can be seen as a

partial decryption, or an invalid ¬‚ag ⊥ (which is not in the message space).

“ DecU (run by a receiver) is a possibly probabilistic algorithm which takes the

ciphertext C, the receiver™s secret key sku and a token D as input, returns

either the plaintext, an invalid ¬‚ag ⊥D denoting D is an invalid token, or

an invalid ¬‚ag ⊥C denoting the ciphertext is invalid.

#»

For correctness, we require that DecU (C, sk, DecS (C, Extract(Msk, ID))) = m for

$ $

all » ∈ N, all (Pub, Msk) ← Setup(1» ), all (pk, sk) ← KGen, all message m, all

#» #»

$

ID-vector ID in ({0, 1}n)¤h and all C ← Enc(m, ID, pk).

3.3 Security

Each adversary has access to the following oracles:

#»

1. An ExtractO oracle that takes an ID-vector ID ∈ ({0, 1}n )¤h as input and

#»

returns its trapdoor dID .

2. An UskO oracle that takes a public key pk as input and returns its corre-