2
$\begingroup$

I was reading this notes http://www.cs.umd.edu/~jkatz/gradcrypto2/NOTES/lecture4.pdf

It's given that discrete log assumption is not enough for semantic security, I'm assuming there maybe chance of getting quadratic residue even if we choose x and r so that both are not even.

But what about decisional diffie Hellman assumption? Isn't it just same? Can't the adversary similarly select one message which is quadratic residue and do the same attack?

| improve this question | |
$\endgroup$
1
$\begingroup$

The difference is to which groups we think the assumption applies.

The discrete logarithm assumption is thought to apply to groups of the form $\mathbb{Z}_p^*$ with $p$ prime, amongst others. As explained in the linked lecture notes, there exist polynomial time algorithms that determine whether $m_b$ is a quadratic residue. This is sufficient to rule out half of the possible plaintexts, because in groups modulo a prime, exactly half of the elements are quadratic residues. Given this counterexample, the discrete logarithm assumption is consequently not sufficient to achieve semantic security.

The Decisional Diffie-Hellman assumption does not apply to groups $\mathbb{Z}_p^*$ with $p$ prime, but it is thought to apply to other groups -- the ones typically use for ElGamel. The DDH assumption is a stronger assumption that applies to some of the groups where the discrete logarithm assumption holds.

In particular, if the DDH assumption holds, we can prove that there cannot exist a polynomial time algorithm that determines whether an element is a quadratic residue. This necessarily disproves the DDH assumption for groups $\mathbb{Z}_p^*$ with $p$ prime.

So long story short, if the DDH assumption holds, then the attacker cannot perform the attack using quadratic residues in polynomial time, or in fact even distinguish chosen plaintexts in polynomial time. However, the DDH assumption does not hold for all groups where the discrete logarithm assumption holds, and for some of those groups where the DDH assumption does not hold, an attacker can perform the attack in polynomial time.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much for your answer, I've understood that because of DDH assumption we cannot distinguish random and DH, therefore we can't distinguish them with quadratic residue either. But in discrete log assumption, isn't it simple to just make sure g^(xr) is not a quadratic residue? Then we can't distinguish the messages even if one of them is quadratic residue $\endgroup$ – user41965 Nov 14 '17 at 14:04
  • $\begingroup$ @user41965 Modulo a prime, the product of two non-residues is a residue, and the product of a residue and a non-residue is a non-residue. So if we make sure that $g^{xy}$ is a non-residue, we can simply determine whether $g^{xy}m_b$ is a residue, and from that immediately conclude whether $m_b$ is a residue or not. $\endgroup$ – knbk Nov 14 '17 at 17:13
  • $\begingroup$ Thank you very much, I'm assuming product of two non residue is a residue because if p is prime, half of them are quadratic residue $\endgroup$ – user41965 Nov 14 '17 at 22:25
  • $\begingroup$ @user41965 The proof is a little different. If $p$ is prime, there exists a generator $g$. An element $g^a$ is a quadratic residue if and only if there exists a $b$ such that $g^a=(g^b)^2=g^{2b} \mod p$, if and only if $a$ is even. Now if $g^a$ and $g^b$ are both non-residues, then $a$ and $b$ are odd, but $a+b$ is even, so $g^ag^b=g^{a+b}$ is a quadratic residue. $\endgroup$ – knbk Nov 14 '17 at 23:20

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.