Suppose there is a plaintext p, which is encrypted with a symmetric cipher using a key k, resulting in a ciphertext c. Bob knows both c and k, but Alice knows only c. Is there any protocol by which Alice can be certain (maybe with some probability) that Bob indeed does know p, without revealing to her p itself?
Also, it be great to not have to have any third-party involved.
Yes, this is possible: every statement in NP can be proven in zero-knowledge, meaning, without revealing anything more than the very fact that the statement is true. In fact, this result can be extended to proofs of knowledge, where the prover does not only show that a statement is true, but also that he does know a witness (still without revealing it).
Of course, general techniques are very inefficient. For standard symmetric ciphers, the best approaches will use general zero-knowledge proofs for statements represented by boolean circuit - see my answer to the question that AleksanderRas links to in the comment section. You should also note that if you replace the symmetric cipher by a cipher with a strong algebraic structure, such as ElGamal, then much (much) more efficient solutions exist - for example, in ElGamal, proving knowledge of a plaintext requires only exchanging a few string (about twice more communication than simply sending the ciphertext - so really not much).
every statement in NP can be proven in zero-knowledge was proved?
$\endgroup$
– Evgeniy Gryaznov
Apr 9 at 14:05
