inverse element in Paillier cryptosystem

Question

As I know, in Paillier cryptosystem, the encryption $c$ of a message $m$ is calculated as $c=g^m r^n \bmod n^2$.

Now, I am wondering if I can derive $g^m \bmod n^2$ given that I know $c$, $r$, and $n$?

It seems that the "$\bmod\ n^2$" operation does not constitute a finite field. Not every element has the corresponding multiplicative inverse in $\mathbb Z^*_{n^2}$. So, it seems not always impossible for to find a proper $(r^n)^{-1}$ to get $g^m=g^m r^n (r^n)^{-1} \bmod n^2$

If so, can we find or limit the use of $r$ so that $(r^n)^{-1}$ can always be found?

Answer 1

Yes. $r^n$ needs to be coprime with $n^2$. The only elements which have don't an inverse modulo $p^2 q^2$ are all multiples of $p$ and all multiples of $q$, so we just require $\gcd{(r^n, p)} = \gcd{(r^n, q)} = 1$.

$\implies \gcd{(r^n, n}) = 1$

Clearly, if $r$ is coprime to $n$, then $r \times r \times \cdots \times r ~ (n ~ \mathrm{times})$ will also be coprime to $n$, so:

$\gcd{(r, n)} = 1$

The probability of a random $r \in \mathbb{Z}_n^*$ not satisfying the above is equal to $\frac{n - 1 - \varphi{(n)}}{n - 1} \to 0$.

Assuming you use sufficiently large $n$, the probability of selecting a bad $r$ (one that cannot be inverted, according to your criterion) is smaller than the probability of your hardware failing and screwing up the calculation while you getting hit by a dozen lightning bolts simultaneously. I think you'll be fine.