ńņš. 48 |

#Ā»

3. A DecOS oracle that takes a ciphertext C and an ID-vector ID, and outputs

#Ā»

DecS (C, dID ). Note that C may or may not be encrypted under ID.

#Ā»

4. A DecOU oracle that takes a ciphertext C, a public key pk and a token D,

and outputs DecU (C, sk, D) where sk is the secret key that matches pk.

General Certiļ¬cateless Encryption and Timed-Release Encryption 131

#Ā»

5. A DecO oracle that takes a ciphertext C, an ID-vector ID, and a public

key pk; outputs DecU (C, sk, D) where sk is the secret key that matches pk,

#Ā»

D = DecS (C, dID ) and C may or may not be encrypted under ID and pk.

#Ā»

Following common practice, we consider the two kinds of adversaries.

1. A Type-I adversary that models any coalition of rogue users, and who aims

to break the conļ¬dentiality of another userā™s ciphertext.

2. A Type-II adversary that models a curious KGC, who aims to break the

conļ¬dentiality of a userā™s ciphertext1 .

We use the common security model in which the adversary plays a two-phased

game against a challenger. The game is modeled by the experiment below, X ā

{I, II} denotes whether an PPT adversary A = (Aļ¬nd , Aguess ) is of Type-I or II,

and determines the allowed oracle queries O and the auxiliary data Aux.

Deļ¬nition 2. Experiment ExpCCAā’X (Ī»)

A

$

(Pub, Msk) ā Setup(1Ī» )

#Ā»

(m0 , m1 , pkā— , IDā— , state) ā AO (Pub, Aux)

$

ļ¬nd

# Ā»ā—

b ā {0, 1}, C ā Enc(mb , ID , pkā— )

$ ā—$

$

b ā AO (C ā— , state)

guess

If (|m0 | = |m1 |) āØ (b = b ) then return 0 else return 1

O is a set of oracles ExtractO(Ā·), UskO(Ā·), DecOS (Ā·, Ā·), DecOU (Ā·, Ā·, Ā·), DecO(Ā·, Ā·, Ā·).

Variables marked with ā— refer to challenges by the adversary. The adversary

#Ā»

chooses a public key pkā— and an ID-vector IDā— to be challenged with, and

the challenger returns a challenge ciphertext C ā— . The following two deļ¬nitions

prohibit the adversary from trivially using the oracles to query for the answer

to (parts of) the challenge.

Deļ¬nition 3. A hierarchical security-mediated certiļ¬cateless encryption scheme

is (t, qE , qD , ) CCA-secure against a Type-I adversary if | Pr[ExpCCAā’I (Ī») =

A

1] ā’ 2 | ā¤ for all t-time adversary A making at most qE extraction queries and

1

qD decryption queries (of any type), subjects to the following constraints:

Aux = ā…, i.e. no auxiliary information is given to the adversary.

1.

#Ā» #Ā» #Ā»

No ExtractO(ID ) query throughout the game, where ID is a preļ¬x of IDā— .

2.

No UskO(pk) query throughout the game for any pk.

3.

#Ā»

No DecOS (C ā— , IDā— ) query throughout the game.

4.

#Ā»

No DecO(C ā— , IDā— , pkā— ) query throughout the game.

5.

All public keys in the game are chosen by the adversary. It is natural to assume

the adversary knows the corresponding secret keys.

1

A rogue SEM is weaker than a Type-II adversary.

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

Deļ¬nition 4. A hierarchical security-mediated certiļ¬cateless encryption scheme

is (t, qK , qD , ) CCA-secure against a Type-II adversary if | Pr[ExpCCAā’II (Ī») =

A

1] ā’ 1 | ā¤ for all t-time adversary A making at most qD decryption queries (of

2

any type), subjects to the following conditions:

1. Aux = (Msk, {pkā— , Ā· Ā· Ā· , pkā—K }), i.e. A is given the master secret and a set of

1 q

challenge public keys.

2. pkā— ā {pkā— , Ā· Ā· Ā· , pkā—K }, i.e. the challenge public key must be among the set

1 q

given by the challenger.

3. No UskO(pk) query throughout the game if pk ā {pkā— , Ā· Ā· Ā· , pkā—K } or pk = pkā— .

/ 1 q

ā—

ā—

4. No DecO (C , pk , D) query throughout the game, where D is outputted by

U

the algorithm DecS (C ā— , dIDā— ).

#Ā»

# Ā»ā— ā—

5. No DecO(C ā— , ID , pk ) query throughout the game.

Since Msk is given to the adversary, the challenge public key must be in the set

given by the challenger.

3.4 Discussions on Our Choices for Deļ¬nition

This section explains the intuitions behind the choices made in formulating our

deļ¬nition and highlights the relationship between existing deļ¬nitions and ours.

User key generation. In order to support more general applications like TRE,

the interface for the algorithms needs a more general syntax. A subtle change is

that our user key generation algorithm KGen only takes the system parameter as

input but not the identiļ¬er. In some CLE schemes [2,24,27,30] the inclusion of

the identiļ¬er, or the trapdoor for an identiļ¬er, is essential for the generation of

the user public key. For these schemes, KGen can be executed only after Extract,

so straightforward adaption results in ineļ¬cient TREs in which the size of the

user public key grows linearly with the number of supported time periods.

Simpliļ¬cation of Type-I adversary. In existing models for 1-level CLE [1,17],

#Ā»

ExtractO query of IDā— is allowed; if such a query is issued, the challenge public

key pkā— can no longer be chosen by the adversary. In our discussion, we sepa-

rate this behavior from the Type-I model and consider this type of adversarial

#Ā» #Ā» #Ā»

behavior (ExtractO(ID ) where ID is a preļ¬x of IDā— ) as a weaker variant of,

and hence covered by, a Type-II adversary. It is true that our resulting deļ¬-

nition for Type-I adversary is weaker, but the āmissing partā is not omitted

from the security requirement since CLEs must consider Type-II adversaries;

this simpliļ¬cation was justiļ¬ed and adopted in [22, Section 2.3].

Existing models also allow full private key extraction for the public keys pre-

pared by the challenger. In our Type-I game, all of the public keys to be attacked

are generated by the adversary, so UskO query is prohibited. The remaining sce-

nario, where the adversary intends to attack a public key given by the challenger,

is also a weaker variant of our Type-II model. To conclude, we keep the essence

of the existing models, and include the adversarially chosen public keys (for

Type-I) and UskO (for Type-II) to match with TRE.

General Certiļ¬cateless Encryption and Timed-Release Encryption 133

Strong decryption oracle. In our deļ¬nition, the decryption oracle works even

if the public key is adversarially chosen but the secret key is not supplied. The

original deļ¬nition of CLE [1] does not allow a strong decryption oracle for curious

KGC adversary, but it is considered in recent work [17]. Adding the following

restriction weakens Deļ¬nition 4 to correspond to a Type-IIā’ attack:

#Ā»

5. (Type-IIā’ ) No DecO(C, ID, pk) query throughout the game for any C if pk ā /

ā— ā—

{pk1 , Ā· Ā· Ā· pkqK }, unless the corresponding secret key sk is supplied when the

ńņš. 48 |