|Added to ACSC:||July 21, 2006|
|Last updated:||January 30, 2010|
Paillier is a public key cryptosystem which offers an additive homomorphism, making it very useful for privacy preserving applications. This is a simple C library which implements Paillier key generation, encryption, decryption, and also makes it easy to use the homomorphism.
The excellent GNU Multiple Precision Arithmetic Library (GMP) is used for the underlying number theoretic operations, so you will need to have that installed before building libpaillier.
The privss toolkit for private stream searching is built on libpaillier, so you will need to install libpaillier if you want to install privss.
Thanks to Thomas B. Pedersen for a bug report.
Generally, the library is written in the most straightforward manner that you may imagine given that it is written in C and uses GMP. The Paillier cryptosystem is not very complicated, and neither is libpaillier.
Right now, the only documentation available is the series of comments in the header file (paillier.h). That is probably all that is necessary, however, given the simplicity of the library.
Bugs and Limitations
There are couple security considerations to keep in mind if you intend to try to actually do something secure with libpaillier. Which you absolutely shouldn’t do anyway, since there are probably other issues I’m overlooking.
When the paillier_keygen function selects a modulus n = p q, it does not bother ensuring that p and q are strong primes. While this was at one point considered important (e.g., it is required by ANSI X9.31), modern factoring algorithms make any advantage of strong primes doubtful. RSA Laboratories no longer recommends the practice.
More importantly, at no point is any special effort made to securely "shred" sensitive memory. This means that it is important that functions dealing with private keys and plaintexts (e.g., paillier_keygen and paillier_enc) only be run on trusted machines. The resulting ciphertexts and public keys, however, may of course be handled in an untrusted manner.
Public-Key Cryptosystems Based on Composite Degree Residuosity Classes
Pascal Paillier. Eurocrypt 1999.
(The basic algorithms that libpaillier implements.)
Extensions to the Paillier Cryptosystem with Applications to Cryptological Protocols
Mads Jurik. BRICS Dissertation Series, August 2003.
(A collection of a number of improvements by Jurik and Damgård. We don’t do any of this stuff, so implementing some of these things would be a great way to contribute.)