Partial homomorphism: RSA and Paillier

Fully homomorphic encryption is hard to achieve. But long before it, we already knew of partially homomorphic schemes, which let only one kind of operation through. And they are already very useful.

Homomorphic, but only partially

A partially homomorphic scheme allows a single type of operation on the plaintexts — either multiplication or addition, but not both, and with no limit on the number of operations of that type. Several classic schemes, known for a long time, have this property "by accident."

RSA is multiplicatively homomorphic

Let us revisit RSA (in its raw version, without random padding). The encryption of a message m is c = m^e mod n. Take two messages m1 and m2:

c1 = m1^e mod n
c2 = m2^e mod n

c1 × c2 = (m1^e)(m2^e) = (m1 × m2)^e  mod n

The product of the two ciphertexts is exactly the ciphertext of the product m1 × m2. We have thus multiplied two hidden numbers without knowing them. RSA is multiplicatively homomorphic.

Beware: this is also a weakness if no padding is added. It is one of the reasons why real RSA is never used "raw."

Paillier is additively homomorphic

The Paillier scheme (1999) has the dual property, and one far more useful in practice: the product of two ciphertexts yields the ciphertext of the sum of the plaintexts.

D( E(m1) × E(m2) ) = m1 + m2

We multiply the ciphertexts, and we obtain (after decryption) the addition of the messages. Paillier is additively homomorphic.

Scheme	Operation on ciphertexts	Effect on plaintexts
Raw RSA	multiplication	multiplication
Paillier	multiplication	addition

The flagship application: electronic voting

Paillier's additive homomorphism is perfect for encrypted voting. Each ballot is an encrypted 0 or 1. To count the votes, the ballot box does not need to decrypt the ballots: it multiplies all the ciphertexts together.

E(1) × E(0) × E(1) × E(1)  =  E(1 + 0 + 1 + 1)  =  E(3)

The result is the ciphertext of the total number of votes. We decrypt only once, at the very end, to reveal the tally — without ever exposing an individual ballot. The secrecy of the vote is preserved.

In summary

Many schemes are partially homomorphic: they let only one operation through. Raw RSA is multiplicatively homomorphic (c1 × c2 encrypts m1 × m2), whereas Paillier is additively homomorphic (the product of the ciphertexts yields the ciphertext of the sum). This last property makes Paillier ideal for electronic voting, where you add up encrypted ballots without ever opening them.