8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Just to be sure I get it right: is this a “question” or a “challenge”? $\endgroup$ – e-sushi Aug 22 '14 at 14:41
  • $\begingroup$ 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 $\endgroup$ – Daniel Apon Aug 22 '14 at 17:31
  • 1
    $\begingroup$ 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. $\endgroup$ – kasperd Aug 23 '14 at 20:57
  • $\begingroup$ @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). $\endgroup$ – Bob McElrath Aug 24 '14 at 12:37
3
$\begingroup$

This sounds like "fair exchange," the subject of many good research papers. In general you need a third party to give any security guarantees, but "optimistic fair exchange" involves the third party only when one of the parties tries to cheat (i.e., when both play honestly there is no involvement from the third party).

Incidentally, Diffie-Hellman is most certainly not fair: whoever sends first lets the other party compute the key before the original sender can.

$\endgroup$
  • $\begingroup$ Indeed it is "Fair Exchange", thanks for making that connection. I still have not seen a solution I like. The best ones rely on third parties (a "Post Office" or "Oracle"), but if the third party is untrusted, you need a fourth party in case the third lies...and a fifth...and a sixth. So it seems to me it can't work among untrusted parties. Providing a statistical security guarantee (assuming only a small fraction will lie) exponentially balloons the amount of communication required. If C needs a third party to verify communication with B also... $\endgroup$ – Bob McElrath Aug 27 '14 at 12:45

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.