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

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