Causal Adversarial Channels With Feedback Snooping

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 fractionpof 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., ifx=(x₁,x₂,…, xₙ)andy=(y₁,y₂,…, yₙ)denote the transmitted and the received codewords respectively, at each timek, he knows(x₁,x₂,…, xₖ)and(y₁,y₂,…, yₖ₋₁). 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 ofpandqfor (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, whenpis below a certain threshold (that depends onq), the adversary is no worse than an i.i.d. memory-less noise source.