In the basic ElGamal encryption scheme, we encrypt a message $m$ as $(g^r, h^r m)$, where $g$ is the group generator and $h$ is the public key of the recipient.

If the sender has another message $m'$ to send to the recipient, can they use the same random $r$ in the construction without decreasing the security of the scheme? More generally, with $n$ different messages $(m_1, m_2, \dotsc, m_n)$, is it safe to encrypt them as $(g^r, h^r m_1, h^r m_2, \dotsc, h^r m_n)$?


1 Answer 1


No, you can't. In this case, an attacker can compute $m_1/m_2$ by multiplying the first ciphertext for the inverse of the second and, for instance, determine if $m_1=m_2$ or not. This should not be possible in a secure scheme.

  • $\begingroup$ @AMarcedone: So, we need a random r for each message... $\endgroup$
    – zof
    Mar 10, 2015 at 11:23
  • 1
    $\begingroup$ Yes, either that or having 2 secret keys and 2 corresponding public keys $h_1,h_2$ $\endgroup$ Mar 10, 2015 at 12:50
  • $\begingroup$ @Florian: How ? $\endgroup$
    – zof
    Mar 10, 2015 at 13:47
  • 2
    $\begingroup$ secret keys are $s_1,s_2$, public keys are $h_i=g^{s_i}$ and ciphertext is $g^r,h_1^rm_1,h_2^rm_2$. $\endgroup$ Mar 10, 2015 at 17:08
  • 1
    $\begingroup$ @zof You can look into randomness reuse for ElGamal in context of multi recipient encryption. Thats what Florian points at. $\endgroup$
    – DrLecter
    Mar 10, 2015 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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