International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Framework for Analyzing Optimistic Fair Exchange with Distributed Arbiters

Alptekin Küpçü
Anna Lysyanskaya
Search ePrint
Search Google
Abstract: Fair exchange is one of the most fundamental problems in secure distributed computation. Alice has something that Bob wants, and Bob has something that Alice wants. A fair exchange protocol would guarantee that, even if one of them maliciously deviates from the protocol, either both of them get the desired content, or neither of them do. It is known that no two-party protocol can guarantee fairness in general; therefore the presence of a trusted arbiter is necessary. In optimistic fair exchange, the arbiter only gets involved in case of faults. To reduce the trust put in an arbiter, it is natural to consider employing multiple arbiters. Avoine and Vaudenay (AV) [6] employ multiple autonomous arbiters in their optimistic fair exchange protocol which uses timeout mechanisms. They leave two open questions: (1) Can an optimistic fair exchange protocol without timeouts provide fairness when employing multiple autonomous arbiters? (2) Can any other optimistic fair exchange protocol with timeouts achieve better bounds on the number of honest arbiters required? In this paper, we answer both questions negatively. To answer these questions, we define a general class of optimistic fair exchange protocols with multiple arbiters, called “distributed arbiter fair exchange” (DAFE) protocols. Informally, in a DAFE protocol, if a participant fails to send a correctly formed message, the other party must contact some subset of the arbiters and get correctly formed responses from them. The arbiters do not talk to each other, but only to Alice and Bob. We prove that no DAFE protocol can exist. However, our impossibility results can be overcome in the timeout model (where all arbiters have access to loosely synchronized clocks) and also in case the arbiters can communicate (e.g., using secure multi-party computation with Omega(n^2) communication).
  title={Framework for Analyzing Optimistic Fair Exchange with Distributed Arbiters},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / optimistic fair exchange, secret sharing, distributed cryptography, threshold cryptography},
  note={Submitted to PODC 2009 14285 received 10 Feb 2009},
  author={Alptekin Küpçü and Anna Lysyanskaya},