From https://en.wikipedia.org/wiki/Decisional_Diffie%E2%80%93Hellman_assumption:

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.

The only way I can think of to distinguish $g^c$ from $g^{ab}$ is:

  • If $\left(\frac{g}{p}\right)=-1$, then $\left(\frac{g^{ab}}{p}\right) = 1$ if and only if $a$ or $b$ is even (which is $3/4$ of the times).
    So if $\left(\frac{g^c}{p}\right) =-1$, probably $g^c\neq g^{ab}$. Nothing is certain.

How'd do you compute $\left(\frac{g^{ab}}{p}\right)$ given $g^a$ and $g^b$?

  • 1
    $\begingroup$ You'd "compute $\left(\frac{g^{ab}}{p}\right)$ given $g^a$ and $g^b$" by solving CDH. ​ ​ $\endgroup$
    – user991
    Dec 18, 2015 at 4:27
  • 2
    $\begingroup$ Solving CDH is not "efficient" though. $\endgroup$
    – Myath
    Dec 18, 2015 at 4:29
  • $\begingroup$ Then there is no "efficient" way. ​ ​ $\endgroup$
    – user991
    Dec 18, 2015 at 4:30

1 Answer 1


Because (I assume) $g$ is a generator, it is not a square (prove this), so its Legendre symbol is $-1$. And hence, the Legendre symbols of $g^a$ and $g^b$ leak the parities or $a$ and $b$. Hence they leak the parity of $ab$, which leaks the Legendre symbol of $g^{ab}$.


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.