group G is computationally random-like, there exists a polynomial = (»), and

122 I. Teranishi and W. Ogata

functions ± : {0, 1} ’ G and β : G ’ {0, 1} satisfying the property described

in De¬nition 7.

Let A0 be an adversary against EPA1 security and n0 be the number of steps

of A0 . We have to construct an extractor for A0 . A basic strategy for construct-

ing an extractor for A0 is as follows. Let pk = (g, h, b, c, d) be a public key. We

construct adversary B0 for the DHK property, which executes A0 , obtains de-

cryption queries C1 = (u1 , v1 , e1 , π1 ), C2 = (u2 , v2 , e2 , π2 ), . . . of A0 , and makes

a query (ui , vi ) for each i. Then the DHK assumption ensures the existence of

extractor L0 for B0 . From the de¬nition, L0 succeeds in outputting ri with over-

whelming probability. Here ri is an element of Zq satisfying (ui , vi ) = (g ri , hri ).

(To simplify, we here omit to consider the case where ri = NonDH.) The plain-

text Mi = Decsk (Ci ) is easily computable from Ci , if we know the random

tape ri of Ci = Encpk (Mi ; ri ) = (ui , vi , ei , πi ) = (g ri , hri , Mi bri , (cdθi )ri ). Here

θi = H(ui , vi , ei ). Therefore, we can construct extractor K0 for A0 by using L0 .

However, we have to subtly modify the above basic strategy, because there is

a small discrepancy between B0 and A0 . Let RA0 and RB0 be the random tapes

of A0 and B0 . From the de¬nition of the DHK assumption, B0 are given g, h and

RB0 only, although A0 are given g, h, b, c, d and RA0 . Thus, in order to execute

A0 , B0 has to construct (b, c, d, RA0 ) in a deterministic way, by using its input

(g, h, RB0 ) only. Therefore, B0 parses RB0 as RB0 = Rb Rc Rd RA0 , and sets

(b, c, d) = (±(Rb ), ±(Rc ), ±(Rd )).

The precise description of B0 is as follows. B0 (g, h; RB0 ) parses RB0 as

RB0 = Rb Rc Rd RA0 , computes (b, c, d) = (±(Rb ), ±(Rc ), ±(Rd )), sets pk =

(g, h, b, c, d), and executes A0 (pk; RA0 ). If A0 makes the i-th decryption query

Ci = (ui , vi , ei , πi ), B0 makes query (ui , vi ) and obtains answer ri . If ri = NonDH

holds, B0 sends ⊥ to A0 . Otherwise, B0 computes θi = H(ui , vi , ei ) and

πi = (cdθi )ri . If πi = πi holds, B0 sends ei /bri to A0 . Otherwise, B0 sends

⊥ to A0 . If A0 terminates, B0 terminates.

From the DHK assumption, there exists an extractor L0 of the DHK prop-

erty for B0 . By using L0 as a subroutine, we construct an extractor K0 of A0

for the EPA1 property. The basic strategy to construct K0 has already been

described. However, we have to modify the basic strategy because of the pre-

viously mentioned discrepancy between B0 and A0 . From the de¬nitions, ex-

tractor L0 and K0 have to extract plaintexts only from data known by B0 and

A0 respectively. Recall that B0 is given (g, h, RB0 ) = (g, h, Rb Rc Rd RA0 ), al-

though A0 is given (g, h, b, c, d, RA0 ) = (g, h, ±(Rb ), ±(Rc ), ±(Rd ), RA0 ). That

is, B0 knows (Rb , Rc , Rd ) although A0 does not know (Rb , Rc , Rd ) itself but

(±(Rb ), ±(Rc ), ±(Rd )) only. Thus, L0 needs (g, h, Rb , Rc , Rd , RA0 ) although K0

can use (g, h, ±(Rb ), ±(Rc ), ±(Rd ), RA0 ) only.

In order to resolve this discrepancy, K0 selects ρb , ρc , and ρd randomly, sets

Rb = β(b, ρb ), Rc = β(c, ρc ), and Rd = β(d, ρd ), and executes L0 by feeding

(g, h, Rb , Rc , Rd , RA0 ). We will show that (Rb , Rc , Rd ) is indistinguishable from

(Rb , Rc , Rd ) by using the random-like property of G. Hence, we will be able to show

that L0 can output the correct discrete logarithm ri even if L0 is not fed (Rb , Rc , Rd )

but (Rb , Rc , Rd ). Therefore, we will be able to show that K0 is successful.

Cramer-Shoup Satis¬es a Stronger Plaintext Awareness 123

We now give the precise description of K0 . We describe how K0 extract a plain-

text from Ci , where i is an arbitrary number and Ci is the i-th encryption query

of A0 . On input public key pk, ciphertext Ci , random tape RA0 of A0 , the state

st of K0 , and the random tape ρK0 of K0 , K0 perform as follows. K0 parses pk

as (g, h, b, c, d), Ci as (ui , vi , ei , πi ), and ρK0 as ρb ρc ρd ρL0 , computes Rb =

β(b; ρb ), Rc = β(c; ρc ), and Rd = β(d; ρd ), sets RB0 = Rb Rc Rd RA0 , executes

L0 (g, h, (ui , vi ), RB0 , st; ρL0 ), and obtains the output (ri , st) of L0 . If ri = NonDH

holds, K0 outputs (⊥, st). Otherwise, K0 computes θi = H(ui , vi , ei ) and πi =

(cdθi )ri . If πi = πi holds, K0 outputs (ei /bri , st). Otherwise, K0 outputs (⊥, st).

In order to show that K0 is successful, we show that subroutine L0 of K0 can

output the correct discrete logarithm with overwhelming probability even in the

experiment EPADec,K0 (»). To this end, we use the assumption that G is random-

Π,A0

like. We construct an adversary C0 for the computationally random-like property

of G. Let (a— , R— ) be an instance of the game of computationally random-like

property. C0 would like to know whether a— = ±(R— ) holds or R— = β(a— ; ρ— )

holds for some ρ— . C0 (a— , R— ) selects j0 ∈ {1, 2, 3} randomly, selects Rj randomly

and sets aj = ±(Rj ) for j < j0 , sets Rj0 = R— and aj0 = a— , selects aj ∈ G

and a random tape ρj randomly, and sets Rj = β(aj ; ρj ) for j > j0 . Then

† †

C0 sets (b† , c† , d† , Rb , Rc , Rd ) = (a1 , a2 , a3 , R1 , R2 , R3 ), randomly selects g ∈ G,

†

x ∈ Zq , and a random tapes RA0 and ρL0 , sets h = g x , pk = (g, h, b† , c† , d† ),

† † †

†

st = µ, and RB0 = RA0 Rb Rc Rd , and executes A0 (pk; RA0 ). If A0 makes the i-

†

th decryption query (ui , vi , ei , πi ), C0 executes L0 (g, h, (ui , vi ), RB0 , st; ρL0 ), and

obtains the output (ri , st) of L0 . If ri = NonDH and vi = ui x hold, C0 outputs

0 and terminates. If ri ∈ Zq and (ui , vi ) = (g ri , hri ) hold, C0 outputs 0 and

terminates. Otherwise, C0 computes θi = H(ui , vi , ei ) and πi = (cdθi )ri . If πi =

πi holds, C0 sends ei /bri back to A0 . Otherwise, C0 sends ⊥ back to A0 . If A0

terminates, C0 outputs 1 and terminates.

If R— = β(a— ; ρ— ) and j0 = 1 holds, the distribution of output of C0 is the same

as that of DHKL0 0 (»). If a— = ±(R— ) and j0 = 3, the distribution of output of

G,B

C0 is the same as that of EPADec,K0 (»). This means that L0 outputs the correct

Π,A0

discrete logarithm with overwhelming probability even in EPADec,K0 (»). Π,A0

We now show that K0 (pk, Ci , RA0 , st; ρK0 ) outputs the correct answer with over-

whelming probability. As before, we write pk as (g, h, b, c, d) and Ci as (ui , vi , ei , πi ).

Let (ri , st) be the output of L0 (g, h, (ui , vi ), RB0 , st; ρL0 ), sk = (z, z , x, x , y, y , pk)

be the unknown secret key corresponding to pk and θi be H(ui , vi , ei ).

We ¬rst consider the case where ri = NonDH. Since L0 outputs the cor-

rect discrete logarithm with overwhelming probability, (ui , vi ) = (g ri , hri ) holds

with overwhelming probability. From the de¬nition of the Cramer-Shoup en-

cryption scheme, Decsk (Ci ) is equal to ei /ui z vi z or ⊥, depending on whether

ui x+θi y vi x +θi y = πi holds or not. From (ui , vi ) = (g ri , hri ), it follows that

ei /ui z vi z = ei /g ri z hri z = ei /bri and ui x+θi y vi x +θi y = g ri x+ri θi y hri x +ri θi y =

(g x hx )r (g y hy )θi ri = (cdθi )ri . Recall that K0 outputs ei /ui z vi z or ⊥, depending

on whether (cdθi )ri = ei holds or not. This means that the output of K0 is equal

to Decsk (C0 ) with overwhelming probability.

124 I. Teranishi and W. Ogata

We next consider the case where ri = NonDH. Since L0 outputs the cor-

rect output with overwhelming probability, there is no s ∈ Zq satisfying

(ui , vi ) = (g s , hs ). This means that there is no (M, s) ∈ G — Zq satisfying

Ci = Encpk (M ; s). Since the Cramer-Shoup scheme is regular, Decsk (Ci ) = ⊥

holds with overwhelming probability. Since the output of K0 is ⊥, the output of

K0 is equal to Decsk (C0 ) with overwhelming probability.

4.3 The Reason We Succeed in Showing the Statistical PA-ness

The main theorem, Theorem 3, shows the statistical PA2-ness of the Cramer-

Shoup scheme based on computational assumptions, such as the computationally

random-like assumption and the DDH assumption. This seems strange at ¬rst

glance. Hence, we here see why the statistical PA2-ness can be derived from

computational assumptions. We proved the statistical PA2-ness as follows:

1. Prove that “EPA1 + computationally random-like ’ statistically PA2”

(Theorem 11).

2. Prove that EPA1-ness of the Cramer-Shoup scheme from the DHK assump-

tion.

3. Prove the computational random-like property of the Cramer-Shoup scheme

from the computational assumptions.

The key point for proving the statistical PA2-ness is our new notion, the

EPA1 security. In fact, we fail to prove the statistical PA2-ness of it, if we

replace the EPA1-ness of Theorem 11 with the statistical PA1-ness. Recall that

X stat Y and Y comp Z only implies X comp Z, where X, Y , and Z are

random variables. Therefore, statistical PA1-ness + computationally random-like

property only implies (at most) computational PA2 security.

In contrast, EPA1 security + computationally random-like property implies

the statistical PA2 security. The reason is as follow. Recall that the EPA1 (Equal-

ity-PA1) security means that “the equality M = Decsk (C) holds with over-

whelming probability,” where M is an output of an extractor K(· · · , C, List, · · · ).

Clearly, the computational indistinguishability changes the probability only neg-

ligibly. That is, if List is computationally indistinguishable from List, the equality

M = Decsk (C) also holds with overwhelming probability, where M is an output

of an extractor K(· · · , C, List , · · · ). (Here List is the list of random elements of X

and List is the list of encryptions. Their computational indistinguishability is en-

sured by the computational random-like property.) Hence, the Equality-PA1-ness

+ the computationally random-like implies the Equality-PA2-ness (and therefore

implies statistical PA2-ness). Therefore, we can say that the EPA1 security al-

lows us to show the statistical PA2-ness.

Another reason we can succeed in proving the statistical PA2-ness is in the

de¬nition of the DHK assumption. Recall that the DHK assumption ensures that

an output of an extractor is not only indistinguishable but equal to the discrete

logarithm with overwhelming probability. Hence, we can prove the Equality-PA1-

ness of the Cramer-Shoup scheme under the DHK assumption and therefore can