Suppose that, instead of choosing r completely at random in ElGamal public key encryption, a lazy encryptor (Alice) derives it by following r′= 2r. Suppose also that Eve knows that Alice had encrypted the same message m with the two random numbers r and r′= 2r, thus creating two ciphertexts {k, c} and {k′, c′}. Answer the following questions.

(a) Show how Eve can derive the message m using the two ciphertexts and the public key provided by Alice.


Okay, so this really seems like an homework question to me, so I am going to try to help you with a hint instead of serving the answer hot on a plate. If my assumption about it being a homework question is wrong, then I apologise but the following hint will help you out anyway.

Usually the cipher text in El Gamal is of the form $c=(c1,c2)$, where $c1 = g^{r}$ and $c2 = m.h^{r}$. Now, if $r' = 2r$, then we have $c'=(c1',c2')$ where $c2' = m.h^{2r}$.

Considering the above, what happens if we divide c2' by c2, i.e $\frac{c2'}{c2}$. Would we be able to obtain some information from the this division operation that we just did.

Another way to think of this would be the fact that El Gamal is not IND-CCA secure as it is multiplicatively homomorphic in the presence of a decryption oracle. Maybe this answer will help you understand this property better. This property here will help us do the above division through which the attacker can obtain the value of $h^{r}$ and consequently the value of $m$.

Hope this helps!

| improve this answer | |
  • $\begingroup$ If homework please don't write an answer, provide only hint on comments, that is our current policy $\endgroup$ – kelalaka Nov 15 '19 at 9:16

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