the i-th encryption query Qi for i > i0 , D0 selects Ri ∈ {0, 1} randomly,

computes Ci = ±(Ri ), resets List† ← List† Ri , and sends Ci back to A0 . If

A0 makes the j-th decryption query Cj , D0 computes Mj ← Decsk (Cj ) and

ˆ ˆ ˆ

(Mj , st) ← L0 (pk, Cj , R, List† , st; ρL0 ). If Mj = Mj holds, D0 outputs 0 and

ˆ ˆ ˆ ˆ

terminates. Otherwise, D0 sends Mj back to A0 . If A0 terminates, D0 outputs 1

ˆ

and terminates.

We next construct an adversary C0 for the game described in De¬nition 8.

Let pk— be an instance of this game. C0 (pk— ) sets pk = pk— , and selects

i0 ∈ {1, . . . , n0 } randomly, selects random tapes R, ρL0 , and μ randomly, ini-

tializes st, stP0 , and List‡ to µ, and executes A0 (pk; R). If A0 makes the i-th

encryption query Qi for i < i0 , C0 selects a random tape ri randomly, computes

(Mi , stP0 ) ← P0 (Qi , stP0 ; μ) and Ci ← Encpk (Mi ; ri ), computes Ri ← β(Ci ; ρi ),

resets List‡ ← List‡ Ri , and sends Ci back to A0 . If A0 makes the i0 -th en-

cryption query Qi0 , C0 computes (Mi0 , stP0 ) ← P0 (Qi0 , stP0 ; μ), makes query

— — —

Mi0 to EoX-oracle, obtains an answer Ci0 , computes Ri0 ← β(Ci0 ; ρi0 ), re-

sets List‡ ← List‡ Ri0 , and sends Ci0 back to A0 . If A0 makes the i-th en-

— —

cryption query Qi for i < i0 , C0 selects Ci ∈ X and ρi randomly, computes

Ri ← β(Ci ; ρi ), resets List‡ ← List‡ Ri , and sends Ci back to A0 . If A0 makes

the j-th decryption query Cj , C0 makes decryption query Cj , obtains an answer

ˆ ˆ

Mj , and computes (Mj , st) ← L0 (pk, Cj , R, List‡ , st; ρL0 ). If Mj = Mj holds, C0

ˆ ˆ ˆ ˆ ˆ

outputs 0 and terminates. Otherwise, C0 sends Mj back to A0 . If A0 terminates,

ˆ

C0 outputs 1 and terminates.

One can easily show that the following the distributions of 1. and 2. are equal,

the distributions of 3. and 4. are equal, and the distributions of 5. and 6. are

equal.

1. An output of EPA1+Dec,L0 (»).

Π,B0

2. An output of D0 , in the case where i0 = 1 and C— = ±(R— ) hold.

3. An output of D0 , in the case where i0 = n0 and R— = β(C— ; ρ— ) hold.

4. An output of C0 , in the case where i0 = 1 hold and Ci0 is a randomly selected

element of X .

5. An output of C0 , in the case where i0 = n0 hold and Ci0 = Encpk (Mi0 ) holds.

6. An output of EPADec,K0 (»).

Π,A0

Since PKE Π is computationally random-like, a hybrid argument shows that

the distribution of 2. and 3. are computationally indistinguishable and the dis-

tribution of 4. and 5. are computationally indistinguishable also. Therefore, the

theorem holds.

120 I. Teranishi and W. Ogata

4 Statistical PA2-ness of Cramer-Shoup Scheme

In this section, we show that the Cramer-Shoup scheme is statistically PA2

secure under a weaker assumption than Dent assumed in [D06]. The description

of the Cramer-Shoup scheme is reviewed in Fig.4.

4.1 Our Assumption Is Weaker Than Dent™s One[D06]

First, we show that our assumption, the random-like property, is weaker than

Dent™s one [D06], simulatability.

Theorem 13 (Simulatable Group ’ Random-Like Group). If a prime

order cyclic group G is simulatable, then it is computationally random-like.

Proof. Suppose that there exists a group G which is not computationally random-

like but is simulatable. From the simulatability of G, there exists a polynomial

= (»), a deterministic polytime function ± : {0, 1} ’ G and a probabilistic

polytime function β : G ’ {0, 1} satisfying the properties (1), (2), and (3) of

De¬nition 6.

We show that ( , ±, β) satis¬es the condition of the computationally random-

like property of G. That is, we show that, for any polytime distinguisher D,

| Pr[D(±(R), R) = 1] ’ Pr[D(a, β(a; ρ)) = 1]| is negligible. Here R ∈ {0, 1} , ρ,

and a ∈ G are randomly selected.

To this end, we take an arbitrary distinguisher D0 . By using D0 , we construct

polytime adversaries B2 and B3 for the experiments of (2) and (3) of De¬nition 6.

B2 (1» ) sends query to Oβ—¦± , obtains R— as an answer, executes D0 (±(R— ), R— ),

b

obtains an outputs b of D0 , and outputs b . In contrast, B3 (1» ) sends query

to O± , obtains a— as an answer, selects ρ randomly, executes D0 (a— , β(a— ; ρ)),

b

obtains an outputs b of D0 , and outputs b .

One can easily show that the following properties hold:

“ The distribution of D0 (±(R— ), R— ) for randomly selected R— ∈ {0, 1} is the

0

same as that of an output of B2 Oβ—¦± .

1

“ The distribution of an output of B2 Oβ—¦± is the same as that of

0

an output of B3 O± , because the property (1) of De¬nition 6 implies

(±(β(±(R— ); ρ)), β(±(R— ); ρ)) = (±(R— ), β(±(R— ); ρ)).

1

“ The distribution of an output of B3 O± is the same as that of D0 (a, β(a)) for

randomly selected a ∈ G.

”Gen(1» )” ”Decsk (C)”

”Encpk (M )”

θ ← H(u, v, e).

g, h ← G, z, z , x, x , y, y ← Zq . r ← Zq

(u, v, e) ← (g r , hr , M br ). If ux+θy v x +θy = π,

(b, c, d) ← (g z hz , g x hx , g y hy ).

θ ← H(u, v, e). output ⊥.

pk ← (g, h, b, c, d).

π ← (cdθ )r .

sk ← (z, z , x, x , y, y ). Otherwise,

Output C = (u, v, e, π). output e/uz v z .

Output (pk, sk).

Fig. 4. The Cramer-Shoup Scheme

Cramer-Shoup Satis¬es a Stronger Plaintext Awareness 121

Since | Pr[D0 (±(R— ), R— ) = 1] ’ Pr[D0 (a— , ±(a— ; ρ— )) = 1]| is non-negligible,

this means that the winning probability of B2 or B3 is non-negligible. This con-

tradicts the property (2) or (3) of De¬nition 6.

4.2 Proof of Main Theorem

We ¬nally show our main theorem, Theorem 3. From our su¬cient condition

(Theorem 11), all we have to prove is that the Cramer-Shoup scheme is compu-

tationally random-like and is EPA1 secure. Recall that our experiment for the

de¬nition of a random-like PKE is quite similar to that for the de¬nition of the

IND-CCA2 security. Therefore, we can prove this part of our su¬cient condition

by slightly modifying the proof of the IND-CCA2 security of [CS98].

Proof (The Cramer-Shoup Scheme is Random-Like). We set X = G 4 . Since G is

computationally random-like, G 4 is clearly computationally random-like. Recall

the proof [CS98] of the IND-CCA2 security of the Cramer-Shoup scheme. In the

proof, the authors of [CS98] showed that a ciphertext is indistinguishable from a

random element of G 4 even if an adversary can access the decryption oracle. This

means that the winning advantage that an adversary enjoys the game descrebed

in De¬nition 8 is negligible.

We next prove the EPA1 security of the Cramer-Shoup scheme. To do so, we

introduce a new notion, regularity. Intuitively, we say that a PKE is regular

if, for any ciphertext C satisfying Decsk (C) = ⊥, there exists (M, r) satisfying

C = Encpk (M ; r) with overwhelming probability. This property clearly holds if

C is an honestly generated ciphertext. The essence of the regularity is that the

property holds even if C is maliciously generated. The precise de¬nition of the

regularity is as follows:

De¬nition 14 (Regularity). Let Π = (Gen, Enc, Dec) be an encryption

scheme. For a public key/secret key pair (pk, sk) of Π, let Dsk be the set of

the bit string C satisfying Decsk (C) = ⊥, and let Epk be the set of the bit string

C satisfying C = Encpk (M ; r) for some M and r.

We say that Π is regular, if for any pk0 and C0 ,

Pr[(pk, sk) ← Gen(1» ), C0 ∈ Dsk \ Epk0 | pk = pk0 ]

is negligible for ».

Note that some arti¬cial PKEs do not satisfy the regularity. See the full paper

for an example. One can easily show the following lemma:

Lemma 15. The Cramer-Shoup scheme is regular.

We now prove EPA1 security of the Cramer-Shoup scheme.