| Pr[S2 ]’Pr[S3 ]| =| Pr[S2 |β = 1]+Pr[S2 |β = 0]’Pr[S3 |β = 1]’Pr[S3 |β = 0]|

2

1

= | Pr[S2 |β = 0] ’ Pr[S3 |β = 0]|.

2

The above equality implies that we only need to consider the case β = 0.

Now we construct again attacker C that breaks IND-CCCA of KEM using

A as subroutine: As with the case of C, we assume that C is provided with

(pk , θ— , Kb ) where b is a random bit and that C de¬nes the function predicate

˜—

pred as

1 : if MAC.Ver(κ, σ, θ) = 1

˜

pred(K) =

0 : otherwise

where K = KEM .Decap(sk, θ) and (K, κ) = KDF(K). Note here that σ ∈

˜ ˜

RMAC , where RMAC denotes the range of the MACs, is hard-coded into

pred(·).

Algorithm C(pk , θ— , Kb )

˜—

˜— $ ˜

pk ← (pk , KDF, MAC); Send pk to A; K 0 ← SK

˜—

(K — , μ) ← KDF(K 0 ); (ν, κ— ) ← KDF(Kb ); σ — ← MAC(κ— , θ— )

˜—

φ— ← (θ— , σ — ); Send (φ— , K — ) to A

If A submits φi = (θi , σi ) to the decapsulation oracle

Submit (θi , predi ) to its CDecap oracle

If θi = θ— then return ⊥

Else

Get Ki or ⊥ from CDecap and simulate the decapsulation

˜

oracle of A if Ki is returned or send ⊥ to A

˜

If A outputs β , output it as b

Constructing Strong KEM from Weak KEM 373

First, assume that b = 1 in the above construction. In this case, σ — is gen-

˜—

erated from the correct key K1 while K — is computed from the key K 0

˜—

chosen randomly from SK . Hence the view of A simulated by the algo-

˜

rithm B4 is the same as that of A in Game G2 at β = 0. Thus, we have

Pr[S2 |β = 0] = Pr[b = 0|b = 1].

Now, assume that b = 0 in the above construction. In this case, σ — is

˜—

generated using K0 chosen randomly from SK . Notice that the view of A

˜

in the above simulation is almost the same as that in this game (Game G3 )

when β = 0 except that in this game, σ — and K — are generated from the

single input to KDF while they are independently generated in the above

simulation. However, by the result of [2], we get | Pr[S3 |β = 0] ’ Pr[b =

0|b = 0]| ¤ 4AdvROR (»).

B,KDF

Putting all the bounds together, we get

1

| Pr[S2 ] ’ Pr[S3 ]| = | Pr[S2 |β = 0] ’ Pr[S3 |β = 0]|

2

1

¤ | Pr[b = 0|b = 1] ’ Pr[b = 0|b = 0] ’ 4AdvROR (»)|

B,KDF

2

¤ AdvIND-CCCA (») + 2AdvROR (»).

C,KEM B,KDF

Observe that we can build up C again using A in this game (Game G3 ).

Algorithm C(pk , θ— , K — )

˜

b

pk ← (pk , KDF, MAC); Send pk to A

(K — , κ— ) ← KDF(Kb ); σ — ← MAC(κ— , θ— )

˜—

φ— ← (θ— , σ — ); Send (φ— , K — ) to A

If A submits (θi , σi ) to the decapsulation oracle

submit (θi , predi ) to its CDecap oracle

to get Ki or ⊥. Simulate the decapsulation oracle

˜

of A if Ki is returned or send ⊥ to A

˜

If A outputs β , output it as b

Note that the above C perfectly simulates the environment of A in Game

G3 . Consequently, we have

1

| Pr[S3 ] ’ | ¤ AdvIND-CCCA (»).

C,KEM

2

It remains to show that the attackers C™s against the IND-CCCA security of the

KEM are admissible, i.e. the corresponding plaintext uncertainty

1

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

˜ ˜$ ˜

uncertC (») =

QC

1¤i¤QC

is negligible for all PPT attackers C™s constructed in the above games. We proceed

to show the result for the attacker C in Game G2 , the result for C™s in Game G3 is

obtained identically. To this end, we build an attacker D against the SUF-CMA se-

curity of the MAC scheme MAC. D gets as input the security parameter », the de-

scription of MAC and access to the MAC generation oracle MAC.Sign(κ— , ·), where

374 J. Baek et al.

κ— is chosen uniformly at random from Sκ . D plays the role of the challenger for C.

D ¬rst runs (pk , sk ) ← KEM .Gen(») and computes (θ— , K) ← KEM .Encap(pk ).

˜

D then queries θ— to its MAC-generation oracle to get σ — = MAC.Sign(κ— , θ— ). D

then gives (θ— , σ — ) as a challenge ciphertext to C. Since D knows the secret key

sk , it can faithfully answer all of C™s queries to the constrained decapsulation or-

acle. In the beginning, D picks a random index j ← {1, . . . , QC }, where QC is the

number of queries to the constrained decapsulation oracle CDecap made by C. On

C™s j-th decapsulation query (θj , predσj ), D sets a fake predicate

§

if MAC.Ver(κ— , σj , θj ) = 1 § θj = θ— §

⎨1 :

σj was never returned by MAC.Sign(κ— , ·)

˜

predσj (K) :=

©

0: otherwise

where K||κ ← KDF(K) and outputs K if predσj (K) = 1. Note here that

˜ ˜

predσj (K) is de¬ned in terms of κ— ← Sκ , while for the real predicate predσj (K),

˜ $

(ν, κ— ) ← KDF(K) with K being chosen uniformly at random from SK . Now let

˜ ˜ ˜

˜ = predσ (K). Then,

˜

F4 denote the event that predσ (K) j j

Pr[predσj (K) = 1 | K ← SK ] ’ Pr[predσj (K) = 1 | K ← SK ] ¤ Pr[F4 ]

˜ ˜$ ˜ ˜ ˜$ ˜

It is easy to see that Pr[F4 ] ¤ AdvROR (»), for a suitable adversary B.

B,KDF

Therefore,

AdvSUF-CMA (») = Pr[MAC.Ver(κ— , σj , θ— ) = 1 § σj was never returned by

D,MAC

MAC.Sign(κ— , ·)]

1

Pr[predj (K) = 1] ≥

˜