Paillier Cryptosystem

The Paillier cryptosystem is a probabilistic public key encryption algorithm whose security rests on the presumed difficulty of deciding whether a given number is an n-th power residue modulo a composite number, a problem known as the decisional composite residuosity assumption. Key generation multiplies two large prime numbers together to form a public modulus and derives a matching private key from the same primes; encrypting a message combines it with a random value under this modulus to produce a ciphertext, and decrypting reverses that combination using the private key, but the scheme's most distinctive property is that it is additively homomorphic, meaning that anyone holding only the public key and two encrypted messages can compute a valid encryption of the sum of the two original messages without ever decrypting either one, which allows applications such as electronic voting systems that tally encrypted ballots without exposing any individual vote. Pascal Paillier invented the cryptosystem in 1999 and it is named after him.