Cryptography Reference
In-Depth Information
∈ F
p
have order
r
. Suppose one uses classic textbook Elgamal with restricted message space
M
Exercise 20.4.9
(Boneh, Joux and Nguyen) Let
p
and
r
|
(
p
−
1) be prime and let
g
m
2
m
1
<p/r
. Extend the attack
of Example
20.4.8
using the baby-step-giant-step method so that it requires
O
(2
m/
2
+
)
exponentiations in
G
to find
m
with noticeable probability, for
>
0.
={
0
,
1
}
−{
0
}
as in Example
20.4.8
where #
M
=
−
. It is then intuitively
clear that IND security under passive attacks depends on the decisional Diffie-Hellman
problem.
One way to avoid these attacks is to restrict the message space to
g
Theorem 20.4.10
Classic textbook Elgamal with
M
=
g
has IND-CPA security if and
only if the DDH problem is hard.
Proof
(for perfect oracles): First, we show IND-CPA
≤
R
DDH: let
A
be an oracle to
solve DDH. Let (
c
1
,
c
2
) be a ciphertext that is an encryption of either
m
0
or
m
1
.Call
A
(
g,
c
1
,h
A
,
c
2
m
−
0
) and if the answer is 'yes' then the message is
m
0
and if the answer is
'no' then the message is
m
1
.
For the converse (i.e., DDH
≤
R
IND-CPA of Elgamal): let
A
be an oracle that breaks
indistinguishability of Elgamal. Then
A
takes as input a public key (
g,h
), a pair of mes-
sages
m
0
,
m
1
and a ciphertext (
c
1
,
c
2
) and outputs either 0 or 1. (We assume that
A
outputs
either 0 or 1 even if the ciphertext corresponds to neither message.) Given a DDH instance
(
g,g
1
,g
2
,g
3
) we repeatedly do the following: choose two random messages
m
0
and
m
1
in
and call
A
on the input (
g,g
1
,
m
0
,
m
1
,g
2
,
m
i
g
3
). If
A
outputs
i
every time then we return 'yes' as the answer to the DDH. If
A
only out-
puts the correct answer
i
about half of the time then we return 'no'. To be sure the
decryption oracle is not just being lucky one should repeat the experiment
(log(
r
))
times.
g
, choose a random
i
∈{
0
,
1
}
If the hash function is sufficiently good then one does not have to make as strong an
assumption as DDH to show that semi-textbook Elgamal encryption has IND security.
Instead, the IND security intuitively only depends on CDH. Theorem
20.4.11
is a basic
example of a security proof in the random oracle model (see Section
3.7
for background
on this model). We give the proof as it illustrates one of the ways the random oracle model
is used in theoretical cryptography.
Theorem 20.4.11
In the random oracle model, semi-textbook Elgamal encryption has
IND-CPA security if CDH is hard.
Proof
(Sketch) Let
A
be an adversary for the IND-CPA game on semi-textbook Elgamal
encryption. Let
g,g
a
,g
b
be a CDH instance. We will describe a simulator
S
that will solve
the CDH problem using
A
as a subroutine.
First
S
runs the adversary
A
with public key (
g,g
a
).
The simulator must handle the queries made by
A
to the random oracle. To do this it
stores a list of hash values, initially empty. Let
g
i
be the input for the
i
th hash query. If
