Sexure Communication in Minimal Connectivity Models

摘要

Proboems of secure communication and computation have been studied extensively in network model. In this work we ask what is possible in the information- theoretic setting when the adversary is very strong (Byzantine) and the network connec- tivity is very low (minimum needed for crash-tolerance). We concentrate on a new model called "multicast lines," and show a sizable gap between the connectivity required for perfect security and for almost perfect security. Our results also have implications to the commonly studied simple channel model and to general secure multiparty computation.