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.

Metadata
Available format(s)
-- withdrawn --
Publication info
Published elsewhere. No
Keywords
simulation paradigmsecure multi-party computation
Contact author(s)
shailesh vaya @ gmail com
vaya @ cse iitm ernet in
History
2009-06-23: withdrawn
2007-09-05: received
See all versions
Short URL
https://ia.cr/2007/346
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.