Date Added: May 2011
The authors initiate the study of secure Multi-Party Computation (MPC) in a server-aided setting, where the parties have access to a single server that does not have any input to the computation; does not receive any output from the computation; but has a vast (but bounded) amount of computational resources. In this setting, they are concerned with designing protocols that minimize the computation of the parties at the expense of the server. They develop new definitions of security for this server-aided setting that generalize the standard simulation-based definitions for MPC, and allow one to formally capture the existence of dishonest but non-colluding participants. This requires one to introduce a formal characterization of non-colluding adversaries that may be of independent interest.