# DDH Assumption Not Holding

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?

• 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. Dec 1, 2016 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).
• How do we find such a $g$ ? is there any API in Crypto++ that returns such configuration ? Jan 17 at 20:28
• @NeelBasu: are you asking about the last paragraph, that is, how to select $g$ such that it is a quadratic residue? Well, one obvious way is to pick an arbitrary $r \ne 1, p-1$, and set $g = r^2 \bmod p$ (or just use $g=4$, if you don't feel the need to explicitly multiply it). Alternatively, if $p \equiv 7 \pmod 8$, then just use $g = 2$... Jan 17 at 20:33