7
$\begingroup$

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?

$\endgroup$
1
  • 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, 2016 at 14:03

1 Answer 1

17
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ How do we find such a $g$ ? is there any API in Crypto++ that returns such configuration ? $\endgroup$
    – Neel Basu
    Jan 17, 2023 at 20:28
  • $\begingroup$ @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$... $\endgroup$
    – poncho
    Jan 17, 2023 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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