[Busec] BUsec this week: Gilad Asherov (Wed 9:30)

Sharon Goldberg goldbe at cs.bu.edu
Wed Feb 19 08:01:26 EST 2014

At seminar today, we have a talk by Gilad Asherov about fairness in
two-party computation; Gilad's seminar will start a bit earlier than usual
(9:30am Wed).


 BUsec Calendar:  http://www.bu.edu/cs/busec/
 BUsec Mailing list: http://cs-mailman.bu.edu/mailman/listinfo/busec
 How to get to BU from MIT: The CT2 bus or MIT's "Boston Daytime Shuttle"

Towards Characterizing Complete Fairness in Secure Two-Party Computation.
Gilad Asharov. Bar Ilan University.
Wed, February 19, 9:30am - 11:00am

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 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 (for instance, more
than $99.999\%$ of the boolean functions with domain sizes $31 \times 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 and private matchmaking. 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

Sharon Goldberg
Computer Science, Boston University

Sharon Goldberg
Computer Science, Boston University
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20140219/38299439/attachment.html>

More information about the Busec mailing list