Return to Answer

Investigate the Paillier cryptosystem for its partially homomorphic properties.

The encryption primitive is defined as $E(m)=g^m\cdot r^n \mod n^2$ for a random element $r \in \mathbb{Z}$. From this we can see that given two ciphertexts we have: $$E(m_0)\cdot E(m_1) = (g^{m_0}\cdot {r_0}^n) \cdot (g^{m_1}\cdot {r_1}^n) \mod n^2$$ $$E(m_0)\cdot E(m_1) = g^{m_0 + m_1}\cdot {(r_0 \cdot r_1)}^n \mod n^2$$ $$E(m_0)\cdot E(m_1) = E(m_0 + m_1) \mod n^2$$

So we can compute the encryption of the addition of two plaintexts from only the ciphertexts, without revealing them, by simply multiplying the ciphertexts.

Additionally, if we know the value of $m_1$ then we can avoid using the encryption primitive and directly compute as follows: $$E(m_0)\cdot g^{m_1} = (g^{m_0}\cdot {r_0}^n) \cdot g^{m_1} \mod n^2$$ $$E(m_0)\cdot g^{m_1} = g^{m_0 + m_1}\cdot {r_0}^n \mod n^2$$ $$E(m_0)\cdot g^{m_1} = E(m_0 + m_1) \mod n^2$$

Now, by viewing multiplication as repeated addition, we can extend the homomorphic property to multiply by a constant, by implementing repeated ciphertext multiplication using exponentiation: $$E(m_0)^{m_1} = (g^{m_0}\cdot {r_0}^n)^{m_1} \mod n^2$$ $$E(m_0)^{m_1} = g^{m_0 \cdot m_1}\cdot {({r_0}^{m_1})}^n \mod n^2$$ $$E(m_0)^{m_1} = E(m_0 \cdot m_1) \mod n^2$$

EDIT: As tylo has pointed out in the commentary, several cryptosystems possess this partially homomorphic property. Notable examples include Benaloh, and Naccache-Stern which generalizes it, as well as Damgård–Jurik which generalizes the Paillier system demonstrated above.

Several cryptosystems possess this partially homomorphic property. Notable examples include Benaloh, and Naccache-Stern which generalizes it, as well as Damgård–Jurik which generalizes the Paillier cryptosystem.

A worked example of the latter scheme:

The encryption primitive is defined as $E(m)=g^m\cdot r^n \mod n^2$ for a random element $r \in \mathbb{Z}$. From this we can see that given two ciphertexts we have: $$E(m_0)\cdot E(m_1) = (g^{m_0}\cdot {r_0}^n) \cdot (g^{m_1}\cdot {r_1}^n) \mod n^2$$ $$E(m_0)\cdot E(m_1) = g^{m_0 + m_1}\cdot {(r_0 \cdot r_1)}^n \mod n^2$$ $$E(m_0)\cdot E(m_1) = E(m_0 + m_1) \mod n^2$$

So we can compute the encryption of the addition of two plaintexts from only the ciphertexts, without revealing them, by simply multiplying the ciphertexts.

Additionally, if we know the value of $m_1$ then we can avoid using the encryption primitive and directly compute as follows: $$E(m_0)\cdot g^{m_1} = (g^{m_0}\cdot {r_0}^n) \cdot g^{m_1} \mod n^2$$ $$E(m_0)\cdot g^{m_1} = g^{m_0 + m_1}\cdot {r_0}^n \mod n^2$$ $$E(m_0)\cdot g^{m_1} = E(m_0 + m_1) \mod n^2$$

Now, by viewing multiplication as repeated addition, we can extend the homomorphic property to multiply by a constant, by implementing repeated ciphertext multiplication using exponentiation: $$E(m_0)^{m_1} = (g^{m_0}\cdot {r_0}^n)^{m_1} \mod n^2$$ $$E(m_0)^{m_1} = g^{m_0 \cdot m_1}\cdot {({r_0}^{m_1})}^n \mod n^2$$ $$E(m_0)^{m_1} = E(m_0 \cdot m_1) \mod n^2$$

EDIT: Thanks tylo for specific examples

Investigate the Paillier cryptosystem for its partially homomorphic properties.

The encryption primitive is defined as $E(m)=g^m\cdot r^n \mod n^2$ for a random element $r \in \mathbb{Z}$. From this we can see that given two ciphertexts we have: $$E(m_0)\cdot E(m_1) = (g^{m_0}\cdot {r_0}^n) \cdot (g^{m_1}\cdot {r_1}^n) \mod n^2$$ $$E(m_0)\cdot E(m_1) = g^{m_0 + m_1}\cdot {(r_0 \cdot r_1)}^n \mod n^2$$ $$E(m_0)\cdot E(m_1) = E(m_0 + m_1) \mod n^2$$

So we can compute the encryption of the addition of two plaintexts from only the ciphertexts, without revealing them, by simply multiplying the ciphertexts.

Additionally, if we know the value of $m_1$ then we can avoid using the encryption primitive and directly compute as follows: $$E(m_0)\cdot g^{m_1} = (g^{m_0}\cdot {r_0}^n) \cdot g^{m_1} \mod n^2$$ $$E(m_0)\cdot g^{m_1} = g^{m_0 + m_1}\cdot {r_0}^n \mod n^2$$ $$E(m_0)\cdot g^{m_1} = E(m_0 + m_1) \mod n^2$$

Now, by viewing multiplication as repeated addition, we can extend the homomorphic property to multiply by a constant, by implementing repeated ciphertext multiplication using exponentiation: $$E(m_0)^{m_1} = (g^{m_0}\cdot {r_0}^n)^{m_1} \mod n^2$$ $$E(m_0)^{m_1} = g^{m_0 \cdot m_1}\cdot {({r_0}^{m_1})}^n \mod n^2$$ $$E(m_0)^{m_1} = E(m_0 \cdot m_1) \mod n^2$$

Investigate the Paillier cryptosystem for its partially homomorphic properties.

The encryption primitive is defined as $E(m)=g^m\cdot r^n \mod n^2$ for a random element $r \in \mathbb{Z}$. From this we can see that given two ciphertexts we have: $$E(m_0)\cdot E(m_1) = (g^{m_0}\cdot {r_0}^n) \cdot (g^{m_1}\cdot {r_1}^n) \mod n^2$$ $$E(m_0)\cdot E(m_1) = g^{m_0 + m_1}\cdot {(r_0 \cdot r_1)}^n \mod n^2$$ $$E(m_0)\cdot E(m_1) = E(m_0 + m_1) \mod n^2$$

So we can compute the encryption of the addition of two plaintexts from only the ciphertexts, without revealing them, by simply multiplying the ciphertexts.

Additionally, if we know the value of $m_1$ then we can avoid using the encryption primitive and directly compute as follows: $$E(m_0)\cdot g^{m_1} = (g^{m_0}\cdot {r_0}^n) \cdot g^{m_1} \mod n^2$$ $$E(m_0)\cdot g^{m_1} = g^{m_0 + m_1}\cdot {r_0}^n \mod n^2$$ $$E(m_0)\cdot g^{m_1} = E(m_0 + m_1) \mod n^2$$

Now, by viewing multiplication as repeated addition, we can extend the homomorphic property to multiply by a constant, by implementing repeated ciphertext multiplication using exponentiation: $$E(m_0)^{m_1} = (g^{m_0}\cdot {r_0}^n)^{m_1} \mod n^2$$ $$E(m_0)^{m_1} = g^{m_0 \cdot m_1}\cdot {({r_0}^{m_1})}^n \mod n^2$$ $$E(m_0)^{m_1} = E(m_0 \cdot m_1) \mod n^2$$

EDIT: As tylo has pointed out in the commentary, several cryptosystems possess this partially homomorphic property. Notable examples include Benaloh, and Naccache-Stern which generalizes it, as well as Damgård–Jurik which generalizes the Paillier system demonstrated above.

Investigate the Paillier cryptosystem for its partially homomorphic properties.

The encryption primitive is defined as $E(m)=g^m\cdot r^n \mod n^2$ for a random element $r \in \mathbb{Z}$. From this we can see that given two ciphertexts we have $$E(m_0)\cdot E(m_1) = (g^{m_0}\cdot {r_0}^n) \cdot (g^{m_1}\cdot {r_1}^n) \mod n^2$$ $$E(m_0)\cdot E(m_1) = g^{m_0 + m_1}\cdot {(r_0 \cdot r_1)}^n \mod n^2$$ $$E(m_0)\cdot E(m_1) = E(m_0 + m_1) \mod n^2$$

So we can compute the encryption of the addition of two plaintexts from only the ciphertexts, without revealing them, by simply multiplying the ciphertexts.

Investigate the Paillier cryptosystem for its partially homomorphic properties.

The encryption primitive is defined as $E(m)=g^m\cdot r^n \mod n^2$ for a random element $r \in \mathbb{Z}$. From this we can see that given two ciphertexts we have: $$E(m_0)\cdot E(m_1) = (g^{m_0}\cdot {r_0}^n) \cdot (g^{m_1}\cdot {r_1}^n) \mod n^2$$ $$E(m_0)\cdot E(m_1) = g^{m_0 + m_1}\cdot {(r_0 \cdot r_1)}^n \mod n^2$$ $$E(m_0)\cdot E(m_1) = E(m_0 + m_1) \mod n^2$$

So we can compute the encryption of the addition of two plaintexts from only the ciphertexts, without revealing them, by simply multiplying the ciphertexts.

Additionally, if we know the value of $m_1$ then we can avoid using the encryption primitive and directly compute as follows: $$E(m_0)\cdot g^{m_1} = (g^{m_0}\cdot {r_0}^n) \cdot g^{m_1} \mod n^2$$ $$E(m_0)\cdot g^{m_1} = g^{m_0 + m_1}\cdot {r_0}^n \mod n^2$$ $$E(m_0)\cdot g^{m_1} = E(m_0 + m_1) \mod n^2$$

Now, by viewing multiplication as repeated addition, we can extend the homomorphic property to multiply by a constant, by implementing repeated ciphertext multiplication using exponentiation: $$E(m_0)^{m_1} = (g^{m_0}\cdot {r_0}^n)^{m_1} \mod n^2$$ $$E(m_0)^{m_1} = g^{m_0 \cdot m_1}\cdot {({r_0}^{m_1})}^n \mod n^2$$ $$E(m_0)^{m_1} = E(m_0 \cdot m_1) \mod n^2$$