Capacity of a Binary Channel with a Time-Bounded Adversary

This paper addresses the challenge of ensuring reliable communication over binary input memoryless channel under the influence of a time-bounded adversary. The adversary can arbitrarily overwrite a fraction <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\delta$</tex> of the received symbols. This model can be used for intermittent hardware errors or adversarial attacks in the receiver processing. The worst-case adversarial capacity is derived using infinite shared randomness to enable coordinated interleaving against the adversary. It is shown that the capacity can be achieved simply with a random interleaver along with a thresholded log-likelihood ratio (LLR) decoder, which can be readily implemented on top of most standard decoder architectures in use in practical systems today. We show that the worst-case adversary targets highly reliable bits to maximize disruption. Simulations are presented on AWGN channels with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$M$</tex>-QAM modulation for both the theoretical capacity as well as the practical capacity with LDPC codes with the proposed thresholded LLR method.