# 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? 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

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