Approximation Hardness and Secure Communication in Broadcast Channels

Problems of secure communication and computation have been studied extensively in network models. Goldreich, Goldwasser, and Linial, Franklin and Yung, and Franklin and Wright have initiated the study of secure communication and secure computation in multi-recipient (broadcast) models. A “broadcast channel” (such as Ethernet) enables one processor to send the same message–simultaneously and privately–to a fixed subset of processors. Franklin and Wright, and Wang and Desmedt have shown that if there are at most k malicious (Byzantine style) processors, then there is an efficient protocol for achieving probabilisticly reliable and perfectly private communication in a strongly n-connected network where n≥ k+1. While these results are unconditional, we will consider these problems in the scenario of conditional reliability, and then improve the bounds. In this paper, using the results for hardness of approximation and optimization problems, we will design communication protocols (with broadcast channels) which could defeat more faults than possible with the state of the art. Specifically, assuming certain approximation hardness result, we will construct strongly n-connected graphs which could defeat a k-active adversary (whose computation power is polynomially bounded) for k=cn, where c>1 is any given constant. This result improves a great deal on the results of Franklin and Wright, and Wang and Desmedt.