Zero knowledgeness of a simple protocol Say there's a public encryption scheme whose public key is $p_k$ and secret key is $s_k$. Prover $P$ wants to convince verifier $V$ that he knows $s_k$. The protocol is:


$V$ uniformly generates $m$ and sends $c = Enc_{p_k}(m)$ to $P$
$P$, receiving $c$, sends $m&#39; = Dec_{s_k}(c)$ to $V$
$V$ checks whether $m = m&#39;$. If so, accept. Else, reject.


Completeness and soundness are obvious. Intuitively decryption shouldn't leak information about the secret key $s_k$ if this scheme is CCA-secure. But I just haven't come up with a proper simulator to argue this. If $V$ cheats, it's hard to get the correct plaintext without knowledge of $s_k$. If the simulator just guess, the probability is so low that exponentially many rounds are required. So the question is:

Is this protocol really zero knowledge? If so, how to construct the simulator?
First, I think the CCA-security is not enough, and the encryption scheme must be at least IND-CCA2-secure.

Second, I believe the protocol is not zero-knowledge, at least in the auxiliary-input model. The reasoning is as follows: Let z be the auxiliary input to the malicious verifier V*. It's safe to assume that $z = Enc_{p_k}(m)$, where m is unknown to V*. Then, V* can deviate from the original protocol: Instead of choosing a random m and computing c (as prescribed in the protocol), she lets c = z, and sends c to the prover. This way, V* exploits P as a "decryption oracle," and obtains knowledge beyond what she could possibly compute.

One piece of advice: Read the paper Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks, specially section 4. It suggests a protocol similar to yours; one which has never been realized. It also proposes the now-famous "knowledge-of-exponent" assumption (KEA), one which was later used to construct a non-black-box ZK protocol. (The reason why you can't find a simulator, beyond the line of reasoning above, is that you try to imagine a black-box simulator. That's impossible by the result of Goldreich and Krawczyk). For more info on the use of the KEA in constructing non-black-box ZK, see [Hada and Tanaka] and the more recent [Bellare and Palacio].

--Edit-- @cyker: I'm working on a similar issue as (presumably) you're doing: The (right) definition of simulators. A partial result of mine, closely related to the protocol you offered, can be found at http://eprint.iacr.org/2010/150. The latest results are submitted but not published online yet.