Paillier's additively homomorphic cryptosystem

Pascal Paillier released his asymmetric encryption algorithm in 1999, which had the particularity of being homomorphic for the addition. (And unlike RSA, the homomorphism was secure.)

Homomorphic encryption, if you haven’t heard of it, is the ability to operate on the ciphertext without having to decrypt it. If that still doesn’t ring a bell, check my old blogpost on the subject. In this post I will just explain the intuition behind the scheme, for a less formal overview check Lange’s excellent video.

Paillier’s scheme is only homomorphic for the addition, which is still useful enough that it’s been used in different kind of cryptographic protocols. For example, cryptdb was using it to allow some types of updates on encrypted database rows. More recently, threshold signature schemes have been using Paillier’s scheme as well.

The actual algorithm

As with any asymmetric encryption scheme, you have the good ol’ key gen, encryption, and decryption algorithms:

Key generation. Same as with RSA, you end up with a public modulus $N = p q$ where $p$ and $q$ are two large primes.

Encryption. This is where it gets weird, encryption looks more like a Pedersen commitment (which does not allow decryption). To encrypt, sample a random $r$ and produce the ciphertext as:

(N + 1)^{m} \cdot r^{N} \mod N^{2}

where $m$ is the message to be encrypted. My thought at this point was “WOOT. A message in the exponent? How will we decrypt?“

Decryption. Retrieve the message from the ciphertext $c$ as

\frac{c^{φ (N)} - 1}{N} \cdot φ (N)^{- 1} \mod N^{2}

Wait, what? How is this recovering the message which is currently the discrete logarithm of $(N + 1)^{m}$ ?

How decryption works

The trick is in expanding this exponentiation (using the Binomial expansion).

The relevant variant of the Binomial formula is the following:

$(1 + x)^{n} = (\binom{n}{0}) x^{0} + (\binom{n}{1}) x^{1} + \dots + (\binom{n}{n}) x^{n}$

where $(\binom{a}{b}) = \frac{a!}{b! (a - b)!}$

So in our case, if we only look at $(N + 1)^{m}$ we have:

(N + 1)^{m} & = (\binom{m}{0}) + (\binom{m}{1}) N + (\binom{m}{2}) N^{2} + \dots + (\binom{m}{m}) N^{m} & = (\binom{m}{0}) + (\binom{m}{1}) N \mod N^{2} & = 1 + m \cdot N \mod N^{2}

Tada! Our message is now back in plain sight, extracted from the exponent. Isn’t this magical?

This is of course not exactly what’s happening. If you really want to see the real thing, read the next section, otherwise thanks for reading!

The deets

If you understand that, you should be able to reverse the actual decryption:

c^{φ (N)} & = ((N + 1)^{m} \cdot r^{N})^{φ (N)} & = (N + 1)^{m \cdot φ (N)} \cdot r^{N φ (N)} \mod N^{2}

It turns out that the $r^{N φ (N)} = 1 \mod N^{2}$ because $N φ (N)$ is exactly the order of our group modulo $N^{2}$ . You can visually think about why by looking at my fantastic drawing:

On the other hand, we get something similar to what I’ve talked before:

(N + 1)^{m φ (N)} = (1 + m N)^{φ} (N) = 1 + m φ (N) N \mod N^{2}

Al that is left is to cancel the terms that are not interesting to us, and we get the message back.