Paper 2007/346

Secure multi-party computation on incomplete networks

Shailesh Vaya

Abstract

Secure multiparty computation of a multivariate function is a central problem in cryptography. It is known that secure multiparty computation can be realized by a set of $n$ parties iff the connectivity of the underlying (authenticated) communication network is more than twice the number of corrupted parties. This impossibility result makes secure multiparty computation far less applicable in practice, as most deployed networks have a much lower degree than $O(n)$ and one would ideally like to tolerate $\theta (n)$ corrupted parties. This work considers a model for (unconditional) secure multiparty computation for networks of low degrees in which authenticated channels are available between very few pairs of parties. Not all honest parties can achieve traditional security guarantees of multiparty computation for this setting. This formulation of secure multiparty computation, which permits some of the honest parties to be "sacrificed" is called almost everywhere secure computation. In this work we show how to realize a.e.s.c., on a few special families of incomplete networks, for the case of Byzantine corruptions.

Note: (1) Simplified proof of security with easier to understand structure. (2) More elaborate explaination of the definition of security and how input indistinguishablity type definition is implied by it. (3) Elaborate comparison.