In this paper, we show how to circumvent this impossibility result and achieve meaningful security guarantees for graphs with small degree (such as expander graphs and several other topologies). In fact, the notion we introduce, which we call {\em almost-everywhere MPC}, building on the notion of almost-everywhere agreement due to Dwork, Peleg, Pippenger and Upfal, allows the degree of the network to be much smaller than the total number of allowed corruptions. In essence, our definition allows the adversary to {\em implicitly} wiretap some of the good nodes by corrupting sufficiently many nodes in the ``neighborhood'' of those nodes. We show protocols that satisfy our new definition, retaining both correctness and privacy for most nodes despite small connectivity, no matter how the adversary chooses his corruptions.
Instrumental in our constructions is a new model and protocol for the {\em secure message transmission} (SMT) problem, which we call {\em SMT by public discussion}, and which we use for the establishment of pairwise secure channels in limited connectivity networks.
Category / Keywords: cryptographic protocols / Secure multi-party computation, almost-everywhere agreement, secure message transmission, expander graphs, bounded-degree networks. Date: received 10 Oct 2007 Contact author: garay at research bell-labs com Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20071014:182632 (All versions of this report) Short URL: ia.cr/2007/394 Discussion forum: Show discussion | Start new discussion