# Is ElGamal homomorphic encryption using additive groups works only for Discrete Log ElGamal? What about EC ElGamal?

It is known that in Discrete Log ElGamal encryption, the ciphertext $$E$$ is encrypted as:

$$a\ =\ g^k$$, where $$k$$ - random scalar from $$[0,\ p)$$, $$g$$ - group generator

$$b\ =\ (Y^k*m)\mod\ p$$, where $$Y$$ - public key, $$m$$ - message to be encrypted and $$p$$ - modulo

$$E\ =\ (a,\ b)$$

The Discrete Log ElGamal forms multiplicative group, which is not suitable for homomorphic encryption with additive group.

The solution is then

$$(Y^k*g^M)\mod\ p$$

Recall, the decryption is $$D\ = b/a^x$$, where $$x$$ - is random scalar from $$[0,\ p)$$.

Which eventually can be used in homomorphic tally with additive group, so we can create as many $$E$$ as we want, then perform $$E1*E2*E3*\ ...$$ and will get $$g^c$$, where $$c\ =\ (m1+m2+m3+\ ...)$$.

That is clear!

But what about EC ElGamal homomorphic encryption/tally with additive group? By nature, the EC ElGamal encryption is already in additive group. So how then I could sum up $$E$$ ciphertexts to achieve the same homomorphic behaviour (tally) as with Discrete Log ElGamal?

• Remarks: there's no reason to include$\bmod p$ in $b\ =\ (Y^k*m)\bmod\ p$ but not in $a\ =\ g^k$ or $D\ = b/a^x$. Independently: the range $[0,p)$ for the random scalar is wrong: if $p$ is a safe prime that range should be $[0,p-1)$ or $[1,p)$ if the generator $g$ is for the whole group $\mathbb Z_p^*$, in which case ElGamal encryption leaks one bit about the plaintext (and it's additively homomorphic variant leaks parity of what's encrypted); or $[0,(p-1)/2)$ or $[1,(p-1)/2]$ if we use the subgroup of quadratic residues modulo $p$, as we should for security.
– fgrieu
Commented Jul 7 at 19:23

The Discrete Log ElGamal forms multiplicative group, which is not suitable for homomorphic encryption with additive group.

There is no inherent difference between 'multiplicative' groups versus 'additive' groups - the distinction is solely on how we choose to express them; that is, whether we decide to write the group operation as $$A \times B$$ or as $$A + B$$

Instead, the problem is that ElGamal is homomorphic over the group operation which is defined, and that group operation is not addition (either over the integers or modulo $$p$$).

In the same way, given the two EC ElGamal encryptions $$(rG, rP+A)$$ and $$(sG, sP+B)$$, then the pointwise sum $$(rG+sG, rP+A+sP+B)$$ is a valid encryption of $$A+B$$, however that $$+$$ is elliptic curve addition - if that's what you're looking for, that's great, if you're looking for something else, you haven't found it yet.

One immediately obvious thing to try would be to define El Gamal over the modular addition operation; that is, the encryption of $$x$$ would be $$(k\times g \bmod p, k \times pub + x \bmod p)$$, with $$pub = g \times priv \bmod p$$ being the public key, and $$k, g, p, pub, priv$$ all being integers. This would be nicely homomorphic over integer addition; however it would be easy to recover the private key $$priv$$ given $$g, pub, p$$, this is also insecure.

If you are looking for an encryption scheme that is homomorphic over modular addition, there's Pallier...

• thank you very much for your proposed solution. I currently started to implement that algorithm, so will accept answer as I test my code. I won't use Pailier, since it doesn't fulfill some of my needs, so ElGamal is my choice with all its pitfalls. Thank you one more time, and in two-three days I will accept your answer if it works in code (or at least I can implement it :D)
– Azii
Commented Jul 8 at 14:40
• @Azii: what is my "proposed solution"? If it's defining El Gamal over addition, well, that's a Bad Idea (unless you don't care about security). Commented Jul 8 at 14:48
• actually your "There is no inherent difference between 'multiplicative' groups versus 'additive' groups" message made me think a bit more abstract, which helped me a lot in code implementation, which I successfully did and tested. So as I promised, I accept your answer, thank you very much for your time!
– Azii
Commented Jul 10 at 9:21

Building additively homomorphic encryption on top of ElGamal encryption is possible regardless of the finite group used. However for convenient decryption the sum $$c$$ of the plaintexts can't span too big an interval, because the cost of decryption grows as $$\mathcal O(\sqrt{c_\max-c_\min})$$.

As explained here we are free to use either additive or multiplicative notation for any group. It's only customary to use multiplicative notation for groups where the internal law is integer multiplication modulo $$p$$ (as in the first part of the question), and additive notation for an elliptic curve group.

Assume a cyclic group suitable1 for ElGamal encryption, noted additively, with it's elements in capital letters, of generator $$G$$. Note integers in lower case. Let $$(x,Y)$$ with $$Y=x*G$$ be an ElGamal (private, public) key pair, where $$*$$ is scalar multiplication.

The plaintexts to be additively homomorphically encrypted are integers $$m_i$$. They are turned into group elements $$M_i=m_i*G$$ and encrypted per generic ElGamal encryption, each yielding as ciphertext the pair of group elements $$\bigl(A_i,\,B_i\bigr)=\bigl(k_i*G,\,k_i*Y+m_i*G\bigr)$$.

For homomorphic combination, these ciphertexts are added, thus forming the combined ciphertext $$\bigl(A,\,B\bigr)=\bigl(\sum A_i,\,\sum B_i\bigr)=\bigl((\sum k_i)*G,\,(\sum k_i)*Y+(\sum m_i)*G\bigr)$$.

For homomorphic decryption, this combined ciphertext $$\bigl(A,\,B\bigr)$$ is decrypted per ElGamal to get the group element $$M=B-x*A=(\sum m_i)*G$$. If it's known a small enough integer interval $$[c_\min,c_\max)$$ that contains $$c=\sum m_i$$, then we can get back $$c$$ from $$M=c*G$$. For very small interval, we can simply search for $$c$$, at a cost dominated by at worse about $$c_\max-c_\min$$ group additions. Baby-step/giant-step reduces that to at worse about $$2\sqrt{c_\max-c_\min}$$ group additions. Pollard's kangaroo is slightly more costly computationally, but uses less memory, thus is typically better for moderate intervals.

When $$c_\max-c_\min$$ is too large (e.g. above $$2^{48}$$), we can use Paillier encryption, which is additively homomorphic, and accommodate arbitrarily large $$c$$. However the cipertexts are larger (for 128-bit security: like 768 bytes, versus 64 for EC-ElGamal).

1 It's sufficient that DDH holds for the group. It's necessary that the DLP is hard, and that the group's order has no small prime factor. In particular, the full multiplicative group $$\mathbb Z_p^*$$ for $$p$$ a safe prime (seemingly used in the beginning of the question) is NOT suitable for CCA security.

• thank you too and again very detailed explanation, I will take into consideration both your and @poncho answers and in two-three days, as I implement it in a code, will accept one of yours solutions, but anyways, I'm so thankful for the real help you provide and appreciate it for taking your time!
– Azii
Commented Jul 8 at 14:42