0

[j0 ]

= RA0 R1 · · · Rkj0 Rkj · · · Rn0 , initializes stL0 to µ and ex-

sets RB0

0 +1

ecutes A0 (pk; RA0 ). If A0 makes the i-th query to the randomness oracle for

i ¤ kj0 , K0 sends Ri back to A0 . If A0 makes the i-th query to the random-

ness oracle for i > kj0 , the extraction has failed. In this case, K0 outputs fail

and terminates, (although we can prove that the extraction never failed). If A0

[j ]

makes the j-th decryption query C j for j < j0 , K0 computes (Mj 0 , stL0 ) ←

[j ] [j0 ]

L0 (pk, C j , RB0 , stL0 ; ρL0 ) and sends Mj back to A0 . If A0 makes the j0 -th

0

[j ] [j ]

decryption query C j0 , K0 computes (Mj00 , stL0 ) ← L0 (pk, C j0 , RB0 , stL0 ; ρL0 ),

0

[j ]

outputs (Mj00 , stK0 ), and terminates.

The only di¬erence between the behavior of K0 and that of EPA1+Dec,L0 (»)

Π,B0

[j0 ]

is as follows: K0 does not check whether Mj = Decsk (C j ) holds or not, al-

[j ]

though EPA1+Dec,L0 (») does. However, since the output Mj 0 of extractor L0 for

Π,B0

the EPA1 security is equal to Decsk (C j ) with overwhelming probability, this

+

[j ] [j ]

checking is unnecessary. Therefore, the messages M1 0 , . . . , Mj00 generated by

K0 are equal to Decsk (C 1 ), . . . , Decsk (C j0 ) with overwhelming probability.

Cramer-Shoup Satis¬es a Stronger Plaintext Awareness 117

[j ]

By using induction, we show that the output Mj00 = Decsk (C j0 ) of K0 is

equal to Decsk (Cj0 ) with overwhelming probability. Suppose that K0 succeeds

in outputting the decrypted plaintexts for j < j0 . From the de¬nition of K0 ,

adversary A0 and the subroutine A0 of K0 are given the same input pk, the

same random tape RA0 , and the same answer R1 , . . . , Rkj0 to the randomness

queries. From the induction hypothesis, both A0 and A0 are given the decrypted

plaintexts as an answers for the the ¬rst, . . ., (j0 ’ 1)-th decryption queries.

These facts mean that A0 and A0 makes the same j0 -th decryption query. That

[j ]

is, Cj0 = C j0 holds. Hence, Mj00 = Decsk (C j0 ) = Decsk (Cj0 ). This means that

K0 is successful.

We can see that the above proof becomes invalid if we consider not the EPA

security but computational PA security. Recall that the computational PA-ness

ensures the computational indistinguishability between a tuple (M1 , . . . , Mn ) of

outputs of extractor and (Decsk (C 1 ), . . . , Decsk (C n )), only if all C i are output by

the same adversary B0 with the same random tape RB0 . Here Decsk (C i ) is the

i-th decryption query of B0 .

[j0 ]

In the above proof, K0 inputs new RB0 to extractor L0 each times K0 is exe-

[1] [n ]

cuted. Therefore, we cannot conclude that the tuple (M1 , . . . , Mn00 ) of outputs

of L0 is computationally indistinguishable from (Decsk (C1 ), . . . , Decsk (Cn0 )), if we

only assume the computational PA-security of Π. Since an answer of K0 to the

[j ]

j0 -th encryption query of A0 is Mj00 , this means that K0 may not be a successful

extractor for the computational PA2 security.

3.3 Proof of Theorem 11

Proof. Let Π be a PKE which is computationally random-like and EPA1 secure.

From Theorem 12, Π is EPA1+ secure. Since Π is computationally random-

like, there exist a computationally random-like set X = X» and functions ± :

{0, 1} ’ X and β : X ’ {0, 1} satisfying the property described in De¬nition 8

and 7.

Let A0 be an adversary for the EPA2 security of Π and n0 be the number of

steps of A0 . In order to show that A0 has a successful extractor, we will construct

an adversary B0 for the EPA1+ security, which executes A0 , obtains random bits

R1 , . . . , Rn0 from the randomness oracle, and feeds C1 = ±(R1 ), . . ., Cn = ±(Rn )

to A0 as an answer to the encryption queries. The EPA1+ property of Π ensures

the existence of extractor L0 for B0 . We will construct extractor K0 for A0 by

using L0 .

The precise description of adversary B0 for the EPA1+ security is as follows.

B0 (pk; R) executes A0 (pk; R). If A0 makes a decryption query, B0 answers it by

making a decryption query. If A0 makes the i-th encryption query Qi , B0 sends

query to the randomness oracle, receives an answer Ri , computes Ci = ±(Ri ),

and sends Ci back to A0 . Finally, B0 outputs the output of A0 .

From the EPA1+ security of Π, there exists an extractor L0 for B0 . We con-

struct extractor K0 for A0 by using L0 . We would like to denote how K0 extracts

118 I. Teranishi and W. Ogata

ˆ ˆ

the plaintext from Cj , where j is an arbitrary integer and Cj is the j-th decryp-

tion query of A0 . Let k be the number of times that A0 has made the encryption

queries before it makes the j-th decryption query.

Our idea behind the construction of K0 is as follows: K0 obtains Decsk (Cj ) by ˆ

feeding Cj to L0 . However, recall that L0 is an extractor for adversary B0 of the

ˆ

EPA1+ security although K0 is an extractor for adversary A0 of the statistical

PA2 security. This means that L0 requires the list List = R1 · · · Rk as an input

although K0 is given the list CList = C1 · · · Ck as an input. Here List is the

list of the answers from the randomness oracle to B0 and CList is the list of

the answers from the encryption oracle to A0 . Therefore, K0 selects ρ1 , . . . , ρk

randomly, sets R1 = β(C1 ; ρ1 ), . . ., Rk = β(Ck ; ρk ), and feeds not List but

List = R1 · · · Rk to L0 .

The precise description of K0 is as follows. K0 (pk, Cj , R, CList, st; ρK0 ) parses

ˆ

CList as CList = C1 · · · Ck , parses ρK0 as ρK0 = ρL0 ρ1 · · · ρn0 , computes

R1 = β(C1 ; ρ1 ), . . ., Rk = β(Ck ; ρk ), sets List = R1 · · · Rk , obtains (Mj , st) ←ˆ

L0 (pk, Cj , R, List, st; ρL0 ), and outputs (Mj , st).

ˆ ˆ

Finally we show that extractor K0 for A0 is successful. We ¬x an arbitrary

plaintext creator P0 . Our idea behind the proof of the successfulness of K0 is as

follows. Since L0 is successful, output Mj of L0 (· · · , Cj , · · · , List , · · · ) is equal to

ˆ ˆ

Decsk (Cj ) with overwhelming probability in EPA1+Dec,L0 (»). From the de¬nitions

ˆ

Π,B0

of EPA1+Dec,L0 (») and B0 , the experimenter of EPA1+Dec,L0 (») feeds to L0 the

Π,B0 Π,B0

list List of answers R1 , . . . , Rk from the randomness oracle, and B0 feeds C1 =

±(R1 ), . . ., Ck = ±(Rk ) to its subroutine A0 . Since X is random-like, (Ci , Ri ) =

(±(Ri ), Ri ) is computationally indistinguishable from (Ci , β(Ci , ρi )), where Ci

is a randomly selected element of X and ρi is a randomly selected bit string.

Since Π is random-like, a randomly selected element Ci of X is computationally

indistinguishable from a ciphertext Ci = Encpk (Mi ; ri ). Here Mi is a plaintext

computed by a plaintext creator P0 from the i-th encryption query of A0 , and

ri is a random tape. In particular, if we set Ri = β(Ci , ρi ) and Ri = β(Ci , ρi ),

Ri is computationally indistinguishable from Ri .

Therefore, output Mj of L0 (· · · , Cj , · · · , List, · · · ) is equal to Decsk (Cj )

ˆ ˆ ˆ

with overwhelming probability, even in the following experiment: A0 is fed

C1 = Encpk (M1 ; r1 ), . . ., Ck = Encpk (Mk ; rk ) as answers to encryption

queries, and L0 is fed List = R1 · · · Rk = β(C1 ; ρ1 ) · · · β(Ck ; ρk ). Since

K0 feeds List = β(C1 ; ρ1 ) · · · β(Ck ; ρk ) to L0 , the above experiment is the

same as EPADec,K0 (»). Thus, output Mj of K0 (· · · , Cj , · · · , Clist, · · · ) is equal

ˆ ˆ

Π,A0

to Decsk (Cj ) with overwhelming probability, where Clist = C1 · · · Ck =

ˆ

Encpk (M1 ; r1 ) · · · Encpk (Mk ; rk ). This means that K0 is successful.

We now formally prove that K0 is successful. We ¬x an arbitrary plaintext

creator P0 and construct a distinguisher D0 for the random-like property of X

and an adversary C0 for the game (depicted in De¬nition 8) of the random-

like property of Π. Let (C — , R— ) be an instance of for distinguishing game of

De¬nition 7. D0 would like to know whether C — = ±(R— ) holds or R— = β(C — ; ρ— )

holds for some random tape ρ— . D0 (C — , R— ) obtains (pk, sk) ← Gen(1» ), selects

Cramer-Shoup Satis¬es a Stronger Plaintext Awareness 119

i0 ∈ {1, . . . , n0 } randomly, selects R and ρL0 randomly, initializes List† and

st to µ, and executes A0 (pk; R). If A0 makes the i-th encryption query Qi for

i < i0 , D0 selects Ci ∈ X and ρi randomly, computes Ri = β(Ci ; ρi ), resets

List† ← List† Ri , and sends Ci back to A0 . If A0 makes the i-th encryption