# Questions about proof of correct encryption in the Paillier cryptosystem

In the Paillier cryptosystem [1] the encryption of $m \in \mathbb{Z}_N$ with randomness $r \in \mathbb{Z}_n^*$ is $c = g^m r^n \bmod{n^2}$. A proof of correct encryption could look like presented in section 4.2 of [2]:

"Suppose a prover $P$ presents a sceptical verifier $V$ with a ciphertext $c$ and claims that it encodes plaintext $i$. A trivial way to convince $V$ would be to reveal also the random choice $r$, then $V$ can verify himself that $c = E(i, r)$. However, for use in the following, we need a solution where no extra useful information is revealed."

Although I understand the proof itself I don't get the exact point of where it is supposed to offer "extra useful information".

Comparing the proof to the proposed Zero Knowledge Proof the verifier does not learn anything apart from what the proof is all about. $n$ and $g$ are part of the public key, $m$, $r$ and $c$ are presented for verification of encryption. Of course the disclosure of $r$ obliterates the probabilism of the system but what is to be gained by this if you already know the plaintext?

Having asked this I have another question that seems closely related to the one above:

Supposed I were to homomorphically sum up the encryptions of a couple of messages from a limited publicly known set of plaintexts $S=\{0, 1\}$. If I then were to proof the correct encryption of the sum by disclosing the encrypted sum, the plaintext sum and the resulting random factor r for the encrypted sum - would this provide any useful information about which summand encrypts which plaintext message?

[1] Pascal Paillier - Public-Key Cryptosystems Based on Composite Degree Residuosity Classes Link

[2] Ivan Damgard and Mads Jurik - A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System Link

-
When you say "Although I understand the proof itself" what proof are you talking about? The simple proof of revealing $r$ or the ZKP that is developed in that section? –  mikeazo Feb 26 '13 at 12:33
I understand why revealing r is a correct proof of encryption. Also the ZKP presented in the linked paper seems to be no voodoo. What I don't get is why the authors of the said paper claim that revealing r also reveals useful information. I was afraid I missed anything and decided to ask here before asking the authors. –  Thomas Lieven Feb 27 '13 at 10:05

Revealing $r$ would then allow the verifier to prove to someone else (another verifier) that $c$ encodes $i$. The verifier could also prove other things knowing $r$ to a different verifier (any other proof using a paillier ciphertext, the corresponding plaintext, and the random value $r$).
To answer your second question, assuming what I have said is the only side effect of revealing $r$, then your method would also allow the verifier to prove things about the sum to another verifier. That may or may not be an issue with your system. There could be other side effects that I am not aware of.