Title: Complete Characterization of Two-Party Boolean Functions that are Computable with Fairness
Classic results from the theory of secure computation stipulate that every efficiently computable function can be computed efficiently and securely when its inputs are distributed among (possibly malicious) parties. When a strict majority of honest parties can be guaranteed, such protocols provide full security, e.g., they are correct, private, guarantee independence of inputs, and they are fair.Fairness is a desirable property in secure computation; informally it means that if one party gets the output of the function, then all parties get the output. For example, when two parties are signing a contract, it means that one party signs the contract if and only if the second party signs the contract. Alas, an implication of Cleve’s result (STOC 86) is that when there is no honest majority, in particular in the important case of the two-party setting, there exist Boolean functions that cannot be computed with fairness. In a surprising result, Gordon et al. (JACM 2011) showed that some interesting functions can be computed with fairness in the two-party setting, and re-opened the question of understanding which Boolean functions can be computed with fairness, and which cannot.
In this talk, I will present the findings of our paper "Complete Characterization of Two-Party Boolean Functions that are Computable with Fairness", a joint work with G. Asharov, A. Beimel and E. Omri published in TCC15. In particular, our main result is a complete characterization of the Boolean functions that can be computed with fairness in the two-party setting; this settles the open problem of Gordon et al. The characterization is quite simple: A function can be computed with fairness if and only if the all one-vector or the all-zero vector are in the affine span of either the rows or the columns of the matrix describing the function.