boolean predicate pred : SK ’ {0, 1}, where SK denotes the key space of key

K embedded in a given ciphertext φ. Then, the decapsulated key K is returned

only if pred(K) = 1; otherwise ⊥ is returned.

Formally, let A be the attacker. On receiving the decapsulation query con-

sisting on a pair of ciphertext and predicate (φ, pred), the “constrained decap-

sulation oracle” CDecap outputs K = KEM.Decap(sk, φ) if pred(K) = 1 and

otherwise it outputs ⊥. Now consider the following game.

Phase 1: The challenger runs the key generation algorithm providing 1»

as input to generate a public/private key pair (pk, sk). The challenger then

computes a challenge ciphertext φ— and a key K1 by running the encapsu-

—

—

lation algorithm. It also picks K0 ∈ SK at random. It then picks β ∈ {0, 1}

at random and gives (pk, φ— , Kβ ) to A.

—

Phase 2: A submits a pair of ciphertext and predicated, each of which is

denoted by (φ, pred), where φ = φ— . On receiving (φ, pred), the challenger

runs CDecap on input (φ, pred) and passes the resulting decapsulation to A.

At the end of this phase, A outputs its guess β ∈ {0, 1}.

We de¬ne the attacker A™s success probability by

1

AdvCCCA (») = Pr[β = β] ’ .

A,KEM

2

Notice that this notion becomes CCA (for KEM) when “pred” always outputs 1

for any input but is equivalent to the con¬dentiality against passive attack when

“pred” always outputs 0 for any input. Hence, in general, CCCA is weaker than

CCA. Indeed, admissible predicates must satisfy that the amount of uncertainty

the attacker has about the key is negligible. Formally, let QA denote the number

of decapsulation queries made by the attacker A. Then for attacker A in the

above experiment we de¬ne plaintext uncertainty uncertA (») as follows:

1

Pr[predi (K) = 1 | K ← SK ]

$

uncertA (») =

QA

1¤i¤QA

where predi : SK ’ {0, 1} is the predicate A submits with the i-th decapsulation

query. An attacker A is said to be “valid” if uncertA (») is negligible in ». We say

Constructing Strong KEM from Weak KEM 363

that KEM is CCCA-secure if AdvCCCA (») = maxA AdvCCCA (») is negligible

A,KEM

KEM

for any admissible attacker A.

We remark that before the CCCA notion was de¬ned, Abe et al. [2] had de-

¬ned a very similar notion called “LCCA”. In LCCA, an attacker also has access

to the “restricted decapsulation oracle”, which outputs a key (decapsulation) of

a queried ciphertext only when a certain predicate taking the key as input re-

turns 1. They showed that the KEM part of Kurosawa and Desmedt™s hybrid

encryption scheme is actually LCCA-secure. We note that our KEM construction

based on the CCCA-secure KEM, which will be presented in the next section, is

still secure even if the underlying KEM is assumed to be LCCA-secure. However,

due to its rigor (e.g. precise de¬nition of uncertainty), we use the CCCA notion.

2.2 Message Authentication Code and Key Derivation Function

Message Authentication Code. Let MAC = (MAC.Sign, MAC.Ver) be a MAC

(Message Authentication Code) scheme whose key space Sκ is de¬ned by the

security parameter ». On input (κ, m), where κ(∈ Sκ ) and m denote a MAC

key and a message resp., MAC.Sign produces a MAC (tag) σ. On input (κ, σ, m),

MAC.Ver outputs 1 if (σ, m) is valid with respect to κ, or outputs 0, otherwise.

In the literature, there exist several unforgeability notions for MAC. The

one we need in this paper is “strong unforgeability under chosen message at-

tack (SUF-CMA)” [5], which can be de¬ned as follows. Given access to the

oracle MAC.Sign(κ, ·) where κ is chosen uniformly at random from Sκ , an at-

tacker A outputs (m, σ) such that MAC.Ver(κ, σ, m) = 1 and σ was never re-

turned by MAC.Sign(κ, ·). We de¬ne the attacker A™s success probability by

AdvSUF-CMA (»). As usual, we say that MAC is SUF-CMA secure if

A,MAC

AdvSUF-CMA (») = maxA AdvSUF-CMA (») is negligible for any admissible at-

A,MAC

MAC

tacker A.

Though this notion seems stronger than usual UF-CMA notion for MAC, as

pointed out in [5], any pseudorandom function (PRF) is a SUF-CMA secure

MAC, and many practical MAC schemes, e.g., HMAC and CBC-MAC are actu-

ally SUF-CMA secure.

Key Derivation Function. Also, we will need the key derivation function [9,13],

denoted KDF, for our construction of the KEM scheme. KDF satis¬es the fol-

lowing security requirement, called “real or random (ROR)”. Assume that KDF

takes an element a chosen uniformly at random from the appropriate domain

Sa . Let l be the length of the output of KDF, which depends on the security

parameter ». We de¬ne the security of KDF in the ROR sense, with respect to

an attacker A, as follows.

AdvROR (») = | Pr[a ← Sa : 1 ← A(1» , KDF(a))]

$

A,KDF

R

’ Pr[a ← Sa ; μ ← {0, 1}l : 1 ← A(1» , μ)]|.

$

We say that KDF is ROR-secure if AdvROR (») = maxA AdvROR (») is

A,KDF

KDF

negligible for any admissible attacker A.

364 J. Baek et al.

3 Our Construction of CCA-Secure KEM from

CCCA-Secure KEM

Description. Let KEM = (KEM .Gen, KEM .Encap, KEM .Decap) be a KEM

scheme. Let MAC = (MAC.Sign, MAC.Ver) be a MAC scheme; and let KDF :

SK ’ SK — Sκ be a key derivation function, where SK denotes the key space

˜ ˜

of KEM ; SK denotes the key space of the resulting KEM scheme KEM (i.e.,

the key space of a given DEM scheme); and Sκ denotes the key space of the

MAC scheme MAC. Based on these primitives, we construct a new KEM scheme

KEM = (KEM.Gen, KEM.Encap, KEM.Decap) as described in Figure 1.

KEM.Gen(1» ) KEM.Encap(pk) KEM.Decap(sk, φ)

par par

(pk , sk ) ← KEM .Gen(1» ) pk ’ (pk , KDF, MAC) sk ’ sk

par

(θ, K) ← KEM .Encap(pk ) φ ’ (θ, σ)

˜

Select KDF and MAC

pk ← (pk , KDF, MAC) (K, κ) ← KDF(K) K ← KEM .Decap(sk , θ)

˜ ˜

sk ← sk σ ← MAC.Sign(κ, θ) (K, κ) ← KDF(K)˜

φ ← (θ, σ)

Return (pk, sk) If MAC.Ver(κ, σ, θ) = 1

Return (φ, K) then return K

Else return ⊥

Fig. 1. Our Generic Construction of CCA-Secure KEM from CCCA-Secure KEM

We note that the above technique of applying a MAC to a ciphertext has widely

been used in the literature. For example, Boneh and Katz [7] used a similar tech-

nique to convert an identity-based encryption scheme to a CCA-secure (normal)

public key encryption scheme. Another example is “Encrypt-then-MAC” construc-

tion of authenticated encryption given in [5]. Our construction shows that this pow-

erful technique also can yield a conversion from CCCA-secure KEM to CCA-secure

KEM.

Security Analysis. We show that the generic construction of KEM presented in

Figure 1 is CCA-secure assuming that the underlying KEM , MAC and KDF

schemes are secure in the sense de¬ned in the previous section. More precisely,

we prove the following theorem.

Theorem 1. If KEM is CCCA-secure; MAC is SUF-CMA secure; and KDF is

ROR-secure, the scheme KEM described in Figure 1 is CCA-secure. That is, we