Secure communication in multicast channels: The answer to Franklin and Wright's question

Problems of secure communication and computation have been studied extensiv ely in network models. Goldreich ei al., Franklin and Yung, and Franklin an d Wright have initiated the study of secure communication and secure comput ation in multirecipient (multicast) models. A "multicast channel" (such as ethernet) enables one processor to send the same message-simultaneously and privately-to a fixed subset of processors. In their recent paper, Franklin and Wright have shown that if there are n multicast lines between a sender and a receiver and there are at most t malicious (Byzantine style) process ors, then the condition n > I is necessary and sufficient for achieving eff icient probabilistically reliable and probabilistically private communicati on. They also showed that if n > [3t/2],then there is an efficient protocol to achieve probabilistically reliable and perfectly private communication. They left open the question whether there exists an efficient protocol to achieve probabilistically reliable and perfectly private communication when [3r/2] greater than or equal to n > t. In this paper, by using a different authentication scheme, we answer this question affirmatively and study rel ated problems.