Protocols for secure two-party computation allow users holding inputs x and y, respectively, to compute f(x,y) while preserving privacy, correctness, and more in the presence of malicious behavior. A protocol is *fair* if either both parties learn the output, or else neither of them do.
Cleve (1986) showed that even completely fair computation of boolean XOR is impossible, and since then the question of complete fairness in two-party computation has been considered closed. Cleve's result, however, only says that complete fairness is impossible *in general*. We ask whether there are *any* interesting examples of functions that can be computed with complete fairness, and make the first progress on this question in 20 years.
We also consider a (mild) relaxation of fairness, and give a complete characterization of when this notion is achievable.
Based on joint work with Carmit Hazay, Dov Gordon, and Yehuda Lindell
Dr. Jonathan Katz received S.B. in both Chemistry and Mathematics from MIT, M.A. in Chemistry from Columbia University, and M. Phil. in Computer Science from Columbia University. He is an invited participant of DARPA Computer Science Study Group of 2009 and winner of NSF CAREER award, 2005-2010. He is currently an Associate Professor at the Department of Computer Science, University of Maryland, responsible for maintaining a world-class research program in cryptography and information security. He teaches courses in cryptography, theoretical computer science and network security.