CryptoDB
Secure computation on incomplete networks
| Authors: | |
|---|---|
| Download: | |
| 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 ideally one would like to tolerate $\theta(n)$ corrupted parties. This work proposes a new model for secure multiparty computation for settings where authenticated channels are not assumed to be available between every pair of parties, and infact may be available between very few pairs of parties (i.e., networks of low degrees). For such settings, it is clear that not all honest parties can achieve traditional security guarantees of MPC. Such honest parties which neither receive their correct outputs, nor maintain the privacy of their inputs are called {\it sacrificed} parties. The new formulation of MPC, which allows some honest parties to be "sacrificed", in the manner described above, is called almost everywhere secure computation. We show how to adapt standard protocols for unconditional secure MPC, that assume authentication channels between all pairs of parties, so that they can execute on incomplete networks, with special properties. Instrumental to our adaptation is a protocol for establishing secure channels between distant nodes of an incomplete network, using some infrastructure support from the incomplete network. The challange of designing such a multiparty protocol, can be abstracted as a two party secret key agreement problem using public broadcast channel. |
BibTeX
@misc{eprint-2007-13626,
title={Secure computation on incomplete networks},
booktitle={IACR Eprint archive},
keywords={secure multiparty computation},
url={http://eprint.iacr.org/2007/346},
note={Submitted to conference/under submission to journal vaya@cs.ucla.edu 13805 received 4 Sep 2007, last revised 19 Oct 2007},
author={Shailesh Vaya},
year=2007
}