# 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. http://www.springerlink.com/content/kwjvf0k8fqyy2h3d/?MUD=MP

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?

-

## 1 Answer

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

Answers:

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.
-
Dear Community♦. I cannot understand why you add the comment, because Lieven asks the question on the same encryption key. – xag 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

1
@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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 49, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9088549613952637, "perplexity_flag": "middle"}