Decisional Diffie-Hellman assumption

From CRYPTUTOR

(Redirected from Decisional Diffie-Hellman Assumption)

The Decisional Diffie-Hellman (DDH) assumption is a computational hardness assumption based on cyclic groups.

1 Definitions
2 The strength of the DDH assumption
3 Randomized self-reduction
4 See also
5 References

Definitions

For the following definitions, we let $G$ be a cyclic group with fixed generator $g$ . We will write the group operation as multiplication.

[edit]

Diffie-Hellman Function

The Diffie-Hellman function is defined as $DH(g x, g y) = g x y$ .

[edit]

Computational Diffie-Hellman (CDH) assumption

The computational Diffie-Hellman (CDH) assumption in a group $G$ is that the Diffie-Hellman function is computationally intractable. That is, for all PPT algorithms $A$ ,

$\Pr_{X,Y} [ A(X,Y) = \mathrm{DH}(X,Y) ]$ is negligible

where the probability is over random choice of $X$ and $Y$ from $G$ .

[edit]

Decisional Diffie-Hellman (DDH) assumption

The decisional Diffie-Hellman (DDH) assumption in a group $G$ is that the Diffie-Hellman function is pseudorandom. That is, the following two distributions are computationally indistinguishable:

Diffie-Hellman (DH) distribution: $\mathcal{D}_1 = \{ (X,Y, \mathrm{DH}(X,Y) ) \}_{X,Y \gets G}$ .
Uniform distribution: $\mathcal{D}_2 = \{ (X,Y,Z) \gets G^3 \}$ .

To be precise, these assumptions are really statements about a family of groups, indexed by a security parameter which is the number of bits needed to represent group elements. The adversary $A$ , as well as the adversary that is implicit in the statement of computational indistinguishability, runs in polynomial time in this security parameter, and distinguishes with negligible probability in this security parameter.

[edit]

The strength of the DDH assumption

The DDH assumption is a stronger assumption than the CDH assumption, which itself is stronger than the discrete logarithm assumption. The DDH assumption is believed to hold in the group of quadratic residues modulo a safe prime, as well as several other families of groups related to elliptic curves.

[edit]

Randomized self-reduction

The DDH problem has a property called a randomized self-reduction, which is a reduction from any fixed problem instance to randomly-distributed instances. We outline the reduction here:

Suppose we are given a triple $(X, Y, Z)$ . Choose random $r,s,t \gets \mathbb{Z}_n$ (where $n$ is the order of the group), and compute the following triple:

(X', Y', Z') = (X t g r, Y g s, Z t Y r X s t g r s)

If $Z = DH(X, Y)$ , then $(X', Y', Z')$ is uniformly distributed from the DH distribution ( $\mathcal{D}_1$ ). If $Z \ne \mathrm{DH}(X,Y)$ , then $(X', Y', Z')$ is uniformly distributed among all triples ( $\mathcal{D}_2$ ).

The consequence of this randomized self-reduction is that solving the DDH problem in the worst case reduces to the problem of solving it for random inputs.

[edit]