1
$\begingroup$

We know that if the decisional Diffie-Hellmann problem is hard then the Elgamal encryption is CPA-secure. One show that if the chosen group is $\mathbb{Z}_p^*$ then the decisional Diffie-Hellman problem is not hard. For instance, one realizes that $g^{ab}$ is a square with probability $3/4$ with an argument based on the parity of $a,b$. Therefore, it makes self to ask the following question:

Is there a CPA-attack on Elgamal when used with $\mathbb{Z}_p^*$?

I need some help on the way to go here. Should I try to build a distinguisher using the above fact about the Diffie-Hellman problem? Or does is just come from the algebraic structure of the group?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

HINT

You already have a hint given in the problem statement:

$g^{ab}$ is a square with probability $3/4$ with an argument based on the parity of $a,b$.

You should start by making sure you understand why is this the case. Then, once you do that, think about what it means to break DDH: it means distinguishing things that look like $g^c$ for a random $c$ from things of the form $g^{ab}$ for random $a,b$. Given the hint above, can you find a feature that differs between these two?

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for the extended explanation of the hint. Let me see if i can exploit it $\endgroup$
    – user1868607
    Jan 28, 2019 at 17:57
  • $\begingroup$ Do you think asking Alice and Bob to encrypt either the generator or 1 would suffice? Because then in the second component i get an even exponent or an odd exponent and i can test whether they are quadratic residues efficiently $\endgroup$
    – user1868607
    Jan 28, 2019 at 18:05
  • $\begingroup$ Yes! That would be a good way of doing it. To make sure I got you: you ask them to encrypt either $m_0 = g^0 = 1$ or $m_1 = g^1 = g$, then the encryption you get is $g^{ab}\cdot g^i = g^{ab+i}$ for either $i=0$ or $i=1$. Then you check whether this ciphertext is a quadratic residue... and what do you do next? $\endgroup$
    – Daniel
    Jan 28, 2019 at 18:22
  • $\begingroup$ If it is quadratic residue i ouput 0, otherwise 1 $\endgroup$
    – user1868607
    Jan 28, 2019 at 18:29
  • $\begingroup$ Right. Just make sure to write down precisely what is the exact success probability, which won't be negligible. Good work! $\endgroup$
    – Daniel
    Jan 28, 2019 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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