# Why is DDH not hard over $\mathbb{Z}^*_p$?

Why is Diffie-Hellman key exchange not hard over $\mathbb{Z}^{*}_p$?

-
Because you can distinguish quadratic residues from quadratic non-residues. –  DrLecter Mar 21 '14 at 8:59
How can we do so? please explain... –  user2771151 Mar 21 '14 at 9:18
The DDH is not hard, but that doesnt mean that Diffie Hellman key exchange isnt secure in $Z_p^*$, because security of Diffie Hellman key exchange relies on the CDHP. –  DrLecter Mar 21 '14 at 9:19
@DrLecter Not hard but it doesn't make effect on DDH security...confused!!! Do you have any reliable source or proof that makes it clear... –  user2771151 Mar 21 '14 at 9:28
@user2771151: My reading is that the title and body of the question do not match! A distinguisher for the Decisional Diffie–Hellman problem over $\mathbb{Z}^*_p$ can be built from DrLecter's remark, but that does not break Diffie-Hellman key exchange over $\mathbb{Z}^*_p$, especially if $(p-1)/2$ is prime and $p$ is wide enough (thousands bits). –  fgrieu Mar 21 '14 at 9:47

If the DDH is hard in a group $G$ with generator $g$, then it is hard to decide given $(g,g^a,g^b,g^c)$ whether $ab\equiv c\pmod{ord(G)}$.

If you take as $G$ the group $Z_p^*$ of order $p-1$ with $p$ being prime, then you will have $(p-1)/2$ elements being quadratic residues ($QR$) and the other half being non-quadratic residues ($QNR$).

Now, we know that $QR\cdot QR = QR$, $QNR\cdot QNR = QR$ and $QR \cdot QNR=QNR$.

So given a tuple $(g,g^a,g^b,g^c)$, we can check for $g^a$, $g^b$ and $g^c$ whether they are $QR$ or $QNR$, i.e., compute their Legendre symbol.

Note that if this is a valid DDH tuple then you can write it as $(g^a,g^b,g^{ab})$ and if you encounter the cases $(QR,QR,QNR)$, $(QNR,QR,QR)$, $(QR,QNR,QR)$ or $(QNR,QNR,QNR)$ then it cannot be the case that $ab\equiv c\pmod{p}$, which gives you a distinguisher for the DDH (this is informal, but should be sufficient to give the idea).

If you choose $p$ to be a safe-prime, i.e., of the form $p=2q+1$ with $q$ also prime, however, and you work in the prime order $q$ subgroup, the DDH is hard (then you work in the subgroup of quadratic residues and you will no longer have the above approach to construct a distinguisher)!

But the DDH is not the hardness assumption underlying Diffie-Hellman key exchange, but it relies on the CDHP, i.e., given $(g,g^a,g^b)$ compute $g^{ab}$, which is hard in $Z_p^*$ for appropriate choice of $p$. This is the problem an eavesdropper is faced when it intercepts $g^a$ and $g^b$ to compute the common key $g^{ab}$. Note that an eavesdropper against Diffie-Hellman key exchange will hopefully never see an DDH tuple $(g^a,g^b,g^{ab})$ as otherwise this would mean that the parties would send the exchanged key $g^{ab}$ in clear over the wire, and this would not be a good idea ;)

-
Thanx DrLecter... –  user2771151 Mar 21 '14 at 10:05