Can anyone explain to me why Paillier crypto system does not provide good performance?

I read here (pdf) that RSA and ElGamal provide better performance than Paillier algorithm.

  • 1
    $\begingroup$ Where did you read this? I would be interested to see their results. $\endgroup$ – mikeazo Jul 15 '16 at 17:14
  • 2
    $\begingroup$ Quote from the paper "In this paper private key bit sizes are selected as suggested by NIST recommendation. Private key size of 1024 bit for RSA, 160 bits for ElGamal and Paillier was used for experimental purpose because RSA provides same amount of security on 1024 bit key size as provided by Elgamal and Paillier on 160 bit." After reading that, I would not trust anything in the paper. It is completely wrong. $\endgroup$ – mikeazo Jul 15 '16 at 17:57
  • 3
    $\begingroup$ Pretty much the entirety of section 4 of the paper makes me wonder if the authors even know how to use cryptography. $\endgroup$ – mikeazo Jul 15 '16 at 17:58
  • 1
    $\begingroup$ Paillier has a larger ciphertext space than similar-strength RSS and ElGamal. That will make the calculations more expensive. It is also a little more complex than the other two. So it is less efficient, but I could not say by how much. Very optimized versions of Paillier are still fast for a number of use cases. $\endgroup$ – mikeazo Jul 16 '16 at 2:07
  • 1
    $\begingroup$ @codesinchaos They don't really specify what they mean. Do they mean the exponent or the modulus? Stating a Paillier key in this way seems especially out of the ordinary. $\endgroup$ – mikeazo Jul 16 '16 at 22:54

There is no way to know what the authors of that paper even did. They say they used Python, but mention no libraries. If it is their own implementation of those algorithms in Python, it may tell you next to nothing of the real world performance of optimized implementations those algorithms.

Further, they say they encrypted files of 68-235 KB, but do not explain how they did that when raw RSA/ElGamal/Paillier all encrypt much shorter messages. (Presumably some kind of blocking, but all details, including padding, are skipped in the explanation.)

This is all in addition to the suspicious key size choices @mikeazo mentioned already in the comments. So please do not take that paper as fact.

Now Paillier is actually slower, primarily because the computations are done modulo $n^2$, which is twice as many bits as the modulus in RSA for similar security. It is not actually that bad because there are various shortcuts/optimizations, but you would expect RSA to be faster because the computations are simpler.

ElGamal is somewhat different, being based on a different problem, but probably faster than RSA. It is also possible to use with elliptic curves, where it has significantly smaller keys etc. and good performance.


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.