Almost-Everywhere Secure Computation with Edge Corruptions
The authors consider secure Multi-Party Computation (MPC) in a setting where the adversary can separately corrupt not only the parties (nodes) but also the communication channels (edges), and can furthermore choose selectively and adaptively which edges or nodes to corrupt. Note that if an adversary corrupts an edge, even if the two nodes that share that edge are honest, the adversary can control the link and thus deliver wrong messages to both players. They consider this question in the information-theoretic setting, and require security against a computationally unbounded adversary. In a fully connected network the above question is simple (and they also provide an answer that is optimal up to a constant factor). What makes the problem more challenging is to consider the case of sparse networks.