Channel Capacity for Adversaries with Computationally Bounded Observations

We study reliable communication over point-to-point adversarial channels in which the adversary can observe the codeword via some function that takes the $n$-bit codeword as input and computes an $rn$-bit output. We consider the scenario where the $rn$-bit observation is computationally bounded -- the adversary is free to choose an arbitrary observation function as long as the function can be computed using a polynomial amount of computational resources. This observation-based restriction differs from conventional channel-based computational limitations, where in the later case, the resource limitation applies to the computation of the channel error. For some number $r^* \in [0,1]$ and for $r \in [0,r^*]$, we characterize the capacity of the above channel. For this range of $r$, we find that the capacity is identical to the completely obvious setting ($r=0$). This result can be viewed as a generalization of known results on myopic adversaries and channels with active eavesdroppers for which the observation process depends on a fixed distribution and fixed-linear structure, respectively, that cannot be chosen arbitrarily by the adversary.