论文标题
具有计算界观测的对手的渠道容量
Channel Capacity for Adversaries with Computationally Bounded Observations
论文作者
论文摘要
我们研究可靠的通信通过点对点对抗通道，在这些通道中，对手可以通过某些功能观察传输的代码字，该功能将$ n $ bit代码字作为输入，并计算某些给定的$ r \ in [0,1] $的$ rn $ bitt $。我们考虑$ rn $ -it观察到计算有限的方案 - 只要可以使用多项式计算资源来计算该函数，就可以自由选择任意观察功能。这种基于观察的限制与基于传统信道的计算局限性不同，在后来的情况下，资源限制适用于（对抗）通道误差的计算。对于[0,1-H（p）] $中的所有$ r \，其中$ h（\ cdot）$是二进制熵函数，而$ p $是对手的错误预算，我们表征了上述渠道的容量。对于$ r $的此范围，我们发现容量与完全明显的设置相同（$ r = 0 $）。该结果可以看作是对具有主动窃听器的近视对手和通道的已知结果的概括，观察过程分别取决于固定分布和固定线性结构，而对手不能由对手任意选择。
We study reliable communication over point-to-point adversarial channels in which the adversary can observe the transmitted codeword via some function that takes the $n$-bit codeword as input and computes an $rn$-bit output for some given $r \in [0,1]$. 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 (adversarial) channel error. For all $r \in [0,1-H(p)]$ where $H(\cdot)$ is the binary entropy function and $p$ is the adversary's error budget, 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.
