The following technical report is available from http://aib.informatik.rwth-aachen.de: Optimal Randomized Fair Exchange with Secret Shared Coins Felix Freiling, Maurice Herlihy, Lucia Draque Penso AIB 2005-22 In the fair exchange problem, mutually untrusting parties must securely exchange digital goods. A fair exchange protocol must ensure that no combination of cheating or failures will result in some goods being delivered but not others, and that all goods will be delivered in the absence of cheating and failures. This paper proposes two novel randomized protocols for solving fair exchange using simple trusted units. Both protocols have an optimal expected running time, completing in a constant (3) expected number of rounds. They also have optimal resilience. The first one tolerates any number of dishonest parties, as long as one is honest, while the second one, which assumes more aggressive cheating and failures assumptions, tolerates up to a minority of dishonest parties. The key insight is similar to the idea underlying the code-division multiple access (CDMA) communication protocol: outwitting an adversary is much easier if participants share a common, secret pseudo-random number generator. -- Peter Schneider-Kamp mailto:psk@informatik.rwth-aachen.de LuFG Informatik II http://www-i2.informatik.rwth-aachen.de/~nowonder RWTH Aachen phone: ++49 241 80-21211