# 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

## 1 Answer

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 = NQR$$ and $$QR \cdot QNR = QR$$, where the $$\cdot$$ operator has the effect $$g^a \cdot g^b = g^{ab}$$. These identities hold trivially as a QR would be of the form $$g^{2k}$$ where $$k\in \mathbb{Z}$$, and so $$g^{2k} \cdot g^b = g^{2(kb)}$$ which is a QR.

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,NQR)$$, $$(QR,QNR,NQR)$$ or $$(QNR,QNR,QR)$$ then it cannot be the case that $$ab\equiv c\pmod{p}$$, which gives you a distinguisher for the DDH.

More formally, the DDH problem is only hard if for $$x, y, z \in G$$ we have

$$|\mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^a, g^b, g^c) = 1) - \mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^a, g^b, g^{ab}) = 1)|\leq \text{negl}(l)$$

An adversary $$\mathcal{A}$$ can adopt the following tactic: check if for the provided $$g^a, g^b, g^c$$ the above QR/NQR identities hold. If they do, then output $$1$$. Otherwise, output $$0$$.

Note that $$P(g^x = QR) = 1/2$$ for a random $$x\in G$$. Hence, according to the above identities, the probability of $$g^{ab}$$ being QR is $$3/4$$ (which is also the probability of either $$g^a$$ or $$g^b$$ being QR). The probabilities above then become:

$$\mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^x, g^y, g^{xy}) = 1) = 1$$ $$\mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^x, g^y, g^z) = 1) = \frac{3}{4}\times\frac{1}{2} + \frac{1}{4}\times\frac{1}{2} = \frac{1}{2}$$ as a valid DH tuple will always obey the QR/NQR identities. Meanwhile, if $$z \neq xy$$, then the adversary outputs $$1$$ if by chance the tuple agrees with the identities (so the probability is [prob that either $$g^a$$ or $$g^b$$ is QR AND $$g^c$$ is QR] OR [the same thing with NQR]).

Hence, $$|\mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^a, g^b, g^c) = 1) - \mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^a, g^b, g^{ab}) = 1)| = \frac{1}{2} \nleq \text{negl}(l)$$ so the problem is not hard, formally.

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
• An element in a group $G$ has a quadratic residue if $\gcd(2,\phi(|G|)) = 1$? – conchild Mar 20 at 15:08