Efficient 1-Round Almost-Perfect Secure Message Transmission Protocols with Flexible Connectivity

In the Secure Message Transmission (SMT) problem, a sender \(\mathcal{S}\) wants to send a message m to a receiver \(\mathcal{R}\) in a private and reliable way. \(\mathcal{S}\) and \(\mathcal{R}\) are connected by nwires, t of which controlled by the adversary. The n wires represent n node disjoint communication paths between the sender and the receiver. The adversary is assumed to have unlimited computational power. An Almost Perfectly Secure Message Transmission (APSMT, for short) provides perfect privacy for the transmitted message, and the probability that the received message is different from the sent one is bounded by δ and, δ = 0 corresponds to perfect SMT. It has been shown that APSMT is possible if n ≥ 2t + 1 and for 1-round perfect SMT, n ≥ 3t + 1. SMT protocols and techniques have found applications in practice, including key distribution and key strengthening in wireless sensor networks. In this paper we show two general methods of constructing 1-round APSMT protocols for different levels of network connectivity. We consider two cases: \(n = (2 + c)t,c > \frac{1} {t}\) where a fraction of wires are corrupted, and \(n = 2t + k,k \geq 1\) where a constant number of extra wires (over the required minimum) exists. The proposed methods use the whole, or part of, the previously constructed protocols to construct new protocols with flexible connectivity, whose privacy, reliability and efficiency can be derived from the component parts. The new protocols are efficient and in some cases have optimal transmission rates. The flexibility that is provided by these constructions facilitate application of APSMT in practical applications.