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

Question

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

Answer 1

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 ;)