Gilad Asharov (Bar-Ilan university)
Wednesday, 19.3.2014, 12:30
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, finite-domain) boolean functions that can be computed
fairly. This raises the fundamental question of characterizing complete fairness in secure two-party
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.
In addition, we demonstrate that fairness is not restricted to the class of symmetric boolean functions
where both parties get the same output, which is the only known feasibility result. Specifically, we show
that fairness is also possible for asymmetric boolean functions where the output of the parties is not
necessarily the same. Moreover, we consider the class of functions with non-binary output, and show that
fairness is possible for any finite range.
The constructions are based on the protocol of Gordon et. al, and its analysis uses tools from convex