Cryptography Reference
In-Depth Information
root modulo
p
. Then, as we have seen in Example 7.1, the DDH problem is easy
with respect to this algorithm (or, in simpler words, the DDH problem is easy in
the groups
Z
p
) and hence the Elgamal encryption scheme over these groups is not
IND-CPA secure. However, the CDH problem is thought to be hard in these groups
and hence Elgamal is thought to be OW-CPA secure also in this case.
As we have seen, a desirable security property for a public-key encryption scheme
is IND-CCA, which is stronger than the IND-CPA property we have just proved.
However, despite having probabilistic encryption, Elgamal's behavior vis-a-vis CCA
attacks is no better than that of plain RSA and the reason is that Elgamal is also
malleable and the adversary can change the ciphertext in such a way that the plaintext
is changed in a controlled way:
•
Elgamal is not IND-CCA secure
.
To see this, suppose that the adversary intercepts a ciphertext
(
c
1
,
c
2
)
that is an
encryption of the plaintext
m
∈
G
with the public key
(
G
,
g
,
h
)
. Then the pair
c
2
m
)
is an encryption of
mm
G
for any
m
(
c
1
,
∈
∈
G
. Indeed, there exists
g
r
h
r
m
an
r
∈ Z
t
(where
t
is the order of
G
) such that
(
c
1
,
c
2
)
=
(
,
)
and hence
c
2
m
)
=
(
g
r
h
r
mm
)
(
c
1
,
,
(a particular case of the homomorphic property since
is an encryption of
m
). Thus an adversary can mount a successful CCA
attack by submitting the ciphertext
m
)
(
,
1
c
2
m
)
(
c
1
,
and multiplying the corresponding
plaintext by
m
−
1
. This attack might be easy to detect since the submitted ciphertext
has the same first component as the challenge ciphertext, which will occur with
negligible probability assuming that the ciphertext has been obtained by applying the
encryption algorithm to a plaintext and that the DDH problem is hard. However, the
adversary can also disguise this fact and use the homomorphic property to construct
a valid ciphertext whose first component is random. For this, the attacker picks a
random
s
c
1
g
s
c
2
h
s
m
)
. Now the first component
is uniformly distributed in
G
assuming that
s
is uniformly chosen at random and this
ciphertext is equal to
← Z
t
and submits the ciphertext
(
,
g
r
+
s
h
r
+
s
mm
)
(
,
, which is, again, a valid encryption of the
plaintext
mm
.
In view of the preceding results, we see that Elgamal is perhaps the most efficient
public-key encryption scheme that is CPA secure under reasonable conditions. This is
a good thing but, of course, one needs to know that the DDH problem is hard relative
to
Gen
G
. While a necessary condition for this to happen is that the CDH problem is
hard, we have just seen that this condition is not sufficient, although there are groups
in which both conditions appear to be equivalent. On the other hand, the most studied
and better understood problem related to the CDH problem is the DL problem but,
again, the hardness of the latter is only known to be a necessary condition for the
hardness of the former. Thus in order to implement Elgamal encryption one looks
for groups in which the DL problem appears to be hard and, moreover, do not have
any obvious additional weaknesses.
