Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

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.

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

share|improve this question
up vote 1 down vote accepted

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.
share|improve this answer
Dear Community♦. I cannot understand why you add the comment, because Lieven asks the question on the same encryption key. – xagawa Jul 27 '12 at 15:19
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). – Thomas Aug 25 '12 at 14:12
@Thomas In this context it wasn't a bump, it was an edit. Probably an edit by an unregistered user. – CodesInChaos Aug 26 '12 at 10:54

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.