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

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

share|improve this question
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
up vote 1 down vote accepted

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.

share|improve this answer
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? – Thomas Lieven Mar 4 '13 at 11:55
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. – Thomas Lieven Mar 4 '13 at 11:57
@ThomasLieven, nothing comes to mind immediately. Perhaps writeup another question and see if others know. I'll continue to think about it. – mikeazo Mar 4 '13 at 16:39

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.