# ZKP of the validity of a decryption key without revealing the message in public

1. Alice publicly shares encrypted message $E_k(m)$.
2. Alice publicly shares the key encrypted with Bob's public key $E_\mathit{bob}(k)$.
3. Alice wants to create a Zero-Knowledge Proof that this is indeed the key that unlocks $E_k(m)$ encrypted with Bob's public key, such that anyone can be convinced that Bob can now know the message $m$ by decrypting $E_k(m)$ without revealing any information about $m$ or Bob's private key.

Is this possible using cryptographic tools (ZKPs, SNARKS, hashes, etc...)?

• This question is closely related to zero knowledge proof application, which is basically asking the same question but for a CSPRNG and its seed instead of some arbitrary encryption method and the message. – tylo Aug 28 '17 at 14:58
• Are those methods efficient in practice? – user47376 Aug 28 '17 at 15:48
• That depends a lot on what encryption schemes you want to use. But in general: No, quite likely they are not efficient in practice. If they are non-algebraic encryption schemes, it also requires a lot of handywork to set up the garbled circuits, etc. – tylo Aug 29 '17 at 8:10

You could solve the problem using a kind of cryptographic commitment, but it requires an additional message from Bob.

(I'm assuming $k$ is a symmetric key from the context of your post)

Alice picks another message, $m_2$, and posts $E_k(m_2)$ and $Hash(m_2)$, using a cryptographic hash function like SHA-256 or what you.

Once Bob gets $k$, he uses it to find $m_2$, and then reveals it. Anyone can check the validity of his $m_2$ by hashing it and checking against Alice's commitment.

Nothing is learned about $m$ unless the symmetric cipher itself leaks information.

• Although your answer is good, I actually secretly wanted to use this as a part of a fair exchange protocol. The "extra message" from Bob is a kind of acknowledgement of the transaction which raises the problem that he can deny it and spoil the fair exchange. – user47376 Aug 29 '17 at 10:49