1
$\begingroup$
  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...)?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – tylo Aug 28 '17 at 14:58
  • $\begingroup$ Are those methods efficient in practice? $\endgroup$ – user47376 Aug 28 '17 at 15:48
  • $\begingroup$ 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. $\endgroup$ – tylo Aug 29 '17 at 8:10
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – user47376 Aug 29 '17 at 10:49

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.