Our main result in this work is a complete characterization of the (symmetric) Boolean functions that can be computed with fairness in the two-party setting; this settles an open problem of Gordon et al. The characterization is quite simple: A function can be computed with fairness \emph{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. This is true for both deterministic and randomized functions. To prove the possibility result, we modify the protocol of Gordon et al.\ (JACM 2011); the resulting protocol computes with full security (and in particular with fairness) all functions that are computable with fairness.
We extend the above result in two directions. First, we completely characterize the Boolean functions that can be computed with fairness in the multiparty case, when the number of parties is constant and at most half of the parties can be malicious. Second, we consider the two-party setting with asymmetric Boolean functionalities, that is, when the output of each party is one bit, but the outputs are not necessarily the same. We generalize our aforementioned protocol for symmetric functions to handle asymmetric functions, and obtain a sufficient condition for computing such functions with fairness. In addition, we provide a necessary condition for fairness; however, a gap is left between these two conditions. We then consider a specific asymmetric function in this gap area, and by designing a new protocol, we show that it is computable with fairness. However, we do not give a complete characterization for all functions that lie in this gap, and their classification remains open.
Category / Keywords: cryptographic protocols / Fairness, secure two-party computation, foundations, malicious adversaries Date: received 16 Dec 2014 Contact author: asharov at cs huji ac il Available format(s): PDF | BibTeX Citation Version: 20141218:035107 (All versions of this report) Discussion forum: Show discussion | Start new discussion