# Decisional Diffie-Hellman: compute Legendre symbol of $g^{ab}$ from $g^a$ and $g^b$?

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!

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

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