Brief announcement: impossibility results for optimistic fair exchange with multiple autonomous arbiters

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, but needs to be trusted. To reduce the trust put in the arbiter, it is natural to consider employing multiple arbiters.

Expensive techniques like byzantine agreement or secure multi-party computation with Ω(n²) communication can be applied to distribute arbiters in a non-autonomous way. Efficient protocols can be achieved by keeping the arbiters autonomous (non-communicating). Avoine and Vaudenay [5] employ multiple autonomous arbiters in their optimistic fair exchange protocol which uses global timeout mechanisms; all arbiters have access to loosely synchronized clocks. They left two open questions regarding the use of distributed autonomous arbiters: (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 communicate with each other, but only to Alice and Bob. We prove that no DAFE protocol can meaningfully exist.

REFERENCES

• 1: N. Asokan , Matthias Schunter , Michael Waidner, Optimistic protocols for fair exchange, Proceedings of the 4th ACM conference on Computer and communications security, p.7-17, April 01-04, 1997, Zurich, Switzerland [doi>10.1145/266420.266426]
• 2: N. Asokan, V. Shoup, and M. Waidner. Optimistic fair exchange of digital signatures. In EUROCRYPT, 1998.
• 3: N. Asokan, V. Shoup, and M. Waidner. Optimistic fair exchange of digital signatures. IEEE Selected Areas in Communications, 18:591--610, 2000.
• 4: Giuseppe Ateniese, Efficient verifiable encryption (and fair exchange) of digital signatures, Proceedings of the 6th ACM conference on Computer and communications security, p.138-146, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319728]
• 5: G. Avoine and S. Vaudenay. Optimistic fair exchange based on publicly verifiable secret sharing. ACISP, 2004.
• 6: F. Bao, R. Deng, and W. Mao. Efficient and practical fair exchange protocols with off-line TTP. In IEEE Security and Privacy, 1998.
• 7: Mira Belenkiy , Melissa Chase , C. Chris Erway , John Jannotti , Alptekin Küpçü , Anna Lysyanskaya , Eric Rachlin, Making p2p accountable without losing privacy, Proceedings of the 2007 ACM workshop on Privacy in electronic society, October 29-29, 2007, Alexandria, Virginia, USA [doi>10.1145/1314333.1314339]
• 8: Michael Ben-Or , Ran Canetti , Oded Goldreich, Asynchronous secure computation, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.52-61, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167109]
• 9: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 10: Ran Canetti , Tal Rabin, Fast asynchronous Byzantine agreement with optimal resilience, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.42-51, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167105]
• 11: Y. Dodis, P. Lee, and D. Yum. Optimistic fair exchange in a multi-user setting. LNCS, 4450:118, 2007.
• 12: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 13: A. Küpçü and A. Lysyanskaya. Usable optimistic fair exchange. In Cryptology ePrint Archive, Report 2008/431, 2008.
• 14: A. Küpçü and A. Lysyanskaya. Framework for analyzing optimistic fair exchange protocols with distributed arbiters. In Cryptology ePrint Archive, Report 2009/069, 2009.
• 15: S. Micali. Simultaneous electronic transactions with visible trusted parties. US Patent 5,553,145, 1996.
• 16: Silvio Micali, Simple and fast optimistic protocols for fair electronic exchange, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.12-19, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872038]
• 17: H. Pagnia and F. Gärtner. On the impossibility of fair exchange without a trusted third party. Darmstadt University of Technology, TUD-BS-1999-02, 1999.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Security

Keywords:
distributed arbiters, optimistic fair exchange, trusted third party