Paper 2012/221
Almost-Everywhere Secure Computation with Edge Corruptions
Nishanth Chandran, Juan Garay, and Rafail Ostrovsky
Abstract
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) \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
Note: Added grant information and re-organized 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 computationbounded-degree networksedge corruptions
- Contact author(s)
- nish @ microsoft com
- History
- 2012-04-23: last of 2 revisions
- 2012-04-22: 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 = {Almost-Everywhere Secure Computation with Edge Corruptions}, howpublished = {Cryptology {ePrint} Archive, Paper 2012/221}, year = {2012}, url = {https://eprint.iacr.org/2012/221} }