Paper 2012/221
AlmostEverywhere Secure Computation with Edge Corruptions
Nishanth Chandran, Juan Garay, and Rafail Ostrovsky
Abstract
We consider secure multiparty 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 informationtheoretic 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 nodecorruption 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{almosteverywhere 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 nodesi.e., to ``corrupt'' edges in the network. While it is easy to see that an a.e. secure computation protocol for the original nodecorruption 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 polynomialtime 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 sublinear. We make progress on this front, by constructing graphs of degree $O(n^\epsilon)$ (for arbitrary constant $0<\epsilon<1$) on which we can run a.e. secure computation protocols tolerating a constant fraction of adversarial edges. The number of givenup nodes in our construction is $\mu n$ (for some constant $0<\mu<1$ that depends on the fraction of corrupted edges), which is also asymptotically optimal.
Note: Added grant information and reorganized the paper slightly.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. A version of this paper, entitled ``Edge Fault Tolerance on Sparse Networks,'' will appear in the proceedings of ICALP 2012; this is the full version of that paper with a more cryptographically oriented treatment.
 Keywords
 secure computationboundeddegree networksedge corruptions
 Contact author(s)
 nish @ microsoft com
 History
 20120423: last of 2 revisions
 20120422: received
 See all versions
 Short URL
 https://ia.cr/2012/221
 License

CC BY
BibTeX
@misc{cryptoeprint:2012/221, author = {Nishanth Chandran and Juan Garay and Rafail Ostrovsky}, title = {AlmostEverywhere Secure Computation with Edge Corruptions}, howpublished = {Cryptology ePrint Archive, Paper 2012/221}, year = {2012}, note = {\url{https://eprint.iacr.org/2012/221}}, url = {https://eprint.iacr.org/2012/221} }