We denote a key chosen randomly from SK by K0 . Note here that the

challenger picks β ∈ {0, 1} at random and returns (φ— , Kβ ) to A.

—

We denote by S0 the event β = β, where β is a bit output by A at the end

of the game. (We use a similar notation S1 , S2 , . . . for all modi¬ed games

G1 , G2 , . . . respectively).

“ Game G1 : In this game, we modify the generation of the challenge ciphertext

˜—

in such a way that when β = 0, we choose K0 at random from SK and ˜

— —

compute (K0 , μ) ← KDF(K ˜ 0 ), where μ ∈ Sκ is an arbitrary string.

Hence we get

1

| Pr[S0 ] ’ Pr[S1 ]| = | Pr[S0 |β = 0] ’ Pr[S1 |β = 0]| ¤ AdvROR (»),

B,KDF

2

for some B that breaks the ROR-security of KDF.

“ Game G2 : In this game, we add another special rejection rule called SR2 to

the decapsulation algorithm of the previous game.

SR2 If a ciphertext φi = (θi , σi ) such that θi = θ— is submitted in Phase 2

of the IND-CCA game then immediately output ⊥.

Let F2 be an event that a ciphertext (submitted to the decapsulation oracle)

is rejected under the rule of SR2 but would have been accepted under the

rule of Game G2 . Since Game G1 and Game G2 proceed identically until this

event happens and in particular, S1 § ¬F2 and S2 § ¬F2 are identical. Thus

we have

| Pr[S1 ] ’ Pr[S2 ]| ¤ Pr[F2 ].

Now, we construct an attacker C that breaks IND-CCCA of the scheme KEM

using A as subroutine as follows. 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(·). Below, we describe a complete speci¬cation of C.

Algorithm C(pk , θ— , Kb )

˜—

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

(K — , κ— ) ← 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

If CDecap does not reject5 then return b = 1 and halt

Note that σi must be di¬erent from σ — because by de¬nition A is not allowed to

5

issue the challenge ciphertext (θ— , σ — ) as a decapsulation query.

Constructing Strong KEM from Weak KEM 371

Else send ⊥ to A and continue

Else

Get Ki or ⊥ from CDecap and simulate the decapsulation

˜

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

˜

If A stops, output b = 0

First, assume that b = 1 in the above construction. In this case, K — and

κ— are generated from K1 , i.e., K — = Kβ and κ— = κ— when β = 1. Now

˜— —

β

consider the event b = 1. By the construction of C given above, b = 1

happens when the decapsulation query (θ— , σi ) (such that σi = σ — ) is not

rejected. But according to SR2, this query should be rejected straight away.

That is, the event b = 1 when b = 1 is equivalent to the event F2 when

β = 1. Hence, we have Pr[F2 |β = 1] = Pr[b = 1|b = 1].

Now, assume that b = 0 in the above construction. Let F2 represent

the event that b = 1 when b = 0. We then modify the above construction

of C so that (K — , κ— ) is selected independently and uniformly at random

from SK — Sκ . Let F2 be an event that b = 1 under this modi¬cation. It

is easy to see that | Pr[F2 ] ’ Pr[F2 ]| ¤ 2AdvROR (») for some attacker B

B,KDF

that breaks the ROR-security of KDF. Now, pick j ∈ {1, . . . , qD } at random

and de¬ne F2 be an event that for the jth ciphertext ψj (submitted to the

decapsulation oracle), b = 1. Note that we have Pr[F2 ] ¤ qD Pr[F2 ]. We

now prove the following claim.

Claim. Pr[F2 ] ¤ AdvSUF-CMA (»).

D,MAC

Proof. Let D be a SUF-CMA attacker for MAC. Assume that D is given

access to the MAC-generation oracle MAC.Sign(κ— , ·), where κ— is chosen

uniformly at random from Sκ . First, D generates (sk, pk) and gives pk to A.

D then parses pk as (pk , KDF, MAC), computes (θ— , K) ← KEM .Encap(pk ).

˜

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

gives (θ— , σ — ) as a challenge ciphertext to A. (Note that (θ— , σ — ) is identi-

cally distributed as the challenge ciphertext that A is given from the above

modi¬ed C where κ— is chosen independently and uniformly at random.) D

responds to A™s decapsulation queries using sk. When A submits (θ— , σi )

such that MAC.Ver(κ— , σi , θ— ) = 1, D outputs σi as a forgery. (Note that σi

was never returned by D™s MAC-generation oracle.) Since the event b = 1

occurs when (θ— , σi ) is not rejected, i.e. MAC.Ver(κ— , σi , θ— ) = 1, we have

Pr[F2 ] ¤ AdvSUF-CMA (»).

D,MAC

Consequently, we obtain

Pr[F2 ] = Pr[b = 1|b = 0] ¤ 2AdvROR (») + qD AdvSUF-CMA (»).

B,KDF D,MAC

Note that by de¬nition 1 | Pr[b = 1|b = 1] ’ Pr[b = 1|b = 0]|=AdvIND-CCCA (»).

C,KEM

2

Thus, we get

Pr[F2 |β = 1] ¤ 2AdvROR (») + 2AdvIND-CCCA (») + qD AdvSUF-CMA (»).

B,KDF C,KEM D,MAC

372 J. Baek et al.

Next, consider the case β = 0. Recall that by the rule set in Game G1 , when

˜— —

β = 0, K0 is chosen at random from SK and K0 is obtained by computing

˜

— ˜—

(K0 , μ) ← KDF(K0 ) for some arbitrary string μ ∈ Sκ . We now slightly

modify the above algorithm C in such a way that K — is (always) obtained by

computing (K — , μ) ← KDF(K0 ), where K0 is chosen uniformly at random

˜— ˜—

from SK . That is, K — is distributed independently from other variables.

˜

Hence, we have Pr[F2 |β = 0] = Pr[b = 1|b = 1].

Also, we can show in exactly the same way as done before that

Pr[b = 1|b = 0] ¤ 2AdvROR (») + qD AdvSUF-CMA (»)

B,KDF D,MAC

Consequently, we have

Pr[F2 ] ¤ 2AdvROR (») + 2AdvIND-CCCA (») + qD AdvSUF-CMA (»).

B,KDF C,KEM D,MAC

“ Game G3 : In this game, we modify the generation of the challenge ciphertext

in such a way that κ— is obtained by computing (ν, κ— ) ← KDF(Kβ ) for

˜—

1 1

arbitrary ν ∈ SK . Hence, when β = 1, the views of A in Game G3 and Game

G2 are identically distributed. Thus we get