Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

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.

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.