Paper Info
Title
Optimal randomized fair exchange with secret shared coins
Abstract
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 agressive 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.
Year
DOI
Venue
2005
10.1007/11795490_7
OPODIS
Keywords
Field
DocType
communication protocol,secret sharing,pseudo random number generator
Psychological resilience,Randomized algorithm,Computer science,Computer security,Fault tolerance,Cheating,Adversary,Digital goods,Random number generation,Distributed computing,Communications protocol
Conference
Volume
ISSN
ISBN
3974
0302-9743
3-540-36321-1
Citations 
PageRank 
References 
7
0.55
22
Authors
3
Name
Order
Citations
PageRank
Felix C. Freiling11415137.30
Maurice Herlihy28623920.94
Lucia Draque Penso319620.46