4
$\begingroup$

In the ElGamal encryption scheme, the message $m$ is multiplied with the secret $g^{xy}$ Wikipedia. I don't understand the advantage of it. Why we can't just XOR our message with the shared secret? As far as I know, multiplication is costlier than the XOR operation. Also, both the schemes will be CPA secure but not CCA secure, in that case, we have to add a MAC anyway. Can anyone please explain this to me?

$\endgroup$
  • $\begingroup$ TL;DR: This way we don't only need one group to describe and reason about in theory and with XOR you would need a stronger assumption than DDH because you need indistinguishability for a string rather than a group element now. $\endgroup$ – SEJPM Jun 12 '17 at 12:02
  • $\begingroup$ @SEJPM thank you for the quick answer. One small question, from the DDH assumption we know $g^{xy}$ is random. So, the XOR of $g^{xy}$ and message will be a random string. Does not it solve the problem? $\endgroup$ – Rick Jun 12 '17 at 12:09
  • 2
    $\begingroup$ If you want to XOR you must first hash $g^{xy}$ and then XOR the result. In this case, the hash behaves as a randomness extractor. If you just XOR it is certainly not secure since some of the bits of $g^{xy}$ are not uniform (it is uniform in the group, not as a string). $\endgroup$ – Yehuda Lindell Jun 12 '17 at 12:12
  • $\begingroup$ A simple example of Yehuda's point: Take standard ECC over prime fields. Use the most standard point encoding as uncompressed ASN.1 sequence. Now the first byte of the message is not encrypted because the standard mandates it to be 0. Also if your messages are equal in the lower bytes you could recover the x coordinate and from that recover the unknown half of the message that is masked by the y coordinate. $\endgroup$ – SEJPM Jun 12 '17 at 12:33
  • $\begingroup$ @SEJPM thank you for the explanation. So, to secure the encryption we need to XOR the hash with the message, right? $\endgroup$ – Rick Jun 12 '17 at 12:56
7
$\begingroup$

One small question, from the DDH assumption we know $g^{xy}$ is random.

Actually, that's not true. What the DDH assumption says is that we cannot distinguish $g^{xy}$ from $g^z$; however it does not say that we can't distinguish either from a random string.

Indeed, we can; if the order of $g$ has no small factors, then $g$ must be a quadratic residue (that is, there must exist a value $h$ with $h^2 = g$; this is easily tested); and hence $g^{xy}$ must also be a quadratic residue. However, a random string is not a quadratic residue with probability 0.5, hence that serves as a distinguisher.

And, if $g$ is not a quadratic residue, then neither the DDH assumption nor indistinguishability from random hold, assuming the attacker can see $g^x$ and $g^y$; that's because $g^{xy}$ is a quadratic residue iff at least one of $g^x$, $g^y$ is a quadratic residue (hence the attacker can compute whether $g^{xy}$ is, even though he doesn't know the value).

This is why Yehuda is telling you to hash $g^{xy}$ first; $g^{xy}$ is distinguishable from a random string (although not necessarily due to a bias in any of the individual bits), $\text{hash}(g^{xy})$ is not.

$\endgroup$
  • $\begingroup$ Thank you for the answer. Please clarify one thing for me, for Key-exchange we don't need $g^x$ or $g^y$ polynomially indistinguishable from a random string. Is only the one-wayness is enough? If that is the case then if we want to convert such a Key exchange scheme to PKE scheme, how hashing the key before XOR is going to help me? Will it be CPA secure? $\endgroup$ – Rick Jun 13 '17 at 19:56

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.