How to use ElGamal to encrypt zero?

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).

• 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. Dec 20 '14 at 20:48
• 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. Dec 20 '14 at 20:50
• 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. Dec 20 '14 at 20:58
• @Guut Boy Yes, true. Thanks, I have integrated your comment into my answer. Dec 20 '14 at 21:07
• 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? Dec 20 '14 at 21:48