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 δ 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 M-QAM modulation for both the theoretical capacity as well as the practical capacity with LDPC codes with the proposed thresholded LLR method.