Why is Diffie-Hellman key exchange not hard over $\mathbb{Z}^{*}_p$?
-
4$\begingroup$ Because you can distinguish quadratic residues from quadratic non-residues. $\endgroup$ – DrLecter Mar 21 '14 at 8:59
-
$\begingroup$ How can we do so? please explain... $\endgroup$ – user2771151 Mar 21 '14 at 9:18
-
1$\begingroup$ 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. $\endgroup$ – DrLecter Mar 21 '14 at 9:19
-
$\begingroup$ @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... $\endgroup$ – user2771151 Mar 21 '14 at 9:28
-
3$\begingroup$ @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). $\endgroup$ – 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)!
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 ;)
-
-
$\begingroup$ An element in a group $G$ has a quadratic residue if $\gcd(2,\phi(|G|)) = 1$? $\endgroup$ – conchild Mar 20 at 15:08