Efficient Protocols for Perfectly Secure Message Transmission with Applications to Secure Network Coding

In the model that has become known as 'Perfectly Secure Message Transmission' (PSMT), a sender Alice is connected to a receiver Bob through $n$ parallel two-way channels. A computationally unbounded adversary Eve controls $t$ of these channels, meaning she can acquire and alter any data that is transmitted over these channels. The sender Alice wishes to communicate a secret message to Bob privately and reliably, i.e. in such a way that Eve gains no information about the message while Bob is able to recover it completely. We focus on PSMT protocols that work in two transmission rounds for $n= 2t+1$. We break from previous work by following a conceptually simpler blueprint. This has two consequences: first, we obtain improved efficiency, namely, we reduce the previously best-known communication complexity, i.e. the number of transmitted bits necessary to communicate a 1-bit secret, from $\mathcal {O}(n^{3}\log n)$ to $\mathcal {O}(n^{2}\log n)$. Our solution also reaches optimal transmission rate for a secret of size $\mathcal {O}(n \log n)$ , thus answering the hitherto open question of attaining a threshold below $\mathcal {O}(n^{2} \log n)$ bits. Second, our construction can be adapted to more general scenarios relevant to Network Coding, where the adversary is given more power