Towards 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 amount of functions can be computed with complete fairness. In fact, almost all boolean functions with distinct domain sizes can be computed with complete fairness (i.e., functions $f: X \times Y \rightarrow \{0,1\}$ with $|X| \neq |Y|$). The class of functions that is shown to be possible includes also very interesting tasks, such as set-membership, private evaluation of a (Boolean) function, private matchmaking, set-disjointness and more.