# Several questions about Paillier cryptosystem

I have several questions concerning the original Paillier cryptosystem as described in Paillier, Pascal (1999). "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes". EUROCRYPT. Springer. pp. 223-238. DOI: 10.1007/3-540-48910-X_16

Notation:
$$p$$ - unencrypted message, plaintext
$$c$$ - encrypted message, ciphertext
$$r$$ - random factor
$$k_{pub}$$ - public key
$$k_{priv}$$ - private key

I have a Paillier-encrypted ciphertext ($$p$$) that is no straight encryption but the result of an arbitrary number of various true or mixed homomorphic operations or re-randomizations.

1. Assuming I know $$p$$ and the corresponding private key $$k_{priv}$$. Am I able to compute the random factor $$r$$ from this so that a reencryption of $$p$$ with $$r$$ would be identical to $$c$$, i.e. $$E(p, k_{pub}, r) = c$$ ?

2. if positive answer to 1, how do I compute $$r$$?

3. if positive answer to 1, is it possible that there exists another $$r'$$ so that a different plaintext $$p'$$ encrypted with $$r'$$ would also result in $$c$$, i.e. $$Enc(p, k_{pub}, r) = c = E(p', k_{pub}, r')$$, $$p \neq p'$$, $$r \neq r'$$ ?

4. if positive answer to 3, could this $$r'$$ be efficiently computed, i.e. could the owner of $$k_{priv}$$ be trusted if he would provide $$r$$ to a given $$c$$ as (Zero knowledge) proof of correct decryption?

Let us briefly recall the Paillier encryption. Let $k_{pub} = (N = PQ, g)$ be a public key, where $N$ is the RSA modulus. The secret key is $\lambda = \mathrm{lcm}(P-1,Q-1)$ (or $P,Q$). The encryption of $p \in \mathbb{Z}_N$ with randomness $r \in \mathbb{Z}_N^*$ is $C = g^p r^N \bmod{N^2}$.

You can verify $\mathbb{Z}_{N^2}^* \simeq \mathbb{Z}_N \times \mathbb{Z}_N^*$. As Paillier wrote, there is a subgroup $G = \{z \mid z = y^N \bmod{N^2}\}$ of order $\phi = (P-1)(Q-1)$. There is a bijective mapping $\tau$ from $\mathbb{Z}_N^*$ to $G$ which maps $y$ to $z = y^N \bmod{N^2}$. The inversion $\tau^{-1}(z)$ is computed by $y = z^{N^{-1} \bmod{\lambda}} \bmod{N}$. Roughly speaking, this is the RSA decryption with $e = N$.

2. You can find such $r$. Since you know the plaintext $p$, you can compute $d = g^{-p}C = r^N \bmod{N^2}$. By applying $\tau^{-1}$, you can find $r$. (See Section 5.)
3. No. There is only one $r \in \mathbb{Z}_N^*$. (See Lemma 3.)\ Makes sense since there may be even a huge number of ciphertexts representing the same plaintext but they all have to decrypt to just one plaintext. Hence r is unique as long as en- and decryption are executed using the same pair of keys.