# Paillier versus Lifted ElGamal for homomorphic addition for e-voting

I'm looking to create an anonymous e-Voting system which will assign a certain number of bits to each candidate during a vote, e.g. 010000 for Alice, 000100 for Bob, and 000001 for Charlie. It works well with ElGamal on a smaller scale but when I try to do it on a larger scale (adding larger numbers), it times out. On the other hand, Paillier seems to be more efficient at adding larger numbers.

I've got a few questions regarding this since I'm not a crypto expert:

• Does ElGamal really have a problem with adding larger numbers, or is this due to an implementation constraint? It would make sense since it uses exponentiation but I'd like to confirm.
• Also, since Paillier allows both addition and multiplication, does it make it more "malleable" and less secure than ElGamal? I couldn't find any metrics on their comparative security analysis but I did find that ElGamal is supposed to be more efficient, hence my original question.

UPDATE: This paper says that: "For example, in order to achieve the 128-bit security level, 4096-bit p and 256-bit q are normally used in ElGamal, while in Paillier, the size of n is normally chosen to be 4096 bits."

Does that mean Paillier is weaker?

## 1 Answer

So in general ElGamal encryption is only homomorphic wrt. multiplication. However with a few tweeks one can transform ElGamal to exponential ElGamal (and I guess that is what you are referring to).

The main difference between ElGamal and exponential ElGamal is that instead of a message: $$m$$ you have to encrypt $$g^{m}$$. On decryption that means that one has to solve the discrete log problem in order to obtain $$m$$. For small numbers this is no problem at all (thus it works perfectly fine in a voting scheme, where the accumulated numbers are not that big in general), but you are right, when $$m$$ becomes bigger, things can become messy and slow.

As far as I know, you do not have this constraint with Paillier.

The security of those algorithms comes from different assumptions. While El-Gamal relies on Diffie-Hellman (respectively Decisional-Diffie-Hellman), Paillier is based on the decisional composite resudiosity assumption.

I have not looked into the respective papers to see which security proofs they offer, but I think when you use a proper implementation of them, with proper parameters, both are totally fine for an e-voting system.

• I've edited the question to add some research. Do you think it makes a difference? Jul 30 at 5:38
• My knowledge about the specific details of those algorithms is quite limited, however if the paper says that these parameters are chosen to obtain 128-bit security, then both achieve 128 bit security with the respective parameters. Thus the complexity of an attack on both would be $2^{128}$ (for the given parameters). Jul 30 at 6:54
• What does it mean that it requires a bigger key for 128 bit security? Would that result in a bigger ciphertext? Jul 30 at 11:43