the Cramer-Shoup scheme is the only known example of the standard model

PA secure scheme. However, the formal de¬nition of the underlying assumption,

simulatability, is elaborate despite the simplicity of the intuition behind it. In

fact, the formal de¬nition allows a distinguisher to execute an “adaptively chosen

message attack”, and therefore prevents us from describing it simply.

Moreover, although Dent showed the computational PA2-ness of the Cramer-

Shoup scheme, a tricky aspect of the computational PA2-ness was later

shown:

Proposition 2 (Tricky Aspect of the Computationally PA2-ness[TO06]).

There exists a computationally PA2 secure PKE and an adversary such that no

extractor can succeed in extracting the correct plaintext.

It is also shown in [TO06] that there are no such PKE and an adversary in the

case of the statistical PA-ness. Thus, we can say that the statistical PA2-ness is

more similar to our intuition.

1.2 Our Results

Statistical PA2-ness of Cramer-Shoup Scheme: In this paper, we show that the

Cramer-Shoup scheme satis¬es a stronger PA2 security, statistical PA-ness, un-

der assumption weaker and simpler than that of [D06]. That is, we introduce a

weaker and simpler assumption, the computationally random-like property whose

intuitive meaning is a “known message attack version of simulatability,” and

show the following theorem:

Theorem 3 (Cramer-Shoup is Statisitically PA2 Secure under Weaker

Assumption). The Cramer-Shoup scheme is statistically PA2 secure if the un-

derlying group satis¬es the computationally random-like property, the DDH as-

sumption and the DHK assumption, and also if the hash function is collision

resistant.

Cramer-Shoup Satis¬es a Stronger Plaintext Awareness 111

We stress that we show the statistical PA2-ness of the Cramer-Shoup scheme

under only computational assumptions. See Subsection 4.3, for the reason we

can show the statistical PA-ness from the computational assumptions.

Su¬cient Condition for the PA2-ness: In order to prove the PA2-ness of the

Cramer-Shoup scheme, we give a su¬cient condition for the statistical PA2-ness.

Although Dent [D06] already gave another su¬cient condition for the compu-

tational PA2-ness, our condition is not for the computational PA2-ness but for

the statistical PA2-ness.

Moreover, our su¬cient condition is formalized in a more practical way than

that descrebed by Dent [D06]. That is, we formalize a part of our su¬cient

condition based on a slightly modi¬ed version of the IND-CCA2 game. Therefore,

we can prove this part of our su¬cient condition by slightly modifying the proof

of the IND-CCA2 security of [CS98]. This means that we can prove the PA2-ness

more easily.

2 Preliminary

In this section, we review the de¬nition of notions described in Section 1.1. See

Section 1.1 for the intuitions behind the de¬nitions.

De¬nition 4 (Standard Model PA-ness[BP04]). Let Π = (Gen, Enc, Dec)

be a PKE. Let A, K, and P be polytime machines, which are respectively called

adversary, extractor, and plaintext creator.

For plaintext creator P, its state stP , and its random tape μ, we let

Encpk —¦ P(Q; μ) denote the algorithm which executes the following procedures:

(M, stP ) ← P(Q, stP ; μ), C ← Encpk (M ), and output C. Note that the state stP

was initialized to the null string µ.

For security parameter », we de¬ne two experiments PADec Π,A,Enc—¦P (») and

K

PAΠ,A,Enc—¦P (»), shown in Fig. 1, where RA , ρ, and μ are the random tapes of

A, K, and P, List is the list of encryption queries of A, and stK is the state of K.

We say that extractor K is perfectly, statistically, or computationally successful

for A if, for any P, PADec K

Π,A,Enc—¦P (») and PAΠ,A,Enc—¦P (») are perfectly, statistically,

or computationally indistinguishable respectively.

We say that a PKE Π is perfectly, statistically, or computationally PA2 secure

if for any adversary A, there exists a perfectly, statistically, or computationally

successful extractor K for A. We also say that a PKE Π is perfectly, statistically,

or computationally PA1 secure if, for any adversary A which makes no encryp-

tion query, there exists a perfectly, statistically, or computationally successful

extractor K for A.

De¬nition 5 (DHK Assumption [D91,BP04]). Let » be a security param-

eter. Let G = G» be a family of cyclic groups with the prime order q = q» . Let A

and K be polytime machines, named adversary and extractor respectively. We

de¬ne an experiment DHKK (») shown in Fig.2. Here, NonDH is a symbol which

G,A

112 I. Teranishi and W. Ogata

Fig. 1. Experiments for the Standard Model PA Security [BP04]

”DHKK (»)”

G,A

Take random tapes RA and ρ randomly.

g ← G, x ← Zq , h ← g x . Initialize stK to µ.

Run A(g, h; RA ).

If A makes a query Q = (u, v) ∈ G 2

(r, stK ) ← K(g, h, Q, RA , stK ; ρ).

If r ∈ Zq and (u, v) = (g r , hr ), send r to A as the reply.

If r = NonDH and v = ux , send r to A as the reply.

Otherwise, return 0 and terminate the experiment.

Return 1.

Fig. 2. Experiment for the DHK assumption

means that “I think that (g, h, u, v) is not a DH-tuple.” We say that the DHK

assumption on G holds, if G satis¬es the following property:

∀A∃K : Pr[DHKK (») = 1] is negligible for ».

G,A

De¬nition 6 (Simulatable Group [D06]). Let » be a security parameter.

Let G = G» be a family of cyclic groups with the prime order q = q» . We say that

G is simulatable if there exist a polynomial = (»), a deterministic polytime

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

satisfying the following properties:

(1) ±(β(a; ρ)) = a holds for any a ∈ G and ρ.

(2) Let Oβ—¦± be the oracle such that, on inputting a symbol query, selects R ∈

b

{0, 1} and a random tape ρ of β randomly and outputs R or β(±(R); ρ),

depending on whether b = 0 or b = 1. Then, for any polytime adversary A,

the following probability is negligible:

1

b

| Pr[b ← {0, 1}, b ← AOβ—¦± (1» ) : b = b ] ’ |

2

Cramer-Shoup Satis¬es a Stronger Plaintext Awareness 113

(3) Let O± be the oracle such that, on inputting a symbol query, selects R ∈

b

{0, 1} and a ∈ G randomly, outputs ±(R) or a, depending on whether b = 0

or b = 1. Then, for any polytime adversary A, the following probability is

negligible:

1

b

| Pr[b ← {0, 1}, b ← AO± (1» ) : b = b ] ’ |.

2

3 Su¬cient Condition for Statistical PA2-ness

In [D06], Dent provided a very elegant idea for showing the PA2-ness, i.e. “if a

ciphertext seems random, the encryption oracle is meaningless and therefore the

PA2-ness is almost equivalent to the PA1-ness.” Then he provided a su¬cient

condition for the computational PA2-ness by formalizing this idea.

In this section, we explain a new su¬cient condition for the PA2-ness. Al-

though our su¬cient condition is also based on the Dent™s above-mentioned

idea. ours allows us to show not the computational PA2-ness but the statisti-

cal PA2-ness. Moreover, our condition is formalized in a more practical way, as

described in Section 1.2.

3.1 Our Su¬cient Condition