In How to prove correct decryption in Paillier cryptosystem, it was asked whether Alice (in sole possession of the secret key) can convince Bob that a given plaintext is the decryption of a ciphertext provided by Bob (who doesn't know its contents). In the case of Paillier encryption, the answer seems to be yes. Is anyone aware of a corresponding (preferably zero knowledge) solution to this problem in the case of Goldwasser-Micali encryption?
Thanks,
Neil.
Goldwasser Micali encrypts a 0 by sending a quadratic residue and a 1 by sending a non-quadratic residue. So, to prove that the encrypted bit is 0 what you need is a zero-knowledge proof of quadratic residuosity: for a given $b,N$, does there exist an $a$ such that $a^2 = y \bmod N$. There exist such proofs, and it should be easy to find online. However, for 1, that would be harder since in general it's harder to prove that something does not exist (naively, this would be a co-NP statement, which doesn't necessarily have an efficient proof). So, the idea is to try to change what you are looking to prove to something easier. The Goldwasser Micali public key includes a value $x$ that is not a quadratic residue. Then, an encryption of 1 is generated by choosing a random quadratic residue and multiplying it by $x$. Given this, you can prove that a value $b$ is an encryption of the bit 1 by first dividing by $x$ and then proving that the result is a quadratic residue (i.e., prove that $b \cdot [x^{-1} \bmod N] \bmod N$ is a quadratic residue). Note that the inverse can be computed using GCD, so that's easy.
