EFFICIENT PERFECTLY SECURE MESSAGE TRANSMISSION IN SYNCHRONOUS NETWORKS

We study perfectly secure message transmission (SMT) in general synchr onous networks where processors and communication lines may be Byzanti ne faulty. Dolev at al. (J. Assoc. Comput, Mach. 40, No. 1, 17-47, Jan , 1993) first posed and solved the problem; our work significantly imp roves on their algorithms in the number of communication bits and the amount of local computation. Hence, our algorithms are better suited f or traditional and fiber-optic networks than previous algorithms while requiring the same amount of connectivity, The algorithms we develop do not rely on any complexity theoretic assumptions and simultaneously achieve the three goals of perfect secrecy, perfect resiliency, and w orst case time that is linear in the diameter of the network. Our algo rithms assume that the containment assumption holds, i.e., there is ef fectively one adversary who controls and coordinates the activities of the faulty processors and lines. In SMT, a processor (Sender) wishes to transmit a secret message to another processor (Receiver) in such a way as to satisfy secrecy and resiliency requirements simultaneously, In 1-way SMT, Sender can send information to Receiver via the wires t hat connect them, but Receiver cannot send information to Sender. In 2 -way SMT, Sender and Receiver can send information to each other via t he wires. A phase is a send from Sender to Receiver or Vice versa. Fir st, we develop a 3-phase algorithm for 2-way SMT. Next, we present a L -phase algorithm for 2-way SMT. To our knowledge, this is the first 2- phase algorithm for SMT that uses communication and computation costs that are polynomial in the number of wires that connect the sender and the receiver. The second algorithm uses less time and more communicat ion bits than the first algorithm. Both the 2-phase and 3-phase algori thms employ new techniques to detect faulty paths. We also present a s imple algorithm for 1-way SMT. (C) 1996 Academic Pleas, Inc.