Join Log in
Score:2
avatar Crypto

Paillier versus Lifted ElGamal for homomorphic addition for e-voting

ng flag
ystark

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?

135
1 + 0
Score:1
Reppiz avatar Crypto
gb flag
Reppiz

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.

0 + 3
ng flag
ystark
I've edited the question to add some research. Do you think it makes a difference?
0
Reply
Reppiz avatar
gb flag
Reppiz
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).
0
Reply
ng flag
ystark
What does it mean that it requires a bigger key for 128 bit security? Would that result in a bigger ciphertext?
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.