|
joint work with Seny Kamara, Payman Mohassel |
|
Results: We initiate the study of secure multi-party computation (MPC) in a server-aided setting, where the parties have access to a single server that (1) does not have any input to the computation; (2) does not receive any output from the computation; but (3) has a vast (but bounded) amount of computational resources. In this setting, we are concerned with designing protocols that minimize the computation of the parties at the expense of the server. We develop new definitions of security for this server-aided setting, that generalize the standard simulation-based definitions for MPC, and allow us to formally capture the existence of dishonest but non-colluding participants. This requires us to introduce a formal characterization of non-colluding adversaries that may be of independent interest. We then design general-purpose server-aided multi-party protocols that are more efficient (in terms of computation and communication) for the parties than the alternative of running a standard MPC protocol (i.e., without the server). We give a general transformation from any secure delegated computation scheme to a server-aided two-party protocol. Our transformation formalizes the intuitive connection between the problems of server-aided computation and verifiable computation by interpreting the former as a means for verifiably and privately outsourcing a secure multi-party computation protocol to an untrusted worker. Finally, we construct a specialized protocol in the server-aided setting for the problem of set intersection with improved efficiency. |
|
|
Resources: Outsourcing Multi-Party Computation Paper |
Motivation:
Most of the existing multiparty computation protocols
implicitly assume that the computation will be executed in a homogeneous
computing environment where all the participants play similar roles,
have the same amount of resources and, if corrupted,
all collude with each other.
In practice, however, computation does not always take place in such a setting.
In fact, it is often the case that distributed computations are carried out by a
diverse set of devices which could include high-performance servers,
large-scale clusters, personal computers and even weak mobile devices.
Furthermore, there are many instances in practice where collusion between
participants is unlikely to occur. This can happen either because it is not
feasible, is too costly, or because it is prevented by other means, e.g., by
physical means, by the Law or due to conflicting interests.
An important example of such a heterogeneous environment - and the main
motivation for our work - is cloud computing, where a computationally powerful
service provider offers (possibly weaker) clients access to its resources ``as a
service".