Consider that I wish to prove knowledge of some RSA private key corresponding to a public key $(e,N)$. A naive interactive proof scheme would proceed as follows:
- $V$ generates some random message $m$ and encrypts it, sending the encrypted data $c$ to $P$
- $V$ then requests $m$ back from $P$. Assuming $P$ could have no knowledge of $m$ outside of $c$, then $P$ can prove knowledge of $d$ by responding with the correct $m$
This appears to be sound and complete on the assumption of hardness of the RSA problem. Clearly, this must be a private-coin system, since if random data was public then a dishonest $P$ would be able to deduce any $m$. I think we also need the assumption that this is an honest-verifier scheme on the basis that a decryption oracle would allow for a break of textbook RSA (I think). However, we could also abstract away the details of the asymmetric cryptosystem used, and assume it is some theoretical asymmetric cryptosystem which cannot be broken using a decryption oracle, and then I think we could drop this stipulation.
Intuitively, this scheme is not zero-knowledge, since we are giving away something somewhat significant (i.e. the decryption of an arbitrary $c$). However, we can easily construct a simulator for this scheme which will choose some random $m$, encrypt it, and then just send back the original $m$ - which implies that it is in fact zero-knowledge. Am I missing some nuance here with what the simulator can/cannot do?
Is this scheme zero-knowledge with RSA (why/why not)? If it isn't, would it be zero-knowledge with some idealised asymmetric scheme which is not vulnerable to any attacks based on decryption oracles (why/why not)?