# Is it insecure using addition instead of multiplication in Elgamal encryption?

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?

• How would you decrypt? – Mark May 3 '17 at 7:20
• 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... – Hilder Vitor Lima Pereira May 3 '17 at 8:29
• 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?). – 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.
• 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. – tylo May 3 '17 at 12:02
• 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$. – Yehuda Lindell May 3 '17 at 14:58