Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-060 | 7th September 2003 00:00

Completeness in Two-Party Secure Computation - A Computational View


Authors: Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen
Publication: 8th September 2003 09:40
Downloads: 1411


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 protocols unconditionally and whether there are functions that are neither complete nor have efficient SFE protocols.

The 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 as having
SFE unconditionally 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
computational row non-transitivity} for a function f to be complete for the asymmetric case.
Furthermore, we show a matching criterion called em computational row transitivity 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.

ISSN 1433-8092 | Imprint