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'}$.

  • $\begingroup$ applying what you mentioned, I have got a^M mod p, where M is m + m', how does one get this to equal M? Do we know that a = 1 mod p therefore giving us M mod p? and we are finished? $\endgroup$ – Adam Jones Mar 26 '18 at 12:32
  • $\begingroup$ 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$. $\endgroup$ – Geoffroy Couteau Mar 26 '18 at 12:35
  • $\begingroup$ I had been absent all week due to illness so had not had time to find the content i had missed before the deadline, so my knowledge of the matter was rather limited. Thank you for the clarification i will do some quick research into that now! $\endgroup$ – Adam Jones Mar 26 '18 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.