Benchmarking Paillier Encryption
Morten Dahl

Hi Morten, thanks for mentioning our libraries phe and javallier. Your results made us revisit our code.

Python PHE

We have not had all algorithmic optimisations implemented. The new version 1.3.0 now has the same performance as the C implementation.


More recent versions of Javallier (from 0.5.0 onwards) will use GMP if it is available on the system. This leads to a significant improvement in performance.


Comparison of runtime of Paillier encryption for different implementations using the GMP library for modular exponentiation

We ran the benchmarks again for different implementations using GMP on a n1-standard-4 Google GCE instance. It is not a big surprise, that all implementations perform very similarly, as the majority of the computation time is spent in the GMP library, trying to compute a modular exponentiation with very big integers.

Same comparison, this time for decryption (hard to see, but Python, Rust and C are essentially the same)

The timings for the decryption are more interesting. The Julia implementation does not use the CRT trick, and therefore showcases the impact of this optimisation. In the Java library, we chose to use the ‘mpz_powm_secfunction of the GMP library in order to hamper side channel attacks. From the GMP docs:

“This function is designed to take the same time and have the same cache access patterns for any two same-size arguments, assuming that function arguments are placed at the same position and that the machine state is identical upon function entry. This function is intended for cryptographic purposes, where resilience to side-channel attacks is desired.”

We chose this trade-off because we use Javallier frequently in virtualised deployments and the threat of side-channel attacks on shared, virtualised systems is not unrealistic.