Decisional Diffie–Hellman assumption

The Decisional Diffie -Hellman problem ( DDH short ) is a variant of Computational Diffie -Hellman problem ( CDH ) in which it comes to the difficulty of deciding whether a figure has a particular shape. For certain groups, it is assumed that this problem is difficult, so it can not be solved by a probabilistic polynomial time algorithm with small error probability. These DDH assumption plays in cryptography and in particular the public-key cryptography, an important role as a starting point for security proofs. The Decisional Diffie -Hellman problem is related to the discrete logarithm ( DLOG ).

Definition

Given a, usually written multiplicatively, finite cyclic group with generator. This means that, for every element of the group is an integer, so that. Example of such a group, the (additive ) group of integers modulo a prime number, and the corresponding multiplicative group.

The Computational Diffie -Hellman problem is the problem to find in such a group to two elements and the element. Such a triplet is the Diffie-Hellman triplet. If is easy in a group DLOG, even CDH is easy. It can be calculated and from it.

In the Decisional Diffie -Hellman problem have been given a triple and has to decide whether it is a Diffie- Hellman triple, ie whether is. If is easy in a group CDH, DDH is also easy. Then one can calculate from and compare with the given.

Examples

In DDH is easy because there also DLOG is easy. Since this is an additive group, DLOG is only the division. If check, if. This is the case where it is. The division is indeed no group operation in, but due to the special structure of the integers still possible ( both the group members and the " exponent " are integers). This is an example of an algorithm that is not possible in the generic group model, in which only group operations are allowed.

If it is at a prime number with a prime, then prime in the subgroup of quadratic residues is fine. It is believed that DDH is hard in this subgroup of quadratic residues.