putationally random-like PKE and an EPA1 security, whose intuitive meanings

are “a ciphertext seems random” and “almost equivalent to the PA1-ness.” Be-

fore giving them, we introduce a new notion, computationally random-like set,

whose intuitive meaning is described in Section 1.

De¬nition 7 (Computationally Random-like Set). Let » be a security

parameter and X = X» be a ¬nite set parametrized by ». We say that X is

computationally random-like if there exists a polynomial = (»), a deterministic

polytime function ± : {0, 1} ’ X and a probabilistic polytime function β :

X ’ {0, 1} such that, for uniformly randomly selected R ← {0, 1} , a ←

X , and a random tape ρ, the distributions of (±(R), R) and (a, β(a; ρ)) are

computationally indistinguishable.

We now de¬ne the computationally random-like PKE. Intuitively, we say that a

PKE is computationally random-like if there exists a computationally random-

like set X such that a ciphertext is indistinguishable from a randomly selected

element of X , even if a distinguisher has access to a decryption oracle. The

precise de¬nition is as follows:

De¬nition 8 (Computationally Random-Like PKE). Let Π = (Gen, Enc,

Dec) be a PKE. We say that Π is computationally random-like if there exists a

computationally random-like set X = X» of (honestly or dishonestly generated)

ciphertexts such that for any polytime adversary A,

b

| Pr[b ← {0, 1}, (pk, sk) ← Gen(1» ), b ← AEoXpk ,Decsk (pk) : b = b ] ’ (1/2)|

is negligible.

114 I. Teranishi and W. Ogata

Fig. 3. Experiments for the Equality-PA2 (left) and for the Equality-PA1+ (right)

Here, EoXb is an oracle such that, if an adversary sends a plaintext M , it

pk

outputs C0 ← Encpk (M ) or C1 ← X , depending on whether b = 0 holds or not.

A is not allowed to send to the decryption oracle answers from the EoXb -oracle.

pk

We next introduce a variant of the PA security, equality-PA (EPA) security.

Decsk (C) holds,

Recall that the de¬nition of PA-ness only requires that M

where M is an output of extractor, “ ” is indistinguishability, C is a decryption

query of an adversary. Our EPA-ness is a variant of the PA-ness which requires

Decsk (C) but M = Decsk (C) with overwhelming probability.

not only that M

De¬nition 9 (Equality-PA Security). We take Π = (Gen, Enc, Dec), A, K,

and P as in De¬nition 4 and de¬ne Encpk —¦ P(Q; μ) as in De¬nition 4. For a

security parameter », we de¬ne an experiment EPADec,K Π,A,Enc—¦P (») shown in the left

of Fig. 3. We say that extractor K is successful for A, if it satis¬es the following

property:

∀P : Pr[EPADec,K

Π,A,Enc—¦P (») = 1] is negligible for ».

We let EPADec,K (») denote EPADec,K

Π,A,Enc—¦P (») if adversary A makes no encryption

Π,A

query to a plaintext creator P.

We say that PKE Π is Equality-PA2 (EPA2) secure if, for any A, there exists

a successful extractor K. We say that PKE Π is Equality-PA1 (EPA1) secure if,

for any polytime adversary A which makes no encryption query, there exists a

successful extractor K.

Since equality implies the indistinguishability, the following theorem clearly

holds:

Theorem 10 (EPA2 ’ Statistical PA2). If a PKE is EPA2 secure, then it

is statistically PA2 secure.

1

One can set the length of the bit string R arbitrarily, because A can obtain a bit

string of arbitrary length by making randomness queries many times.

Cramer-Shoup Satis¬es a Stronger Plaintext Awareness 115

We now describe our su¬cient condition. See Section 3.3 for the proof.

Theorem 11 (Comp. Random-Like + EPA1 ’ EPA2 (’ Stat. PA2)).

If a PKE is a computationally random-like and EPA1 secure, then it is EPA2

secure (and therefore is statistically PA2 secure).

3.2 Randomness Oracle

Before showing Theorem 11, we review notions and a result given by Dent [D06].

In [D06], Dent de¬ned an oracle named the randomness oracle which de¬ned

as follows: if an adversary makes a query a symbol query, it selects a random

bit string R and sends R back to the adversary. Dent then gave a variant of

the PA1 security, PA1+ security, where an adversary was allowed to access the

randomness oracle. He formalized his su¬cient condition by using the PA1+

security.

Since Dent had to carefully discuss about the di¬erence from the PA1 security

and the PA1+ security, one may think that we also have to discuss carefully

about the di¬erence between the EPA1 security and the EPA1+ security. Here

the EPA1+ security is a variant of the EPA1 security where an adversary was

allowed to access the randomness oracle. However, such careful discussion is

unnecessary because the EPA1+ security is equivalent to EPA1 security.

In order to formalize the above discussion, we give the formal de¬nition of

EPA1+ security. Let EPA1+Dec,K (») be the experiment depicted at the right of

Π,A

Fig.3. We say that PKE Π is EPA1+ secure if ∀A∃K∀P : Pr[EPA1+Dec,K (») = 1]

Π,A

is negligible for ».

Theorem 12 (EPA1 ” EPA1+ ). A PKE is EPA1 secure if and only if it is

EPA1+ secure.

Proof. Since EPA1+ security clearly implies EPA1 security, we prove that the con-

verse is also true. Let Π be an EPA1 secure PKE and A0 be an adversary for the

EPA1+ security. We let RA0 be the random tape of A0 , n0 be the number of the

randomness queries of A0 , and Ri be the answer to the i-th randomness query.

In order to show that A0 has a successful extractor, we will construct adver-

sary B0 for the EPA1 security satisfying the following property: the behavior of

B0 (pk; RA0 R1 · · · Rn0 ) is the same as that of A0 (pk; RA0 ) which is given Ri

as the answer to the i-th randomness query. Here “B0 (pk; RA0 R1 · · · Rn0 )”

means that B0 is given a public key pk as an input and RA0 R1 · · · Rn0 as the

random tape. Since the hypothesis ensures the existence of a successful extractor

L0 for B0 , we will construct the extractor K0 for A0 by using L0 .

We now describe the algorithm of adversary B0 for the EPA security. For a

public key pk and a random tape RB0 , B0 (pk; RB0 ) parses its random tape RB0 as

RA0 R1 · · · Rn0 and executes A0 (pk; RA0 ). If A0 makes the i-th randomness query,

B0 sends back Ri as an answer. If A0 makes a decryption query, B0 answers it by

passing the queries to the decryption oracle. B0 ¬nally outputs the output of A0 .

116 I. Teranishi and W. Ogata

From the assumption, there is a successful extractor, named L0 , of the EPA1+

security for B0 . We construct an extractor K0 for A0 by using L0 . We denote how

K0 extracts the plaintext from Cj0 , where j0 is an arbitrary integer and Cj0 is

the j0 -th decryption query of A0 . Our basic idea behind the construction of K0

is quite simple: “Since the behavior of B0 is almost the same as that of A0 , L0

cannot distinguish the j0 -th decryption query of B0 from that of A0 . Thus, K0

can extract the plaintext by feeding Cj0 to L0 .”

We subtly modify the above idea, because A0 and B0 have one small but

essential discrepancy. Recall that B0 (pk; B0 ) = B0 (pk; RA0 R1 · · · Rn0 ) can be

executed only if all of RA0 , R1 , . . ., Rn0 are given in advance as the random

tape. In contrast, when A0 makes decryption query Cj0 , A0 only knows RA0 , R1 ,

. . ., Rkj0 but does not know Rkj0 +1 , . . ., Rn0 . Here kj0 is the number of times

that A0 has made the randomness queries before it makes the j0 -th decryption

query. From the de¬nitions, extractor L0 and K0 have to extract plaintexts only

from data which B0 and A0 know respectively. Thus, L0 needs all of RA0 , R1 ,

. . ., Rn0 , although K0 can use only R1 , . . . , Rkj0 .

In order to resolve this discrepancy, K0 selects Rk0 +1 , . . . , Rn0 randomly,

[j ]

sets RB0 = RA0 R1 · · · Rkj0 Rkj · · · Rn0 , simulates EPA1+Dec,L0 (») with

0

0 +1 Π,B0

[j ]

feeding RB0 as the random tape of B0 , obtains an answer of L0 to the j0 -th

0

decryption query of B0 , and outputs the answer.

We now give the precise description of K0 . Since K0 uses the same algorithm

as A0 as a subroutine of B0 , we denote the subroutine as A0 in order to dis-

tinguish the subroutine from A0 itself. The inputs of K0 are a public key pk,

the ciphertext Cj0 , the random tape RA0 of A0 , the list List = R1 · · · Rkj0

of the answers from the randomness oracle, the state stK0 , and the random