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}$?
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.