AlmostEverywhere Secure Computation with Edge Corruptions
Academic Article

 Overview

 Identity

 Additional Document Info

 Other

 View All

Overview
abstract

© 2013, International Association for Cryptologic Research. 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) 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 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 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 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 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 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 givenup nodes in our construction is μn (for some constant 0<μ<1 that depends on the fraction of corrupted edges), which is also asymptotically optimal.
published proceedings
author list (cited authors)

Chandran, N., Garay, J. A., & Ostrovsky, R
citation count
complete list of authors

Chandran, NishanthGaray, Juan AOstrovsky, Rafail
publication date
publisher
published in
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue
Other
userdefined tag

16 Peace, Justice and Strong Institutions