3
$\begingroup$

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$?

Thank you!

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

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}$.

$\endgroup$

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.