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.