A Secure Function Evaluation (SFE) of a two-variable function f is a protocol that allows two parties with inputs x and y to evaluate f(x,y) in a manner where neither party learns `` more than is necessary". A rich body of work deals with the study of completeness for secure two-party computation. A function f is complete for SFE if a protocol for securely evaluating f allows the secure evaluation of all (efficiently computable) functions. The questions investigated are which functions are complete for SFE, Which functions have SFE protoccols and whether there are functions that are neither complete nor have SFE protocols.
Previous study of these questions was mainly conducted from an Information Theoretic point of view and provided strong answers in the form of combinatorial properties. However, we show that there are major differences between the information theoretic and computational settings. In particular, we show functions that are considered trivial by the combinatorial criteria but are actually complete in the computational setting.
We initiate the fully computational study of these fundamental questions. Somewhat surprisingly, we manage to provide an almost full characterization of the complete functions in this model as well. More precisely, we present a computational criterion (called computa tional row non-transitivity ) for a function f to be complete for the asymmetric case. Furthermore, we show a matching criterion called {\em computational row transiti vity} for f to have a simple SFE (based on no additional assumptions). This criterion is close to the negation of the computational row non-transitivity and thus we essentially characterize all ``nice" functions as either complete or having SFE unconditionally.
Postscript
,
gzipped Postscript.
Related On-Line
Papers: