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. Mar 21 '14 at 8:59
• How can we do so? please explain... 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. 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... 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 = 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)!

An algebraic group commonly used in application of the Diffie-Hellman problem are Schnorr Groups. These are subgroups of $$\mathbb{Z}_p^*$$ and have the form $$G_S = \{h^r \text{ mod } p\ |\ h \in \mathbb{Z}_p^*\}$$ where $$p=rq + 1$$ and $$p,q$$ are primes. It then follows that the order of the group is $$q = (p-1)/r$$.

Note that in this case $$p,q$$ are necessarily odd (aside from the trivial case of $$q=2$$), which means that $$r=2s$$ for some $$s\in \mathbb{N}$$ (ie $$r$$ is even). This means that all elements are quadratic residuals in $$\mathbb{Z}_p^*$$ and hence the above distinguisher would not be applicable.

Moreover, a similar attack on DDH can be constructed for cubic, quartic, etc. residuals. Formally, you can construct such a distinguisher for any $$k$$th residual given $$k$$ divides the group order. The group order for $$\mathbb{Z}_p^*$$ where $$p=rq+1$$, as outlined above, is $$p-1 = rq$$. Hence, we need to check for $$r$$th residuals (which don't give any discrimination power as all elements of the subgroup $$G_S$$ are $$r$$th residuals) and for $$q$$ residuals (which aren't useful as that only includes $$1$$ due to $$q$$ being prime).

Schnorr groups are selected such that $$p\gg q$$, resulting in $$r$$ being big and having a lot of prime factors, making any sort of $$k$$th residual attack have negligible chances of success for reasons outlined above. Though $$k$$th residual attacks for large $$k$$s quickly stop giving any noticeable discrimination power.

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... Mar 21 '14 at 10:05
• An element in a group $G$ has a quadratic residue if $\gcd(2,\phi(|G|)) = 1$? Mar 20 '21 at 15:08
• Is DDH hard in Bitcoin's sec256k1 (in other words, is it s Schnorr group)? Jun 26 '21 at 13:52