Reading about the Decisional Diffie-Hellman on Wikipedia, I came across this section:

Importantly, the DDH assumption does not hold in the multiplicative group $\mathbb{Z}^*_p$, where $p$ is prime. This is because given $g^a$ and $g^b$, one can efficiently compute the [Legendre symbol] of $g^{ab}$, giving a successful method to distinguish $g^{ab}$ from a random group element

I read through the related questions to this and I still don't understand how this assumption is false if $g$ is a generator of $\mathbb{Z}^*_p$ and not of $\mathbb{G}_q$? Can we even show the probability would be greater than 0.5?

  • 1
    $\begingroup$ In fact, even more is true: $g^{ab}$ can be distinguished from a random element even without $g^a$ and $g^b$ (assuming $a$ and $b$ are chosen uniformly). Think about it. $\endgroup$ – fkraiem Dec 1 '16 at 14:03

Here's the issue; the size of the multiplicative group is $p-1$; if $p>2$, then $p-1$ is even.

What this means is that we can divide the group into two equal sized halves, the "even" elements (which happen to be the values $x$ which have a solution to the equation $y^2 \equiv x \bmod p$, known as quadratic residues), and the "odd" elements (which happen to be the values for which the equation has no such solution, known as quadratic nonresidues). Computing the Legendre symbol is an efficient way of determining which half a particular element falls into.

Here's why this is important: $g^{ab}$ will be a quadratic nonresidue if (and only if) both $g^a$ and $g^b$ are quadratic nonresidues. Hence, given $g^a$, $g^b$ and a group element $h$, an attacker can determine the Legendre symbol on all three values, and see which half $g^{ab}$ would be expected to fall in; if it falls in one half, and $h$ is in the other, the attacker knows that $h \ne g^{ab}$ (and for a random group element $h$, this is expected to happen half the time).

We typically get around this by redefining the group; we limit ourselves to the subgroup of quadratic residues (and so $h$ isn't allowed to be a random group element, they're allowed only to be in the "even" half); hence this trick doesn't work. This does mean that $g$ cannot generate the entire group (as we cannot allow it to generate the "odd" elements), however we can find an element that generates the entire "even" subgroup (in fact, if we select $p$ to be a safe prime, that is, $(p-1)/2$ is also prime, then any element in the even subgroup, other than 1, will generate the entire even subgroup).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.