- Towards Characterizing Comp...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in February 2014
Towards Characterizing Complete Fairness in Secure Two-Party Computation
Speaker:
Gilad Asharov
, Bar-Ilan University
Date: Friday, February 21, 2014
Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone
Public: Yes
Location: 32-G449
Event Type:
Room Description:
Host: Vinod Vaikuntanathan, TOC, CSAIL, MIT
Contact: Holly A Jones, hjones01@csail.mit.edu
Relevant URL: http://toc.csail.mit.edu/node/497
Speaker URL: None
Speaker Photo:
None
Reminders to:
cis-seminars@csail.mit.edu, seminars@lists.csail.mit.edu
Reminder Subject:
TALK: Towards Characterizing Complete Fairness in Secure Two-Party Computation
ABSTRACT:
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 (i.e., functions f: X x Y -> {0,1} where |X| and |Y| are distinct. 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-disjoint and more.
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.
Research Areas:
Impact Areas:
Created by Holly A Jones at Thursday, January 16, 2014 at 3:16 PM.