Is there a cryptographic (or even not entirely cryptographic) way of exchanging objects between Alice and Bob that would not require a third party, and Alice and Bob would not need to trust each other? For example, Alice and Bob have Y and X objects (some information) and want to exchange them (in other words both Alice and Bob after transaction will have access to the set Y∪X). How can they do this directly to each other? Is it possible to solve this problem, for example, using private keys, zk-proofs, etc? Is it possible to solve it in principle? Thank you!

  • $\begingroup$ To make the problem more concrete, assume that Alice and Bob have cryptographic hashes of the desired data. (We can also assume Alice and Bob are identified by public keys but that doesn't seem so important.) Assuming Alice and Bob take turns communicating and the protocol has a deterministic number of rounds, then there is a last round where Bob, say, will send a message but not receive a response. At this point Bob already knows Y and Alice does not know X, so Bob could just not send the message. It's probably possible to make it so that Alice at least has some of X, in this case. $\endgroup$ – Derek Elkins Mar 17 '18 at 20:14

This is known as the fair exchange problem. There's lots of research on the topic; see the link for an overview and starting point.

  • $\begingroup$ As described in the introduction of Efficiently Making Secure Two-Party Computation Fair which is indirectly referenced by that answer, the two approaches to this problem either involve a Trusted Third Party (TTP) or Gradual Release which corresponds one party potentially getting only partial information. The introduction briefly includes an argument similar to the one in my comment. That said, the amount of involvement and what the TTP is trusted to do can be somewhat limited as described in the paper. $\endgroup$ – Derek Elkins Mar 18 '18 at 22:32
  • $\begingroup$ @DerekElkins, absolutely. There is work on reducing or eliminating the need for a TTP, including gradual release, as well as Bitcoin-based methods (though perhaps you could consider the Bitcoin network as the TTP). Anyway, hopefully this should be enough of a starting point to learn more. $\endgroup$ – D.W. Mar 19 '18 at 0:04

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.