On the Classification of Finite Boolean Functions up to Fairness

Gilad Asharov, Amos Beimel, Nikolaos Makriyannis +1 more

W. Michael Dickson

Nikolaos Makriyannis

Abstract. Two parties, P1 and P2, wish to jointly compute some func-tion f(x, y) where P1 only knows x, whereas P2 only knows y. Further-more, and most importantly, the parties wish to reveal only what the output suggests. Function f is said to be computable with complete fair-ness if there exists a protocol computing f such that whenever one of the parties obtains the correct output, then both of them do. The only protocol known to compute functions with complete fairness is the one of Gordon et al (STOC 2008). The functions in question are finite, Boolean, and the output is shared by both parties. The classification of such func-tions up to fairness may be a first step towards the classification of all functionalities up to fairness. Recently, Asharov (TCC 2014) identifies two families of functions that are computable with fairness using the protocol of Gordon et al and another family for which the protocol (po-tentially) falls short. Surprisingly, these families account for almost all finite Boolean functions. In this paper, we expand our understanding of what can be computed fairly with the protocol of Gordon et al. In partic-ular, we fully describe which functions the protocol computes fairly and which it (potentially) does not. Furthermore, we present a new class of functions for which fair computation is outright impossible. Finally, we confirm and expand Asharov’s observation regarding the fairness of fi-nite Boolean functions: almost all functions f: X×Y → {0, 1} for which

Gilad Asharov

The well known impossibility result of Cleve (STOC 1986) implies that in general it is impossible to securely compute a function with complete fairness without an honest majority. Since then, the accepted belief has been that nothing non-trivial can be computed with complete fairness in the two party setting. The surprising work of Gordon, Hazay, Katz and Lindell (STOC 2008) shows that this belief is false, and that there exist some non-trivial (deterministic, nite-domain) boolean functions that can be computed fairly. This raises the fundamental question of characterizing complete fairness in secure two-party computation. In this work we show that not only that some or few functions can be computed fairly, but rather an enormous number of functions can be computed fairly. In fact, almost all boolean functions with distinct domain sizes can be computed with complete fairness (for instance, more than 99:999 % of the boolean functions with domain sizes 31 30). The class of functions that is shown to be possible includes also rather involved and highly non-trivial tasks, such as set-membership, evaluation of a private (boolean) function, private matchmaking and set-disjointness.

Guoliang Xu, Mengsi Zhang, Binbin Zhang +2 more

Gilad Asharov, Amos Beimel, Nikolaos Makriyannis +1 more

Abstract. 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. Alas, an implication of Cleve’s result [18th ACM Symposium on the Theory of Computing, 1986] is that when there is no honest majority, in particular in the important case of the two-party setting, there exist functions that cannot be computed with fairness. In a surprising result, Gordon et al. [18th ACM Symposium on the Theory of Computing, 2008; J. ACM, 58 (2011), 24] showed that some interesting functions can be computed with fairness in the two-party setting and reopened the question of understanding which Boolean functions can be computed with fairness, and which cannot. 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 statement of 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. This is true for both deterministic and randomized functions. To prove the possibility result, we modify the protocol of Gordon et al.; the resulting protocol computes with full security (and in particular with fairness) all functions that are computable with fairness. Complementing this result, we also show that any function that does not satisfy the aforementioned condition can be reduced to a fair sampling protocol, which, by Agrawal and Prabhakaran [ Advances in Cryptology – CRYPTO 2013, 2013], cannot be computed with fairness.