4

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.

AleksanderCH
  • 6,435
  • 10
  • 29
  • 62
Evgeniy Gryaznov
  • 43
  • 2

1 Answers1

6

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

Geoffroy Couteau
  • 19,919
  • 2
  • 46
  • 68
  • Thank you. Do you know where the following statement: every statement in NP can be proven in zero-knowledge was proved? – Evgeniy Gryaznov Apr 09 '19 at 14:05
  • 2
    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. – Geoffroy Couteau Apr 09 '19 at 14:16
  • @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$? – Fiono Jan 23 '20 at 14:23
  • 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. – Geoffroy Couteau Jan 23 '20 at 14:29
  • @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? – Fiono Jan 23 '20 at 15:16
  • greater than 0 is not obvious to define over known order groups, but if by that you mean that the natural mapping of $x \in G$ to map$(x) \in [-p/2,p/2]$, then sure, this becomes a well defined NP language L and - as for any NP language - you can prove in zero-knowledge that a word belongs to L (e.g. using a range proof as you suggest). – Geoffroy Couteau Jan 23 '20 at 22:40