Perfectly secure message transmission in asynchronous networks

We study the problem of perfectly secure communication in general asynchronous networks where processors and communication lines may be Byzantine faulty. To our knowledge, this is the first work that solves the secure message transmission (SMT) problem on asynchronous networks. The algorithms we develop do not rely on any complexity theoretic assumptions and simultaneously achieve the goals of perfect secrecy and perfect resiliency. Consider a network where there are n node-disjoint wires between sender and receiver, a disrupter that has access to ρ wires and attempts to maliciously alter communication between sender and receiver, and a listener that has access to ρ wires and attempts to decipher secret messages that sender sends to receiver. Let τ be max {ρp,σ,}. First, we develop an algorithm that can run on asynchronous networks with n⩾τ+p+1. The algorithm is for 1-way SMT, where information flows only from the sender to receiver. Next, we develop an asynchronous algorithm for the 2-way SMT, where sender and receiver “converse”