Efficiency of optimistic fair exchange using trusted devicesby Mohammad Torabi Dashti

ACM Trans. Auton. Adapt. Syst.


Computer Science (miscellaneous) / Software / Control and Systems Engineering


An efficient protocol for anonymous and fair document exchange

N. Zhang, Q. Shi, M. Merabti

Fair Exchange Mechanism for P2P Systems

Xu Xiao-long, Xiong Jing-Yi, Cheng Chun-Ling

Selection of a Fair Currency Exchange Rate

Allen J. Schwenk

Efficient Packet Scheduling Using Channel Adaptive Fair Queueing in Distributed Mobile Computing Systems

Li Wang, Yu-Kwong Kwok, Wing-Cheong Lau, Vincent K.N. Lau


3Efficiency of Optimistic Fair Exchange Using Trusted Devices


Efficiency of asynchronous optimistic fair exchange using trusted devices is studied. It is shown that three messages in the optimistic subprotocol are sufficient and necessary for exchanging idempotent items. When exchanging nonidempotent items, however, three messages in the optimistic subprotocol are sufficient only under the assumption that trusted devices have unbounded storage capacity. This assumption is often not satisfiable in practice. It is then proved that exchanging nonidempotent items using trusted devices with a bounded storage capacity requires exactly four messages in the optimistic subprotocol.

Categories and Subject Descriptors: C.2.2 [Software Engineering]: Applications; D.2.4 [ComputerCommunication Networks]: Formal methods; K.4.4 [Computers and Society]: Network Protocols—


General Terms: Security, Theory, Verification

Additional Key Words and Phrases: Optimistic fair exchange protocols, trusted computing devices, minimal message complexity, logics of knoweldge, nonidempotent items

ACM Reference Format:

Torabi Dashti, M. 2012. Efficiency of optimistic fair exchange using trusted devices. ACM Trans. Autonom.

Adapt. Syst. 7, 1, Article 3 (April 2012), 18 pages.

DOI = 10.1145/2168260.2168263 http://doi.acm.org/10.1145/2168260.2168263 1. INTRODUCTION

Fair Exchange protocols (hereafter called FE) aim at exchanging items in a fairmanner.

Informally, fair means that all involved parties receive a desired item in exchange for their own, or none of them does so. Deterministic fair exchange protocols cannot be constructed with no presumed trust in the system [Even and Yacobi 1980]. Therefore, many FE protocols rely on impartial processes which are trusted by all the protocol participants, hence called Trusted Third Parties (TTPs). In the presence of a TTP, there is a canonical solution to FE. The items subject to exchange can be sent to the trusted entity and then he would distribute them if all the items arrive in time. If some items do not arrive in time, the TTP would simply abandon the exchange. In the optimistic family of FE protocols, normally the participants execute an optimistic (or, main) subprotocol which does not involve the TTP at all. However, if a failure maliciously or accidentally occurs, the participants are provided with fallback scenarios, which enable them to recover to a fair state with the TTP’s help. When failures are infrequent, optimistic protocols are preferred over those which involve the TTP in each exchange.

In this article, we study optimistic FE between Trusted Computing Devices (TDs).

By construction, TDs follow their certified software, and are guaranteed to observe the terms of use and distribution of digital contents. These devices are nowadays becoming prevalent, particularly in the music industry. A common application of TDs pertains to

This work has been supported by AVANTSSAR, FP7-ICT-2007-1 project no. 216471.

Author’s address: M. Torabi Dashti, ETH Zu¨rich, Informationssicherheit, Basin, CNB F 109.1, Universita¨tstrasse 6, 8092 Zuerich, Switzerland; email: mohammad.torabi@inf.ethz.ch.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted.

To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from

Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 869-0481, or permissions@acm.org. c© 2012 ACM 1556-4665/2012/04-ART3 $10.00

DOI 10.1145/2168260.2168263 http://doi.acm.org/10.1145/2168260.2168263

ACM Transactions on Autonomous and Adaptive Systems, Vol. 7, No. 1, Article 3, Publication date: April 2012. 3:2 M. Torabi Dashti

Table I. Optimal Number of Messages in Two-Party Optimistic Subprotocol Computing devices

Items non-idempotent idempotent non-trusted − 4 trusted, with unbounded storage capacity 3 3 trusted, with bounded storage capacity 4 3 protecting digital contents from unauthorized access (e.g., rendering a video file) and illicit distribution.

Note that TDs are not necessarily operated by honest owners, and they usually have to communicate over insecure media. Therefore, using TDs does not entirely obliterate the need for security protocols to ensure fairness in exchange. One would, however, expect that using TDs results in simpler, more efficient, or value-added FE protocols.

In this article, we show that using TDs does not increase the efficiency of two-party optimistic fair exchange protocols in common practical scenarios. Next, we explain what is meant by efficiency and by common practical scenarios.

The premise of optimistic FE is that failures are infrequent, and consequently fallback subprotocols are executed rarely. Therefore, a meaningful measure of efficiency in these protocols is the number of messages exchanged in the main subprotocol. This number will serve as our measure of efficiency for FE protocols. As a convention we refer to n-message FE protocols, where n refers to the number of messages exchanged in their optimistic subprotocol.

Most existing protocols for fair exchange assume that the items subject to exchange are idempotent, meaning that receiving (or possessing) an item once is not different from receiving it multiple times [Asokan 1998; Pagnia et al. 2003]. For instance, once

Alice gets access to Bob’s signature on a contract, receiving it again does not add anything to Alice’s knowledge. The idempotency assumption reflects mass reproducibility of digital contents. Certain digital items are, however, not idempotent. Electronic vouchers [Fujimura et al. 1999; Fujimura and Eastlake 2003] are prominent examples of nonidempotent items. Depending on the implementation, right tokens in various digital rights management schemes are as well digital nonidempotent items, for example, see Kuntze and Schmidt [2007] and Torabi Dashti et al. [2008]. A common approach to secure use and dissemination of nonidempotent items is to limit their distribution to TDs. We focus on practical scenarios in which fair exchange between TDs needs to ensure that nonidempotent items are not cloned arbitrarily. 1.1. Contributions