# Proof of Communication

I desire an algorithm in which Alice sends a block of data $X$ to Bob, with proof that the data was both sent and received. Ideally this would take the form of a public-key signature of the block $X$ by both Alice and Bob, so that each is in possession of (X + sign(X,A) + sign(X,B)).

Further let us assume that Alice and Bob both may have motivation to lie about having sent/received the communication. Bob may choose to lie depending on the contents of $X$ once he sees it, and Alice may lie to attempt to discredit Bob. Therefore the signatures or other proof of communication must be revealed simultaneously to both Alice and Bob. At no point may either be in possession of the proof while the other is not.

I'd put a bounty on this if I had any reputation, but hopefully people will just consider it an interesting challenge. Some notes that may help: This is closely related to the Two-Generals problem (for which there is no two-party solution), however due to cryptography orders may not be forged, so I hold hope that there may be a two-party solution. If not, a multi-party solution (using witnesses) is acceptable. An example of an algorithm which simultaneously reveals information is Diffie-Hellman, but the shared secret there cannot be chosen by either party, so cannot itself contain any information.

• Just to be sure I get it right: is this a “question” or a “challenge”? – e-sushi Aug 22 '14 at 14:41
• If I'm reading your question correctly, I believe this is a special case of fair secure function evaluation, where the function of interest is F((A,X); B) = ((X,sig(X,A),sig(X,B)); (X,sig(X,A),sig(X,B))). See e.g. cs.umd.edu/~jkatz/papers/fair2party.pdf – Daniel Apon Aug 22 '14 at 17:31
• Many years ago, I was explained in high level terms, how a protocol for this could be implemented. I didn't get to look into the details though. The idea was to take turns in revealing bits of information, including zero-knowledge proofs of correctness. Neither party would ever get more than one bit ahead, which means at any given point each party could brute-force the rest of the bits, and the difference in computation needed would be at most a factor two. – kasperd Aug 23 '14 at 20:57
• @kasperd I thought about that too, but that leaves you in a situation where the communication can be incomplete, but the missing signature may be brute-forced. (Because some of it has already been exchanged, the search space is reduced -- just imagine that the connection is closed before the last bit is received). – Bob McElrath Aug 24 '14 at 12:37