Goal

I want Alice and Bob to communicate a message without their answers influencing each other. More formally:

  • Alice wants to send Bob a message, a.
  • Bob wants to send Alice a message, b.
  • But Alice must not know b before sending a
  • And Bob must not know a before sending b.

Attempt

I was thinking I could have:

  • Alice sends an encrypted message, f(a, p1) = a', and a hash with the original message and the private key, h(a, p1).
  • Bob also sends an encrypted message, f(b, p2) = b' and hash, h(b, p2).
  • Alice and Bob exchange private keys once they have received their messages
  • They decrypt the received messages and verify the hash matches

Is there any problems with this method? Would it be feasible for Alice to construct a p' that causes the message to be decrypted as something other than a yet still satisfy the hashing function? (assuming cryptographically secure f and h)

Are there more commonly accepted ways to do this?


previously posted in security stack exchange but was told it'd be more appropriate here

up vote 1 down vote accepted

What you want is a commitment scheme.
Typically these are a pair of functions $c(m), v(c,m')$ where the first creates a commitment (while not leaking information on $m$) and the latter verifies a commitment against a message.

Let $c(\cdot)$ be such a committing algorithm, then you can use the following protocol:

\begin{align} A\to B:\quad &c(a)\\ B\to A:\quad &b\\ A\to B:\quad &a \end{align}

In this case, A doesn't know $b$ when sending $a$, and B doesn't know $a$ when sending $b$. When A then sends $a$, B can verify that this $a$ is indeed the $a$, A commited to earlier and thus that it wasn't chosen in dependence of $b$.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.