security requirements of the asymmetric and symmetric parts of the hybrid en-

cryption scheme can be completely separated and studied independently. Addi-

tionally, as pointed out in [22] and [2], the KEM/DEM framework is suitable

for streaming applications since the receiver does not need to bu¬er the entire

ciphertext. Indeed, the KEM/DEM approach to construct hybrid encryption

schemes has gained popularity among researchers and has been supported by

several standards including the ISO/IEC standard on public key encryption [16].

We argue that in spite of the new frameworks™ e¬ectiveness in explaining some

hybrid encryption schemes, the original KEM/DEM framework is still very attrac-

tive as it is standardized, it allows “stream processing” and gives the users ¬‚exi-

bility in choosing the symmetric encryption algorithm for DEM. On the contrary,

the Tag-KEM/DEM framework does not provide stream processing in general and

the new framework proposed in [15] requires DEM to be one-time AE-OT, which

is strictly stronger than one-time CCA-secure symmetric encryption.

Last but not least, there is in our opinion a pedagogical reason for stick-

ing to the original KEM/DEM framework. The KEM/DEM framework is in-

tuitive and easier to understand by the general information security public, in

particular by implementors. We think there is no need for individuals outside

the cryptographic community to update their cryptographic knowledge at every

new theoretical advancement. Providing intuitive sound and stable cryptographic

frameworks could help to obtain less error-prone end-systems.

1.2 Our Contributions

First, we present a simple but useful method that transforms a CCCA-secure

KEM to a CCA-secure KEM. The basic idea behind this transformation is to

3

Readers are referred to Section 2.1 for the detailed reviews on the CCA and CCCA

notions of KEM.

360 J. Baek et al.

authenticate the ciphertext output by the CCCA-secure KEM using a secure

Message Authentication Code (MAC) with a (symmetric) key generated by the

CCCA-secure KEM.

Since the KEM parts of both Kurosawa and Desmedt™s [17], and Hofheinz and

Kiltz™s [15] hybrid encryption schemes are known to be CCCA-secure [15], our

transformation yields two new CCA-secure KEMs based the Decisional Di¬e

Hellman (DDH) problem. We discuss in Section 4.2 that these KEM schemes

are the most e¬cient CCA-secure KEMs in the literature to our knowledge.

We also obtain new hybrid encryption schemes by combining our new KEM

schemes with any one-time CCA-secure DEMs. However, a particular interest-

ing case is when they are combined with length-preserving CCA-secure DEMs

[18,21]. In this case, the resulting hybrid encryption schemes are as e¬cient

as Kurosawa-Desmedt™s [13]4 and Hofheinz and Kiltz™s [15] hybrid encryption

schemes in terms of ciphertext length and computation time. In contrast to the

latter, the CCA-security of the new schemes can be explained in the original

KEM/DEM framework.

1.3 Further Discussion on Related Work

The concept of chosen ciphertext security for public key encryption was ¬rst

introduced by Naor and Yung [19] and further developed by Dolev, Dwork and

Naor [12]. Relations between the non-malleability and indistinguishability frame-

works for chosen ciphertext security were clari¬ed by Bellare et al. [4]. As men-

tioned previously, the KEM/DEM framework for constructing hybrid encryption

was introduced by Cramer and Shoup [9].

After the KEM/DEM framework emerged, Abe et al. [1] proposed a new

framework, called “Tag-KEM/DEM”. Di¬erent from KEMs, the encapsulation

algorithm [1,2] of a Tag-KEM takes an arbitrary string called “tag” as input Sub-

sequently, a hybrid encryption scheme can be built regarding a DEM ciphertext

as a tag [1].

More recently, Hofheinz and Kiltz [15] introduced a new security notion for

KEM, “security against constrained chosen ciphertext attacks (CCCA)”. This

notion is weaker than the normal chosen ciphertext security for KEM. In CCCA

an attacker makes a decapsulation query by presenting a ciphertext together with

a boolean predicate, which represents some a-priori knowledge about the decap-

sulated key. Hofheinz and Kiltz showed that a hybrid encryption scheme in which

a DEM encrypts a plaintext message using a key output by the CCCA-secure

KEM is CCA-secure if the underlying DEM is a one-time secure authenticated

encryption scheme (AE-OT secure). However, as pointed out in Appendix D of

4

The original construction of Kurosawa and Desmedt™s hybrid encryption scheme

given in [17] is based on the information theoretically secure key derivation function

(KDF) and message authentication code (MAC). In [13], it is shown that these

primitives can be replaced by computationally secure ones. Throughout this paper,

“Kurosawa and Desmedt™s hybrid encryption scheme” refers to the scheme with

computationally secure KDF and MAC discussed in [13].

Constructing Strong KEM from Weak KEM 361

[15], authenticated encryption is a strictly stronger security notion than chosen-

ciphertext security for symmetric encryption as shown in [5]. Moreover, length-

preserving authenticated encryption does not exist while length-preserving CCA-

secure symmetric encryption does.

As a variant of Kurosawa and Desmedt™s KEM scheme, Okamoto [20] proposed

a new KEM scheme. Although this KEM scheme is validity-check-free, it requires

a special type of pseudo random function, called “πPRF”. However constructing

a πPRF family is still an open problem [20].

2 Preliminaries

In this section, we review the primitives used throughout this paper.

First, we introduce some notations. We use the notation A(·, . . . , ·) to de-

note an algorithm, with input arguments separated by commas. (Note that

our underlying computational model is a probabilistic Turing Machine.) We use

a ← A(x1 , . . . , xn ) to denote the assignment of an element from the output of A

par

on input (x1 , . . . , xn ) to the variable a. By “ ’” we denote “parsing operation”.

par

For instance, a ’ (b, c) means that a string a is parsed as (b, c).

2.1 Key Encapsulation Mechanism (KEM) and Its Security Notions

Key Encapsulation Mechanism (KEM). The KEM scheme, denoted KEM, con-

sists of the following algorithms [9,22,16].

“ KEM.Gen(1» ): A probabilistic algorithm that generates a public/private key

pair (pk, sk).

“ KEM.Encap(pk): A probabilistic algorithm that generates a ciphertext/key

pair (φ, K).

“ KEM.Decap(sk, φ): An algorithm that outputs either a key K or a special

symbol ⊥ (meaning “reject”).

CCA-Security for KEM. The security notion for KEM against (adaptive) cho-

sen ciphertext attack, is de¬ned as follows. Let A be an attacker. Consider the

following game in which A interacts with the challenger.

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, where SK denotes the

key space. It then picks β ∈ {0, 1} at random and gives (pk, φ— , Kβ ) to A.

—

Phase 2: A submits ciphertexts, each of which is denoted by φ. On receiving

φ, the challenger runs the decapsulation algorithm on input φ and passes the

resulting decapsulation to A. At the end of this phase, A outputs its guess

β ∈ {0, 1}.

362 J. Baek et al.

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

1

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

A,KEM

2

We say that KEM is CCA-secure if AdvCCA (») = maxA AdvCCA (») is

A,KEM

KEM

negligible for any attacker A.

Constrained CCA-Security for KEM. Hofheinz and Kiltz [15] de¬ned a new se-

curity notion for KEM, called constrained chosen-ciphertext security (CCCA).

This is a relaxed security notion in which an attacker is allowed to make a de-

capsulation query only if it has some a-priori knowledge about the decapsulated