ElGamal encryption algorithm is as follows:

To encrypt a value $m$, it chooses a random value $r$, and calculates

$c_1=g^r$ $mod$ $q$

$c_2=m*h^r$ $mod$ $q$

where $g$ is the group generator, $x$ is the private key and $h=g^x$ is the public key.

But if $m$ is 0, then $c_2$ will always be 0. How to deal with this?


Well, you can't.

In standard ElGamal the message space is defined as the elements of the group $\mathbb{Z}_q^*=\{1,\ldots,q-1\}$. So $0$ is not in your message space.

You could take exponential ElGamal, i.e., encode messages in the exponent of $g$. So instead of computing $$c_2=mh^r \mod q$$ you compute $$c_2=g^mh^r \mod q.$$ Note however, that firstly your message space must be that small that discrete logs can be efficiently computed (as decrypting requires computing discrete logs). Secondly, this gives you an additively homomorphic scheme and no longer a multiplicatively homomorphic scheme.

Or as @Guut Boy correctly mentions in his comment, you may also use a simpler mapping as the above. For instance you may simply map the message space $\{0,\ldots,q-2\}$ to $\{1,\ldots,q-1\}$, i.e., adding 1 to your message before encryption and subtracting 1 after decryption, such that $0$ maps to $1$ and thus avoids the problem.

Which approach is more suitable for you depends on your application (which, however, is not clear from your question).

  • 1
    $\begingroup$ A simpler option would be to translate the message space $\{0, \ldots, q - 2\}$ to $\{1, \ldots, q-1\}$ by simply adding $1$ before encryption and subtracting $1$ after decryption. $\endgroup$
    – Guut Boy
    Dec 20 '14 at 20:48
  • $\begingroup$ Yes, clearly one could simply use such a simple mapping. It is, however, not clear what the OP's application is and which solution would be most meaningful. $\endgroup$
    – DrLecter
    Dec 20 '14 at 20:50
  • 1
    $\begingroup$ Sure, both ways work. If you just want to be able to encrypt zero, then I think the mapping is simpler, and possibly more efficient as well. $\endgroup$
    – Guut Boy
    Dec 20 '14 at 20:58
  • 1
    $\begingroup$ @Guut Boy Yes, true. Thanks, I have integrated your comment into my answer. $\endgroup$
    – DrLecter
    Dec 20 '14 at 21:07
  • $\begingroup$ Thanks for all of you! But I want to keep the multiplicatively homomorphic property: the product of two ciphertexts is encryption of 0 if one of them is encryption of 0. Can I achieve this? Or is there any other multiplicatively homomorphic encryption scheme that enables to encrypt 0? $\endgroup$
    – Jan Leo
    Dec 20 '14 at 21:48

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.