Cryptography Reference
In-Depth Information
The computational Diffie-Hellman problem (CDH).
Given a cyclic group
G
and a generator
g
∈
G
define, for each pair of elements
u
,
v
∈
G
:
g
(
log
g
u
)(
log
g
v
)
.
DH
g
(
u
,
v
)
=
The problem is then to compute DH
g
(
u
,
v
)
for randomly chosen
u
and
v
.
Exercise 7.1
Give a precise definition of the hardness of the CDH problem by defin-
ing an experiment inwhich an adversary can only succeedwith negligible probability.
It is clear that being able to solve CDH is equivalent to being able to recover the
key in the Diffie-Hellman protocol. It is clear also that the discrete logarithmproblem
is at least as difficult as the CDH problem or, in other words, if the discrete logarithm
problem is easy so is CDH. However, it is not known whether the converse holds,
i.e., whether hardness of the discrete logarithm problem implies that CDH is hard. It
seems possible that there is some way of solving CDH without computing discrete
logarithms but so far no such method has been found and hence it seems plausible
that, whether or not equivalent to the discrete logarithmproblem, the CDH problem is
hard (in appropriate groups). This hypothesis is known as the
computational Diffie-
Hellman assumption
and, as we have mentioned, it entails that a computationally
bounded adversary cannot recover the key
k
shared by the parties in the Diffie-
Hellman protocol.
But this is, of course, still insufficient to guarantee that the DH protocol is secure
in the sense of Definition 7.2. In practical situations, we have to bear in mind the
possibility of attacks that do not recover the key but only partial information about it,
in which case the protocol is also insecure (in Example 7.1 below, this situation arises
even though the computational Diffie-Hellman assumption is believed to hold). In
an extreme case, it might happen that the partial information leaked might be enough
to reduce the possible keys to a tiny fraction of elements of
G
, leading to a possible
recovery by means of a brute-force attack.
If we look at the DH problem from the point of view of Definition 7.2, we are
naturally led to the following problem:
The decisional Diffie-Hellman problem (DDH)
.
DDH is, roughly speaking, to distinguish DH
g
(
from a random element of
G
for randomly chosen
u
and
v
or, a little more explicitly, to distinguish between
the two distributions
u
,
v
)
(
u
,
v
,
DH
g
(
u
,
v
))
and
(
u
,
v
,w)
, when
u
,
v
,w
are randomly
g
x
g
y
g
xy
chosen in
G
or, equivalently, to distinguish between the distributions
(
,
,
)
g
x
g
y
g
z
and
Z
t
, where
t
is the order of
G
.
Thus we see that what is required for the DH protocol to be secure is that the DDH
problem is hard (also known as the
decisional Diffie-Hellman assumption
). If the
CDH problem is easy then certainly so is the DDH problem but the converse is not
believed to hold.
The DDH problem can be more formally defined relative to a group generating
algorithm
Gen
G
that, on input 1
n
, outputs a (specification of a) cyclic group
G
(
,
,
)
when
x
,
y
,
z
are randomly chosen in
