2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I've edited the question to add some research. Do you think it makes a difference? $\endgroup$
    – ystark
    Jul 30, 2021 at 5:38
  • $\begingroup$ 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). $\endgroup$
    – Reppiz
    Jul 30, 2021 at 6:54
  • $\begingroup$ What does it mean that it requires a bigger key for 128 bit security? Would that result in a bigger ciphertext? $\endgroup$
    – ystark
    Jul 30, 2021 at 11:43

Your Answer

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

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