Cryptography Reference
In-Depth Information
may not be a valid Elgamal ciphertext but we may assume without loss of generality
that
A
outputs a bit also in this case. We have just seen that the second component
c
2
is a random element of
G
and so is
c
1
=
g
y
because
y
was randomly chosen in
Z
t
.
Thus none of them carries any information about
m
and hence the probability that
A
b
|
will guess the correct bit is exactly 1
/
2. Thus 1
/
2
=
Pr
(
b
=
i
=
1
)
=
Pr
(
b
=
b
|
i
=
1
)
=
Pr
(B
succeeds
|
i
=
1
)
. Since we know the probability that
B
succeeds
in both cases, we can compute the probability that
B
succeeds by using Proposition
2.1 and we obtain:
1
2
Pr
1
2
Pr
Pr
(B
succeeds
)
=
(B
succeeds
|
i
=
0
)
+
(B
succeeds
|
i
=
1
)
1
2
(
1
2
+
ε(
1
2
)
=
1
2
+
1
2
ε(
=
k
)
+
k
).
1
Since
ε(
k
)
is non-negligible, so is
2
ε(
k
)
, which is the advantage of
B
in solving
the DDH problem, and this completes the proof of the implication.
For the converse implication, suppose that there exists a PPT algorithm
B
such that
Pr
(
DDH
B,
Gen
G
(
k
)
=
1
)
=
1
/
2
+
ε(
k
)
, where
ε(
k
)
is a non-negligible function (i.e.,
B
solves the DDH problemwith non-negligible advantage). Then we construct a PPT
adversary
A
such that
A
has non-negligible advantage in the CPA indistinguishability
experiment
PubK
ind-cpa
succeeds with probability non-negligibly
better than random guessing) as follows. On input the public key
A,
Elgamal
(
k
)
(so that
A
(
G
,
g
,
h
)
, where
G
has order
t
,
A
generates two messages
m
0
,
m
1
∈
G
and is given the ciphertext
g
r
h
r
m
b
)
(
c
1
,
c
2
)
=
(
,
, where
b
←{
0
,
1
}
and
r
← Z
t
are randomly chosen and
unknown to
A
.
A
runs
B
on input:
c
2
m
−
1
(
G
,
g
,
c
1
,
h
,
)
0
outputs
b
too.
Let us analyze the behavior of
outputs a bit
b
. Then
B
A
and
A
.If
b
=
0, i.e., if
m
0
is the encrypted message,
c
2
m
−
1
h
r
m
0
m
−
1
g
r
g
r
g
x
g
rx
then
(
G
,
g
,
c
1
,
h
,
)
=
(
G
,
g
,
,
h
,
)
=
(
G
,
g
,
,
,
)
, (where
0
0
g
x
). Thus,
(
G
,
g
,
x
)
is the Elgamal private key—unknown to
A
—, so that
h
=
succeeds in the
PubK
ind-cpa
recalling Definition 7.4, we see that
A
A
,
Elgamal
(
k
)
experiment
(i.e.,
A
outputs 0) precisely when
B
succeeds in the DDH experiment, namely, when
h
r
m
1
m
−
0
is uniformly
distributed in
G
because
m
0
and
m
1
are uniformly chosen at random and, again in
this case,
1, then
c
2
m
−
1
B
outputs 0. On the other hand, if
b
=
=
0
A
succeeds precisely when
B
succeeds (except with negligible probability).
Since the advantage of
B
is non-negligible by hypothesis, so is the advantage of
A
,
completing the proof.
Remark 8.6
Observe that, while Theorem 8.4 is a much more interesting result than
Proposition 8.7, there may be group generation algorithms
Gen
G
to which the latter
applies but the former does not. Let us consider, for example, a PPT algorithm that
on input
k
outputs the pair
(
Z
p
,
g
)
, where
p
is a random
k
-bit prime and
g
a primitive
