3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Not sure if this is possible, but I found this question which is somehow related (here Alice knows $p$). $\endgroup$ – AleksanderRas Apr 9 at 9:38
6
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Thank you. Do you know where the following statement: every statement in NP can be proven in zero-knowledge was proved? $\endgroup$ – Evgeniy Gryaznov Apr 9 at 14:05
  • 2
    $\begingroup$ yes, look up "proofs that yield nothing but their validity and a methodology of cryptographic protocol design". In modern terms, the underlying assumption is the existence of OWFs. $\endgroup$ – Geoffroy Couteau Apr 9 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.