Cryptology ePrint Archive: Report 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.

Category / Keywords: simulation paradigm, secure multi-party computation

Publication Info: No

Date: received 4 Sep 2007, last revised 1 Mar 2009, withdrawn 23 Jun 2009

Contact author: shailesh vaya at gmail com, vaya@cse iitm ernet in

Available formats: (-- withdrawn --)

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.

Version: 20090623:104035 (All versions of this report)

Discussion forum: Show discussion | Start new discussion