# Proof of correctness of Exponential ElGamal

I have an assignment for proving the correctness of both ElGamal and exponential ElGamal homomorphic features (multiplicative and additive respectively). I have managed to prove the former but am struggling on proving the latter. I have reached the point where adding two ciphertexts $c_1$ and $c_2$ to obtain $c_3$, where:

$$c_3 = (a^{r_1} + a^{r_2}, m_1+m_2(b^{r_1} + b^{r_2}))$$

Have I gone completely wrong?

First, when writing ElGamal over a multiplicative group $(\mathbb{G},\times)$ as you did, we do not generally assume any additional structure on top of the group structure - hence writing $a^{r_1} + a^{r_2}$ does not make sense in general.
Second, in multiplicative notations, a ciphertext looks as follow: $c_1 = (a^{r_1},b^{r_1}\cdot a^m)$. You can write it $(r_1\cdot a, (r_1\cdot b)+(m \cdot a))$ if you want to use additive notations instead, but none of these notations will lead to the $c_3$ you obtained.
Hint for the solution: use the group operation to "merge" group elements, do not try to add up objects of the form $a^{r_1}$ and $a^{r_2}$, this will not lead you anywhere. Using multiplicative notation, you should make use of the following observation: $a^{m}\cdot a^{m'} = a^{m+m'}$.
• Have you discussed the exponential ElGamal (as you call it) in class before getting the assignment? This is an issue that your teacher should have discussed when presenting the scheme, as it arise when trying to decrypt, not only after homomorphic addition. When you have $a^M \bmod p$, the only way to get $M$ is via a discrete logarithm (e.g. by brute force: try $a, a^2, a^3$...). This implies that the scheme works only when it is used to encrypt small enough messages: $m+m'$ should not be too large for the discrete log to succeed. Note that $1^M = 1 \neq M \bmod p$. – Geoffroy Couteau Mar 26 '18 at 12:35