4
$\begingroup$

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)$?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @AMarcedone: So, we need a random r for each message... $\endgroup$ – zof Mar 10 '15 at 11:23
  • 1
    $\begingroup$ Yes, either that or having 2 secret keys and 2 corresponding public keys $h_1,h_2$ $\endgroup$ – Florian Bourse Mar 10 '15 at 12:50
  • $\begingroup$ @Florian: How ? $\endgroup$ – zof Mar 10 '15 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$ – Florian Bourse Mar 10 '15 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 '15 at 18:00

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.