sk

e(C2 , D2 )ˆ(σ, D3 )

ˆ e

m ← C1 · .

e(„, D1 )

ˆ

2

One pairing computation can be saved by a trick adopted in [17]: pick ξ ∈R Z— and

p

sξ

ξs

compute C1 = m · e(Y, g2 · g ) /ˆ(X, g1 ).

e

ˆ

3

The same trick for minimizing the number of pairing computations involved in check-

ing the ciphertext and the token can be incorporated to the ¬nal decryption step.

The modi¬ed decryption algorithm only uses 4 pairing computations; however, it

gives a random message (instead of an invalid ¬‚ag ⊥) for an invalid ciphertext.

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

4.3 Analysis

Similar to [4], the ciphertext size of our scheme is independent of the hierarchy

length. This is also bene¬cial when it is used as a TRE (see Section 5.5).

In the concrete SMCLE scheme of Chow, Boyd and Gonz´lez Nieto [12],

a

partial decryption uses the pairing function e(·, ·) to pair part of the ciphertext

ˆ

and the ID-based private key. To make this partial decryption result veri¬able

requires turning a generic interactive proof-of-knowledge non-interactive. Our

scheme employs a di¬erent technique such that the token generated by the partial

decryption is publicly and non-interactively veri¬able.

Our scheme™s security is asserted by Theorem 2; [13] contains a proof.

Theorem 2. Our scheme is secure against Type-I attack and Type-II attack

(De¬nition 3 and 4) if h-wDHE problem and 3-DDH problem is intractable.

5 Applying General Certi¬cateless Encryption to TRE

5.1 Syntax of Timed-Release Encryption

For ease of discussion, consider only 1-level of time-identi¬ers as in [7]. It can be

shown that our results hold for an h-level analog.

De¬nition 8. A TRE scheme for time-identi¬ers of length n (n is a

polynomially-bounded function) 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, and the global parameters

Pub. We assume that » and n = n(») are implicit in Pub and all other

algorithms take Pub implicitly as an input.

“ Extract (run by the server) is a possibly probabilistic algorithm which takes

the master secret key Msk and a string ID ∈ {0, 1}n, outputs a trapdoor key

dID associated with the identi¬er ID.

“ 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, 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 or a receiver) is

a possibly probabilistic algorithm which takes a ciphertext C and a trapdoor

key dID as input, returns either a token D which can be seen as a partial

decryption of C, 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.

General Certi¬cateless Encryption and Timed-Release Encryption 139

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

$

identi¬er ID in {0, 1}n and all C ← Enc(m, ID, pk).

5.2 Timed-Release Encryption from Certi¬cateless Encryption

Given a SMCLE scheme {SMC.Setup, SMC.Extract, SMC.KGen, SMC.Enc,

SMC.DecS , SMC.DecU }, {T RE.Setup, T RE.Extract,

a TRE scheme

T RE.KGen, T RE.Enc, T RE.Dec , T RE.Dec } can be built as below.

S U

T RE.Setup(1» , n): Given a security parameter » and the length of the time-

identi¬er n, execute (Msk, Pub) ← SMC.Setup(1» , n), retain Msk as the master

secret key and publish Pub as the global parameters.

T RE.Extract(Msk, ID): For a time-identi¬er ID ∈ {0, 1}n, the time-server returns

dID ← SMC.Extract(Msk, ID).

T RE.KGen(): Return (sk, pk) ← SMC.KGen() as the user™s key pair.

T RE.Enc(m, ID, pk): To encrypt m ∈ GT for pk under the time ID ∈ {0, 1}n,

return SMC.Enc(m, ID, pk), which may be ⊥ if pk is an invalid public key.

T RE.DecS (C, dID ): To partially decrypt C by a time-dependent trapdoor dID ,

return D ← SMC.DecS (C, dID ).

T RE.DecU (C, sk, D): To decrypt C by the secret key sk and the token D, just

return SMC.DecU (C, sk, D).

Theorem 3. If SMC is an 1-level SMCLE scheme which is CCA-secure against

Type-I adversary (De¬nition 3), T RE is CCA-secure against Type-I adversary.

Theorem 4. If SMC is an 1-level SMCLE scheme which is CCA-secure against

Type-II adversary (De¬nition 4), T RE is CCA-secure against Type-II adversary.

Proof. The security models of TRE can be found in [13]. We prove by contradic-

tion. Suppose A is a Type-X adversary such that | Pr[ExpCCA ’X (») = 1]’ 2 | > ,

1

A

we construct an adversary B with | Pr[ExpCCA’X (») = 1] ’ 1 | > in the face of

B 2

a SMCLE challenger C where the running times of B and A are equal.

Setup: When C gives B (Pub, Aux), B just forwards it to A. The public key to

be passed to A is either chosen from the a set of public key in Aux (in Type-II

game), or chosen by B itself (in Type-I game).

First Phase of Queries: B forwards every request of A to the oracles of its

own challenger C. From the description of T RE, we can see that every legitimate

oracle query made by A can be answered faithfully.

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

Challenge: When A gives B (m0 , m1 , pk— , ID— ), B just forwards it to C.

Second Phase of Queries: Again, B just forwards every request of A to the

oracles of its own challenger C. From the description of T RE, it is easy to see

that every oracle query which does not violate the restriction enforced by A also

does not violate the restriction enforced by C.

Output: Finally, A outputs a bit b, B forwards it to C as its own answer. The

probability for A to win the TRE experiment simulated by B is equal to the

probability for B to win the SMCLE game played against C. It is easy to see

that the running times of A and B are the same.

These theorems show that the scheme presented in section 4 can be instantiated

as a TRE scheme without a random oracle.

5.3 Certi¬cateless Encryption from Timed-Release Encryption

One may expect that a general CLE can be constructed from any TRE. The

usage of time-identi¬ers, however, is only one speci¬c instantiation of the timed-

release idea. Other formulations of TRE, di¬erent from De¬nition 8, exist; for

example, in [9], time is captured by the number of repeated computations of one-

way hash function. Also, the notion of CLE supports an exponential number of