2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user4478 Dec 10 '12 at 2:26
  • $\begingroup$ @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. $\endgroup$ – Thomas Dec 10 '12 at 3:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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