Abstract:
With the advent of 5G and technologies such as cloud computing, Internet-of-Things (IoT), etc, future communication networks will consist of a large number of heterogeneous devices connected together. A critical aspect will be ensuring that communication is not only fast and reliable, but also resilient to malicious attack. As networks increasingly adopt zero-trust principles in their security frameworks, it is important to consider such attacks from a zero-trust perspective. Motivated by this, we consider the problem of communicating a message reliably across a binary erasure channel (BEC( $q$ )) or a binary symmetric channel (BSC( $q$ )) against an adversary actively injecting additional erasures or flips at the channel’s input. The adversary can corrupt up to a fraction $p$ of the transmitted bits and knows the transmission scheme agreed upon by the communicating terminals. Further, he has the capability to causally snoop in on both the transmitter and the receiver in real time, i.e., if ${\mathbf {x}}=(x_{1},x_{2},\ldots, x_{n})$ and ${\mathbf {y}}=(y_{1},y_{2},\ldots, y_{n})$ denote the transmitted and the received codewords respectively, at each time $k$ , he knows $(x_{1},x_{2},\ldots, x_{k})$ and $(y_{1},y_{2},\ldots, y_{k-1})$ . Using his side-information, the adversary is free to employ any attack that respects his constraint on the number of corruptible bits. We prove an information-theoretic tight capacity characterization as a function of $p$ and $q$ for (i) the erasure adversary with a BEC( $q$ ) and (ii) the bit-flip adversary with a BSC( $q$ ). A unique feature of our models is the compounding of stochastic and adversarial noise sources. Our analysis reveals the worst-case adversarial attacks for both models and proves the existence of coding schemes that achieve rates equal to the capacity for any adversarial attack. In the case of bit-flips, we show that, interestingly, when $p$ is below a certain threshold (that depends on $q$ ), the adversary is no worse than an i.i.d. memory-less noise source.
Published in: IEEE Journal on Selected Areas in Information Theory ( Volume: 3, Issue: 1, March 2022)
