We consider secure multi-party computation (MPC) in a setting wherethe 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. We 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 we

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.

Partially connected networks are far more realistic than fully

connected networks, which led Garay and Ostrovsky [Eurocrypt\'08] to

formulate the notion of (unconditional) \\emph{almost everywhere (a.e.)

secure computation} in the node-corruption model, i.e., a model in

which not all pairs of nodes are connected by secure channels and the

adversary can corrupt some of the nodes (but not the edges). In such a setting,

MPC amongst all honest nodes cannot be guaranteed due

to the possible poor connectivity of some honest nodes with other

honest nodes, and hence some of

them must be ``given up\'\' and left out of the

computation. The number of such nodes is a function of the underlying

communication graph and the adversarial set of nodes.

In this work we introduce the notion of \\emph{almost-everywhere secure

computation with edge corruptions}, which is exactly the same problem as

described above, except that we additionally allow the adversary to

completely control some of the communication channels between two

correct nodes---i.e., to ``corrupt\'\' edges in the network. While it is

easy to see that an a.e. secure computation protocol for the original

node-corruption model is also an a.e. secure computation protocol tolerating

edge corruptions (albeit for a reduced fraction of edge corruptions

with respect to the bound for node corruptions), no polynomial-time

protocol is known in the case where a {\\bf constant fraction} of the edges can be corrupted (i.e., the maximum that can be tolerated)

and the degree of the network is sub-linear.

We make progress on this front, by constructing graphs of degree

$O(n^\\epsilon)$ (for arbitrary constant $0