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
  • 2
    $\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 = 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 ;)

  • $\begingroup$ Thanx DrLecter... $\endgroup$ – user2771151 Mar 21 '14 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.