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

other.

Filed under: Study |

## Leave a Reply