I have a Paillier Cyphertext C and a counterparty that controls the keypair that was used to encrypt the data D to arrive at C.

How can they prove to me that the Cyphertext C is actually the encryption of a particular value, e.g. how can they prove that D=0 without giving me the secret key?

Equivalently, how can that counterparty prove to me that the decryption of C is some value V or not?

up vote 4 down vote accepted

Assuming that $D$ is the correct decryption, we have

$$C = g^D r^n \pmod{n^2}$$

for some value $r$.

Someone with the private key can easily recover $r$; hence they can just display it (and you can easily verify the above equation).

Learning the value $r$ does not allow you to derive the private key (if it did, you could encrypt values yourself using a known value $r$, and then use that to recover the private key).

Alternatively, if you need a zero knowledge proof (for example, if the value of $r$ would tell you something about the internal computations that the other side doesn't want you to know), you can do something like this cut-and-choose protocol several times:

  • They pick a random number $r'$ with $\gcd(r', n)=1$, and send $a = r'^n \bmod n^2$

  • You then choose either 0 or 1

  • If you pick 0, they output $r'$, which you can verify by checking if $a = r'^n \bmod n^2$

  • If you pick 1, they output $b = r \cdot r'^{-1} \bmod n$, which you can verify by checking that $C = a g^D b^n \pmod {n^2}$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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