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

Question

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?

Answer 1

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$).

But what about EC ElGamal homomorphic encryption/tally with additive group?

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...

Answer 2

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 suitable¹ 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).

---

¹ 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.