0
$\begingroup$

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

$\endgroup$
6
  • 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
10
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanx DrLecter... $\endgroup$ – user2771151 Mar 21 '14 at 10:05
  • $\begingroup$ An element in a group $G$ has a quadratic residue if $\gcd(2,\phi(|G|)) = 1$? $\endgroup$ – conchild Mar 20 at 15:08

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.