Editing Paillier cryptosystem (section)

=== Homomorphic properties ===
A notable feature of the Paillier cryptosystem is its [[Homomorphic encryption|homomorphic]] properties along with its non-deterministic encryption (see Electronic voting in Applications for usage). As the encryption function is additively homomorphic, the following identities can be described:

* '''Homomorphic addition of plaintexts'''

: The product of two ciphertexts will decrypt to the sum of their corresponding plaintexts,

:: <math>D(E(m_1, r_1)\cdot E(m_2, r_2)\bmod n^2) = m_1 + m_2 \bmod n. \, </math>

: The product of a ciphertext with a plaintext raising <math>g</math> will decrypt to the sum of the corresponding plaintexts,

:: <math>D(E(m_1, r_1)\cdot g^{m_2} \bmod n^2) = m_1 + m_2 \bmod n. \, </math>

* '''Homomorphic multiplication of plaintexts'''

: A ciphertext raised to the power of a plaintext will decrypt to the product of the two plaintexts,

:: <math>D(E(m_1, r_1)^{m_2}\bmod n^2) = m_1 m_2 \bmod n, \, </math>
:: <math>D(E(m_2, r_2)^{m_1}\bmod n^2) = m_1 m_2 \bmod n. \, </math>

: More generally, a ciphertext raised to a constant ''k'' will decrypt to the product of the plaintext and the constant,

:: <math>D(E(m_1, r_1)^k\bmod n^2) = k m_1 \bmod n. \, </math>

However, given the Paillier encryptions of two messages there is no known way to compute an encryption of the product of these messages without knowing the private key.