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

The article is devoted to the problem of secure communication in multicast channels with malicious (Byzantine) processors. A multicast channel (like an ethernet bus or a token ring) enables one participant to send a message simultaneously and privately to a fixed subset of participants so that other participants learn nothing about the content of the message. A Byzantine adversary has unlimited computational power and can control some processors (messages sent by the processors). In the first two sections, the authors present the problem and the model they use in the article. They consider a graph representation of networks containing \(n\) paths with disjoint neighborhoods and \(t\) Byzantine nodes. The third section shortly reviews some relevant results in the reliable communication over neighbor networks. The main results are presented in the last two sections. In the fourth one, the authors survey Franklin and Wright's results in the subject under discussion and then address their open problem from [\textit{M. Franklin} and \textit{R. N. Wright}, J. Cryptology 13, 9-30 (2000; Zbl 0957.68042)]; namely, if it is possible to achieve perfect privacy when \(t < n \leq \lfloor 3t/2 \rfloor\). They introduce the perfectly private transmission protocol and show under which condition it is efficient, reliable and perfect private. In the last section the applicability of multicast line protocols to general multicast graphs is studied and shown that it is NP-complete to decide whether a multicast graph has \(n\) paths with disjoint neighborhoods.