Efficient perfectly secure message transmission in synchronous networks

Document Type



We study perfectly secure message transmission (SMT) in general synchronous networks where processors and communication lines may be Byzantine faulty. Dolevet al.(J. Assoc. Comput. Mach.40, No. 1, 17–47, Jan. 1993) first posed and solved the problem; our work significantly improves on their algorithms in the number of communication bits and the amount of local computation. Hence, our algorithms are better suited for 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 worst case time that is linear in the diameter of the 1?network. Our algorithms assume that the containment assumption holds, i.e., there is effectively 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-waySMT, Sender can send information to Receiver via the wires that connect them, but Receiver cannot send information to Sender. In 2-waySMT, Sender and Receiver can send information to each other via the wires. Aphaseis a send from Sender to Receiver or vice versa. First, we develop a 3-phase algorithm for 2-way SMT. Next, we present a 2-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 communication bits than the first algorithm. Both the 2?phase and 3-phase algorithms employ new techniques to detect faulty paths. We also present a simple algorithm for 1-way SMT.


Computer Engineering | Electrical and Computer Engineering | Engineering


Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.