Cryptography Reference
In-Depth Information
this completes the proof of the implication. The converse implication is left as an
exercise.
Exercise 8.27
Show that if the Elgamal scheme is OW-CPA secure then the CDH
problem is hard.
Remarks 8.14
We have seen in Sect.
7.3
that the CDH problem is no harder than
the DL problem. Therefore, hardness of the DL problem is a necessary condition for
Elgamal to be OW-CPA secure but it is not known whether the reverse implication
holds. We have also seen that solving the CDH problem is equivalent to being able
to recover the key in the DH protocol so we arrive at the conclusion that the latter
capacity is also equivalent to breaking Elgamal (in the sense of plaintext recovery).
As we have mentioned on several occasions, OW-CPA security is a very weak
security property. However, the fact that Elgamal encryption is probabilistic allows us
to prove that Elgamal enjoys a much stronger security property under an assumption
which is likely stronger than the CDH problem being hard, namely, that the DDH
problem is hard (see Sect.
7.3
for the definition).
Theorem 8.4
The Elgamal encryption scheme is IND-CPA secure if and only if the
DDH problem is hard relative to
Gen
G
.
Proof
First we show, by contradiction, that if the DDH problem is hard then Elga-
mal is IND-CPA secure. Let
A
be a PPT adversary against Elgamal and let
ε(
k
)
's advantage in the indistinguishability experiment
PubK
ind-cpa
be
A
A
,
Elgamal
(
k
)
, i.e.,
PubK
ind-cpa
(
A,
Elgamal
(
)
=
)
=
/
+
ε(
)
ε(
)
Pr
is non-negligible,
we construct a PPT algorithm that succeeds on the DDH experiment of Definition
7.4with non-negligible advantage as follows. Suppose that
Gen
G
was run on input 1
k
,
with output
k
1
1
2
k
. Assuming that
k
(
G
,
g
)
, where
|
G
|=
t
, and random elements were chosen:
i
←{
0
,
1
}
,
g
xy
x
,
y
← Z
t
. Suppose further that
h
∈
G
is defined by setting
h
:=
if
i
=
0
and
h
←
G
if
i
=
1 (so that
h
is chosen uniformly at random in this case). Then
g
x
g
y
B
is given
(
G
,
g
,
,
,
h
)
as input and its task is to guess the bit
i
.
B
proceeds as
follows:
•
B
g
x
runs
A
on input the Elgamal public key
(
G
,
g
,
)
and
A
outputs two messages
m
0
,
m
1
∈
G
.
g
y
•
B
chooses a random bit
b
←{
0
,
1
}
and sets
(
c
1
,
c
2
)
=
(
,
hm
b
)
.
outputs a bit
b
.
•
B
runs
A
on the ciphertext
(
c
1
,
c
2
)
and
A
b
.
Let us analyze the probability that
•
B
outputs the bit
b
⊕
B
succeeds. Assume first that
i
=
0, in which
g
xy
. Then
c
2
g
xy
m
b
and hence
case
h
=
=
hm
b
=
(
c
1
,
c
2
)
is a valid Elgamal
g
x
b
=
ciphertext for the public key
(
G
,
g
,
)
. Then Pr
(B
succeeds
|
i
=
0
)
=
Pr
(
b
⊕
PubK
ind-cpa
b
|
0
|
i
=
0
)
=
Pr
(
b
=
i
=
0
)
=
Pr
(
A,
Elgamal
(
k
)
=
1
)
=
ε(
k
)
+
1
/
2.
Suppose next that
i
=
1 and hence that
h
is a random element of
G
. Then
g
y
(
c
1
,
c
2
)
=
(
,
hm
b
)
and the second component
hm
b
is uniformly distributed in
G
because
hm
b
=
G
and these values are
equally likely to occur since
h
is randomly chosen. Observe that now the pair
h
0
m
0
=
h
1
m
1
for unique elements
h
0
,
h
1
∈
(
c
1
,
c
2
)
