I am wondering why most textbook only explain Elgamal encryption using multiplication operation, i.e. $c = m\cdot g^{ab} \pmod p$ instead of addition modulo $p$, i.e. $c = m + g^{ab} \pmod p$?

Is there any flaws or insecurity for the addition version of ElGamal encryption?

  • $\begingroup$ How would you decrypt? $\endgroup$ – Mark May 3 '17 at 7:20
  • $\begingroup$ First of all, this $\mod p$ operation is not required, since it is possible that it doesn't even make sense depending on the group you are working on... $\endgroup$ – Hilder Vitor Lima Pereira May 3 '17 at 8:29
  • $\begingroup$ Second observation, groups doesn't provide both multiplication (to perform exponentiation) and addition. Then, you would have to work on a ring to do that, and it would change all the security proofs we have (for instance, is it easier to solve the DLP in a ring rather than in a group?). $\endgroup$ – Hilder Vitor Lima Pereira May 3 '17 at 8:38

In the generic sense of an abstract group, this is a problem since addition may not be defined. However, when working modulo a prime $p$, addition is certainly defined. However, it is not secure. In order to see why, note that we must work in a prime subgroup of $p$ in order for ElGamal to be secure. Thus, we typically choose $p=2q+1$ where $q$ is also a prime, and then we work in the subgroup of order $q$ of quadratic residues. When you add, you may get out of the subgroup.

A description of an attack when addition is used A Simple Attack on ElGamal Public Key Encryption by Dan Boneh (the paper deals with something else, but also considers addition as motivation).

| improve this answer | |
  • $\begingroup$ In the paper of Dan Boneh, he is using an assumption of the subgroup being very sparse (in the example with half length), which doesn't apply if $p=2q+1$ for prime $q$. Regarding the attack itself: It's quite easy if the public key $y$ is a quadratic residue, an encryption of $0$ would be $y^r+0$, which is a quadratic residue as well, which can be used to break IND-CPA. However, if $y$ is a quadratic non-residue, I can't see right now how to choose the messages - adding any value other than $0$ could change the residuosity or not. $\endgroup$ – tylo May 3 '17 at 12:02
  • 1
    $\begingroup$ I assume that by $y$ you mean the public key. However, for ElGamal security it must be a quadratic residue. Thus, you can make one message 0 and the other random. Then, the probability that the random message will end up giving a quadratic residue is $1/2$. Thus, you can distinguish with probability $1/2$. $\endgroup$ – Yehuda Lindell May 3 '17 at 14:58

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.