AdvCCA (») ¤ 4AdvCCCA (») + 5AdvROR (») + qD AdvSUF-CMA (»),

KEM KEM KDF MAC

where » denotes the security parameter and qD denotes the number of decapsu-

lation queries.

The proof is given in Appendix A.

Constructing Strong KEM from Weak KEM 365

4 Applications of Our KEM Construction

4.1 New CCA-Secure KEMs from Well-Known CCCA-Secure

KEMs

Using our method that transforms CCCA-secure KEM to CCA-secure KEM, one

obtains new CCA-secure KEM schemes from the well-known CCCA-secure KEM

schemes in the literature, the Kurosawa-Desmedt KEM [17] and the Hofheinz-

Kiltz KEM [15] schemes.

First we describe the new KEM scheme KDKEM, which is constructed using

the Kurosawa-Desmedt KEM scheme. Let G be a ¬nite group, generated by g1

and g2 . Assume that the order of this group is p, a prime, and that DDH problem

is hard in this group. (The formal de¬nition of the DDH problem can be found in

Appendix B.) Also, assume that the key derivation function KDF and the MAC

scheme MAC satisfy the security requirements described in Section 2.2. Let TCR

denote a target collision resistant hash function as de¬ned in [17]. In Figure 2,

we describe each sub-algorithm of KDKEM.

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

par

r ← Z— ; u1 ← g1 ; u2 ← g2

$

φ ’ (u1 , u2 , σ)

r r

Select KDF, MAC, TCR p

± ← TCR(u1 , u2 ) ± ← TCR(u1 , u2 )

x 1 , x 2 , y 1 , y 2 ← Z—

$

p

θ ← (u1 , u2 ) ∈ G2 K ← ux1 +y1 ± u2 2 +y2 ±

˜ x

c ← g1 1 g2 2 ; d ← g1 1 g2 2

x x y y

1

K ← cr dr± ∈ G (K, κ) ← KDF(K)

˜ ˜

pk ← (», p, g1 , g2 , c, d)

(K, κ) ← KDF(K) ˜

sk ← (x1 , x2 , y1 , y2 ) If MAC.Ver(κ, σ, (u1 , u2 )) = 1

σ ← MAC.Sign(κ, θ)

pk ← (pk , KDF, MAC) return K

φ ← (θ, σ) Else return ⊥

sk ← sk

Return (φ, K)

Return (sk, pk)

Fig. 2. CCA-Secure KEM from Kurosawa-Desmedt CCCA-Secure KEM [17]

Recall that according to Theorem 1, if the Kurosawa-Desmedt KEM scheme is

CCCA-secure, the above KDKEM scheme is CCA-secure. In [15], the Kurosawa-

Desmedt KEM scheme is shown to be CCCA-secure assuming that the DDH

problem is hard. Thus the KDKEM scheme is CCA-secure.

Another KEM scheme HKKME which is constructed using the Hofheinz-Kiltz

KEM scheme [15] can be described as follows. Let G be a ¬nite group as de¬ned

previously. Let g be a generator of G. Assume that KDF and MAC are as de¬ned

in Section 2.2. Figure 3 describes each sub-algorithm of the scheme HKKEM.

Since the the Hofheinz-Kiltz KEM scheme is shown to be CCCA-secure as-

suming that the DDH problem is hard, the HKKEM scheme presented in Table

3 is CCA-secure.

We remark that the random oracle model is not required to analyze the two

KEM schemes presented above.

366 J. Baek et al.

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

par

r ← Z— ; c ← g r

$ $

φ ’ (c, π, σ)

Select KDF, TCR, MAC p

t ← TCR(c); π ← (ut v)r If c ∈ G or π ∈ G return ⊥

x 1 , y 1 , y 2 , w ← Z—

$

/ /

p

θ ← (c, π) ∈ G2 t ← TCR(c)

’x1 /y2

h←g ; u←g w

K ← hr ∈ G If cxt+y = π return ⊥

˜

v ← g ’y1 /y2 h1/y2

(K, κ) ← KDF(K) K ← cx1 t+y1 π y2

˜ ˜

pk ← (u, v) ∈ G2

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

sk ← (x1 , y1 , y2 ) ∈ Z3 p

φ ← (θ, σ) If MAC.Ver(κ, σ, (c, π)) = 1

pk ← (pk , KDF, MAC)

Return (φ, K) return K

sk ← sk

Else return ⊥

Return (sk, pk)

Fig. 3. CCA-Secure KEM Constructed from Hofheinz-Kiltz CCCA-Secure KEM [15]

4.2 E¬ciency Comparisons with Other Schemes

We now compare the KDKEM and HKKEM schemes with other well-known KEM

schemes.

First, we compare the length of ciphertext, the cost for encapsulation and

decapsulation in KDKEM and HKKEM with those of the KEM schemes con-

structed by choosing a key K uniformly at random (from an appropriate DEM-

key space) and encrypting it with CCA-secure hybrid encryption schemes by

Kurosawa and Desmedt [13] and Hofheinz and Kiltz [15]. We denote the two

KEM schemes constructed in this way by KDHE2KEM and HKHE2KEM respec-

tively. (In [2], it is shown that these KEM schemes are CCA-secure.) We also

compare the length of ciphertext and the cost for encapsulation/decapsulation of

our schemes with those of Cramer and Shoup™s [9] KEM scheme, named “CS3”.

Note that the security of all the schemes is based on the DDH problem and does

not depend on random oracles. In Table, 1, we summarize the comparisons.

Next, we compare the length of ciphertext and the cost for encryption and

decryption of the hybrid encryption schemes constructed by combining our

two CCA-secure KEM schemes with length-preserving one-time CCA-secure

DEMs [21] (following the KEM/DEM framework) with those of Kurosawa and

Desmedt™s [13] CCA-secure hybrid encryption scheme; Hofheinz and Kiltz™s [15]

CCA-secure hybrid encryption scheme; and the hybrid encryption schemes con-

structed by combining length-preserving CCA-secure DEMs with Cramer and

Shoup™s [9] KEM scheme. We assume that the length of the plaintext to be en-

crypted is the same for all the schemes. We assume that the same MAC algorithm

is used. In Table 2, we summarize the comparisons.

We observe that compared to the previous CCA-secure KEM schemes based

on the DDH problem, the KEM schemes obtained by our proposed transforma-

tion (Figures 2 and 3) satisfy that either:

“ are more computationally e¬cient (saving one exponentiation in encapsula-

tion/decapsulation) or

“ have shorter ciphertext (about 80 bits).

Constructing Strong KEM from Weak KEM 367

Table 1. E¬ciency comparison for DDH-based CCA-secure KEMs in the standard

model. KDHE2KEM and HKHE2KEM are the KEM schemes constructed by choosing

a key K uniformly at random and encrypting it with CCA-secure hybrid encryption

schemes by Kurosawa and Desmedt [13], and Hofheinz and Kiltz [15] resp. CS3 is

the CCA-secure KEM proposed by Cramer& Shoup in [9]. |p| is the bit-length of

the representation of an element in G. |enc| denotes the output bit-length of a block

cipher used to encrypt a random key K, and |σ| denotes the length of the output of

a MAC. macG denotes the MAC generation operation, and macV denotes the MAC