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 Damgård and Mads Jurik - A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System Link

  • $\begingroup$ 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? $\endgroup$
    – mikeazo
    Feb 26, 2013 at 12:33
  • $\begingroup$ 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. $\endgroup$ Feb 27, 2013 at 10:05

1 Answer 1


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

With the ZKP, the verifier cannot prove anything to anyone else about that ciphertext. This seems like a useful property in some situations.

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.

  • $\begingroup$ Now that you mention it I come to realize that the proof can be passed on without loss of authenticity. Its obvious but I did not think of it. As for me this is only partially a problem. Is there a way to turn "revealing r" into an interactive version involving a challenge? Would this solve the problem of transferable proof? $\endgroup$ Mar 4, 2013 at 11:55
  • $\begingroup$ Assuming "revealing r" would provide any information about the summands of a Paillier homomorphically added sum. Would it help to use primes as random factors for the encryption of the summands? I mean an attacker then would have to find an efficient way to factorize the resulting r. $\endgroup$ Mar 4, 2013 at 11:57
  • $\begingroup$ @ThomasLieven, nothing comes to mind immediately. Perhaps writeup another question and see if others know. I'll continue to think about it. $\endgroup$
    – mikeazo
    Mar 4, 2013 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.