# inverse element in Paillier cryptosystem

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?

-

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.

-
So your idea is that we are still considering the problem of whether there exists a x such that ax=1 mod N, where a here is defined as r^n and N here is defined as n^2 in the Paillier system. Because we know a has the multiplicative inverse only when gcd(a,N)=1, it turns out we know that r^n has the multiplicative inverse only when gcd(r^n,n^2)=1. –  user4478 Dec 10 '12 at 2:26
@user4478 Yes, that is correct, but you can simplify this condition further - if gcd(a, b^2) = 1, then gcd(a, b) = 1 (can you see why?) and if gcd(a, b) = 1 then gcd(a^n, b) = 1 for all n. –  Thomas Dec 10 '12 at 3:58