Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
Yes,you got it wrong on this one. Most importantly, ElGamal is defined on a group in general, but you kind of mixed the additive notation with the multiplicative notation.
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'}$.
