# Prove that some Cyphertext C encrypts some plaintext D

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?

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