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.

Perfectly secure message transmission, secure network coding
IEEE Transactions on Information Theory
Centrum Wiskunde & Informatica, Amsterdam, The Netherlands

Spini, G, & Zémor, G. (2020). Efficient Protocols for Perfectly Secure Message Transmission with Applications to Secure Network Coding. IEEE Transactions on Information Theory, 66(10), 6340–6353. doi:10.1109/TIT.2020.2994285