Complete Characterization of Two-party Securely Computable Functions



Friday, 14 November 2014, 14:00 to 15:30



Abstract: In two-party secure computation, Alice has an input X, Bob has an input Y and both of them want to compute a function $f:\mathcal{X} \times \mathcal{Y} \to \mathcal{Z}$ securely by exchanging messages to each other over several rounds. By security we mean that they should compute $f(X,Y)$ correctly and either party should not learn any information about the other party's input other than what it can infer from its own input and the function value. We will characterize the class of securely computable functions, i.e., which functions can be computed securely and which cannot be.