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

$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?


1 Answer 1


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$.


  1. Yes.
  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.
  4. No.
  • $\begingroup$ Dear Community♦. I cannot understand why you add the comment, because Lieven asks the question on the same encryption key. $\endgroup$
    – xagawa
    Jul 27, 2012 at 15:19
  • $\begingroup$ For future reference, Community isn't a real user but a bot that bumps up questions that didn't get an accepted answer every now and then so they don't stay dead (think convection). $\endgroup$
    – Thomas
    Aug 25, 2012 at 14:12
  • 1
    $\begingroup$ @Thomas In this context it wasn't a bump, it was an edit. Probably an edit by an unregistered user. $\endgroup$ Aug 26, 2012 at 10:54

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.