The computational problems we consider in this setting are summarized in Fig. 10.1. In all cases,
we are considering an attacker that knows the group G and the generator g. It is given the
quantities listed in the column labeled “given,” and is trying to compute the quantities, or answer
the question, listed in the column labeled “figure out.”
The most basic problem is the discrete logarithm (DL) problem. Informally stated, the at-
tacker is given as input some group element X, and must compute DLogG,g(X). This problem is
conjectured to be computationally intractable in suitable groups G.
One might imagine “encrypting” a message x ∈ Zm by letting gx be the ciphertext. An
adversary wanting to recover x is then faced with solving the discrete logarithm problem to do so.
However, as a form of encryption, this has the disadvantage of being non-functional, because an
intended recipient, namely the person to whom the sender is trying to communicate x, is faced
with the same task as the adversary in attempting to recover x.
The Diffie-Hellman (DH) problems first appeared in the context of secret key exchange. Suppose
two parties want to agree on a key which should remain unknown to an eavesdropping adversary.
The first party picks x $←
Zm and sends X = gx to the second party; the second party correspond-
ingly picks y $←
Zm and sends Y = gy to the first party. The quantity gxy is called the DH-key
corresponding to X, Y . We note that
Y x = gxy = Xy .
Thus the first party, knowing Y, x, can compute the DH key, as can the second party, knowing X, y.
The adversary sees X, Y , so to recover the DH-key the adversary must solve the Computational
Diffie-Hellman (CDH) problem, namely compute gxy given X = gx and Y = gy. Similarly, we will
see later a simple asymmetric encryption scheme, based on Equation (10.1), where recovery of the
encrypted message corresponds to solving the CDH problem.
The obvious route to solving the CDH problem is to try to compute the discrete logarithm of
either X or Y and then use Equation to obtain the DH key. However, there might be other
routes that do not involve computing discrete logarithms, which is why CDH is singled out as a
computational problem in its own right. This problem appears to be computationally intractable
in a variety of groups.
We have seen before that security of a cryptographic scheme typically demands much more than
merely the computational intractability of recovery of some underlying key. The computational
intractability of the CDH problem turns out to be insufficient to guarantee the security of many
schemes based on DH keys, including the secret key exchange protocol and encryption scheme
mentioned above. The Decisional Diffie-Hellman (DDH) problem provides the adversary with a
task that can be no harder, but possibly easier, than solving the CDH problem, namely to tell
whether or not a given group element Z is the DH key corresponding to given group elements X, Y .
This problem too appears to be computationally intractable in appropriate groups.
We now proceed to define the problems more formally. Having done that we will provide more
specific discussions about their hardness in various different groups and their relations to each
Filed under: Study |