4
$\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.

Improve this question
$\endgroup$
1
  • 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 '19 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).

Improve this answer
$\endgroup$
6
  • $\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 '19 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 '19 at 14:16
  • $\begingroup$ @GeoffroyCouteau: Is it possible to prove that $r_1 = r_2$ in the ElGamal ciphertext $(r_1G, xG + r_2H)$ without revealing either $xG$ or $r_2H$? $\endgroup$ – Fiono Jan 23 '20 at 14:23
  • $\begingroup$ this is a trivial statement: any pair of group elements can be seen as an ElGamal encryption with r1 = r2, for some x. This is in fact equivalent to saying that any pair of group element is a valid Elgamal ciphertext. $\endgroup$ – Geoffroy Couteau Jan 23 '20 at 14:29
  • $\begingroup$ @GeoffroyCouteau: what if the $x$ has to be greater than $0$? If you do a range-proof (e.g. Bulletproofs) on $xG + r_2H$, then, if $r_1 \neq r_2$, the decrypted $x$ will be different and can be $<0$, right? Can you do the range-proof on $xG + r_2H + r_1G$ instead to solve this? $\endgroup$ – Fiono Jan 23 '20 at 15: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.