caa a22 4500 606148868 CHVBK 20210128100531.0 cr unu---uuuuu 210128e20151001xx s 000 0 eng 10.1007/s00145-013-9176-3 doi (NATIONALLICENCE)springer-10.1007/s00145-013-9176-3 Almost-Everywhere Secure Computation with Edge Corruptions [Elektronische Daten] [Nishanth Chandran, Juan Garay, Rafail Ostrovsky] We 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. 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) 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 among 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 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 constant fraction of the edges can be corrupted (i.e., the maximum that can be tolerated) and the degree of the network is sublinear. We make progress on this front, by constructing graphs of degree O(n ϵ ) (for arbitrary constant 0<ϵ<1) on which we can run a.e. secure computation protocols tolerating a constant fraction of adversarial edges. The number of given-up nodes in our construction is μn (for some constant 0<μ<1 that depends on the fraction of corrupted edges), which is also asymptotically optimal. International Association for Cryptologic Research, 2013 Almost-everywhere secure computation nationallicence bounded-degree network nationallicence Securemessage transmission nationallicence Byzantine agreement nationallicence Chandran Nishanth Microsoft Research, 9, Lavelle Road, Bangalore, India aut Garay Juan Yahoo Labs, 701 First Avenue, Sunnyvale, CA, USA aut Ostrovsky Rafail Department of Computer Science and Department of Mathematics, UCLA, 3732D Boelter Hall, Los Angeles, CA, USA aut Journal of Cryptology Springer US; http://www.springer-ny.com 28/4(2015-10-01), 745-768 0933-2790 28:4<745 2015 28 145 https://doi.org/10.1007/s00145-013-9176-3 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s00145-013-9176-3 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Chandran Nishanth Microsoft Research, 9, Lavelle Road, Bangalore, India aut NATIONALLICENCE 700 1- Garay Juan Yahoo Labs, 701 First Avenue, Sunnyvale, CA, USA aut NATIONALLICENCE 700 1- Ostrovsky Rafail Department of Computer Science and Department of Mathematics, UCLA, 3732D Boelter Hall, Los Angeles, CA, USA aut NATIONALLICENCE 773 0- Journal of Cryptology Springer US; http://www.springer-ny.com 28/4(2015-10-01), 745-768 0933-2790 28:4<745 2015 28 145