How to calculate Enc(-m) from Enc(m) in Paillier cryptosystem?

Question

The encryption in Paillier cryptosystem is like this according to Wikipedia:

1. Let $m$ be a message to be encrypted where $m \in \mathbb{Z}_n$
2. Select random $r$ where $r \in \mathbb{Z}_n^*$
3. Compute ciphertext as: $c = g^m \cdot r^n \bmod n^2 $

So just calculating the inverse of ciphertext $c$ (i.e enc($m$)) will not work, because enc($m$)*enc($-m$) is equal to $r^{2n} \bmod n^2$, not $1 \bmod n^2$.

Answer 1

Actually, computing the inverse modulo $n^2$ using (say) the Extended Euclidean method is exactly what you do. If $c = g^m r^n \bmod n^2$ is an encrypted version of $m$, then $c^{-1} = (g^m r^n)^{-1} = g^{-m} (r^{-1})^n$ is a representation of $-m$ (because if $r \in \mathbb{Z}^*_n$, so is $r^{-1}$)

That $enc(m) * enc(-m)$ isn't precisely 1 isn't relevant; however if we use different randomness $r$ and $s$ during the separate encryptions (as we're supposed to), it'll actually be $r^ns^n = (rs)^n$. However, there is lots of encrypted representations of 0; while 1 is such a valid representation, $(rs)^n$ is as well.