Published by Dept. CS U. Chicago. Copyright 2009 CJTCS and the author.
In the setting of secure multiparty computation, a set of mutually
distrustful parties wish to
securely compute some joint function of their private inputs. The computation
should be carried
out in a secure way, meaning that the properties privacy, correctness,
independence of inputs,
fairness and guaranteed output delivery
should all be preserved. Unfortunately, in the case of no
honest majority -- and specifically in the important two-party case -- it is
impossible to achieve fairness and guaranteed output delivery.
In this paper we show how a legal infrastructure that respects digital
signatures can be used to enforce fairness in two-party computation. Our
protocol has the property that if one party obtains output while the
other does not (meanig that fairness is breached) then the party not obtaining
output has a digitally signed cheque from the other party. Thus, fairness can
be "enforced" int the sense that any breach results in a loss of money by the
Submitted January 16, 2008, revised version submitted June 10 2009, published June 12 2009.