Paillier's Cryptosystem - Homomorphism

I'm lacking quite some mathematical knowledge here, but could anyone please explain to me why the Paillier cryptosystem is still (additive/multiplicative) homomorphic despite introducing a random value?

$$[\![w_1w_2]\!]_g$$ = $$[\![w_1]\!]_g + [\![w_2]\!]_g\ \bmod\ n$$

Does it have to do with the value being sampled from $$\mathbb{Z}^*_n$$? Is the only requirement for the above statement to hold that $$w_1, w_2 \in \mathbb{Z}^*_{n^2}$$?

• Welcome to crypto.SE! Note that in the question's equation, the product is modulo $n^2$, and the sum is modulo $n$. Another way to define the homomorphism in Paillier's cryptosystem is $\forall (m_1,m_2,r_1,r_2),\quad D(E(m_1,r_1)\cdot E(m_2,r_2) \bmod n^2)\;=\;m_1+m_2\bmod n$. where $m_i$ are the messages, and $r_i$ the randomness used in encryption. This is not an answer.
– fgrieu
Dec 16 '19 at 13:40
• Thanks, in the paper only the sum contains a modulo though? Dec 16 '19 at 14:15
• [updated] In this paper, ciphertexts are in $\Bbb Z_{n^2}^*$ (the subset of ,$\Bbb Z_{n^2}$ with elements are coprime with $n$), thus multiplication of ciphertexts implicitly reduce modulo $n^2$. Definitely, one can reduce modulo $n^2$ after multiplication of ciphertexts. That's a good idea since it reduces size, and a practical implementation could/should enforce ciphertext in $[0,n^2)$. Plus, in some protocols, the reduction could help prevent traceability. This is not an answer either.
– fgrieu
Dec 16 '19 at 22:11

The difficult part about understanding the Paillier cryptosystem is to understand what the $$L$$ function in the cryption actually does and why it works. The good news is: To understand the homomorphism, that detail can be put on hold.

The best way to understand homomorphism is to have a close look at the encryption function. Here it is: $$E(m) = r^n g^m \mod n^2$$

If we take this apart, we can see:

• The modulus is $$n^2$$. That means we operate on a multiplicative group with order $$n \cdot \lambda$$ (with $$\lambda=lcm(p-1,q-1)$$).
• This means, there exist subgroups of order $$p,q,n,pa, qa,$$ and $$na$$, where $$a$$ is any proper divisor of $$\lambda$$.
• The random number $$r$$ has an order equal to one of those subgroup orders. It could be divisible by $$p,q$$ (actually, it's overwhelmingly likely to be the order $$n\lambda$$). However, if we take that to the $$n$$-th potency, then the order of $$r^n$$ is not divisible by either $$p$$ or $$q$$, it can only be a divisor of $$\lambda$$. That is a property that can be used.

Now for the decryption, it is enough that somehow the decryption function can:

• Remove any masking factor which is such an $$r^n$$, without knowing which $$r$$ it is.
• Get $$m$$ back from the remaining number $$g^m$$, which is basically a discrete logarithm in this special kind of group.

Now for the homorphism, just encrypt two messages, build their product and do some very basic transoformations:

$$E(m_1) = c_1 = g^{m_1}{r_1}^n$$ $$E(m_2) = c_2 = g^{m_2}{r_2}^n$$ $$c_1 c_2 = g^{m_1}{r_1}^n g^{m_2}{r_2}^n = g^{m_1+m_2} (r_1r_2)^n$$

Clearly, this is just the same as using the encryption method with the message $$m_1+m_2$$ and the random number $$(r_1r_2)$$. And for that the decryption works just like for a single ciphertext.