Return to Answer

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 - r' \bmod n$, which you can verify by checking that $C = a g^D b^n \pmod {n^2}$

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

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'^{-1}r \bmod n$, which you can verify by checking that $C = a g^D b^n \pmod {n^2}$

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 - r' \bmod n$, which you can verify by checking that $C = a g^D b^n \pmod {n^2}$

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 $m$ and send you $a = r^m \bmod n^2$

• You then choose either 0 or 1

• If you pick 0, they output $m$, which you can verify by checking if $a = r^m \pmod{n^2}$

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

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'^{-1}r \bmod n$, which you can verify by checking that $C = a g^D b^n \pmod {n^2}$