Monday, March 15, 2010
4:00pm

5130 Upson Hall

Abstract:

In the problem of secure two-party computation, two distrusting players interact to compute a function of their private inputs. General solutions to this problem were found in the 80's, guaranteeing every security property we might desire, with the single exception of \emph{fairness}. Fairness in secure computation is a guarantee that if one player receives output, then both players receive output. This is an important security property for many applications, such as purchasing electronic goods, exchanging signatures on a contract, and others. Unfortunately, it was proven by Cleve in 1986 that without simultaneous message exchange (e.g. when communicating over the internet), we cannot even guarantee fairness in computing boolean XOR.

In this talk we survey several results, new and old, relating to fairness in secure computation. Although fair coin flipping is impossible, we describe the first fair protocols for other functions of interest. We also describe several relaxations that have been considered in the past 20 years, including various notions of "partial" fairness, ways of achieving complete fairness when players are "rational," and settings where we have some limited help from a trusted party. In each of these cases we describe our own contributions at a high level that is accessible to a general audience.