Paillier cryptosystem

The Paillier cryptosystem, invented by and named after Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing n-th residue classes is believed to be computationally difficult. The decisional composite residuosity assumption is the intractability hypothesis upon which this cryptosystem is based. The scheme is an additive homomorphic cryptosystem; this means that, given only the public key and the encryption of and , one can compute the encryption of . The scheme works as follows: Choose two large prime numbers and randomly and independently of each other such that . This property is assured if both primes are of equal length. Compute and . lcm means Least Common Multiple. Select random integer where Ensure divides the order of by checking the existence of the following modular multiplicative inverse: , where function is defined as . Note that the notation does not denote the modular multiplication of times the modular multiplicative inverse of but rather the quotient of divided by , i.e., the largest integer value to satisfy the relation . The public (encryption) key is . The private (decryption) key is If using p,q of equivalent length, a simpler variant of the above key generation steps would be to set and , where . The simpler variant is recommended for implementational purposes, because in the general form the calculation time of can be very high with sufficiently large primes p,q. Let be a message to be encrypted where Select random where and Compute ciphertext as: Let be the ciphertext to decrypt, where Compute the plaintext message as: As the original paper points out, decryption is "essentially one exponentiation modulo ." A notable feature of the Paillier cryptosystem is its homomorphic properties along with its non-deterministic encryption (see Electronic voting in Applications for usage).