Sufficiently myopic adversaries are blind
Sufficiently myopic adversaries are blind
复制标题
足够近视的对手都是盲目的
DOI：
10.1109/isit.2015.7282638
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
M. Langberg
中科院分区：
文献类型：
--
作者：
B. Dey;S. Jaggi;M. Langberg
在这项工作中，我们考虑这样的通信设置，其中发送者Alice希望通过由近视的敌对实体Calvin控制的信道与接收者Bob进行通信。粗略地说，对于块长度n，由Alice传输的码字Xn被Calvin破坏，Calvin必须基于他的对抗性决定，基于Xn的哪些字符来破坏以及如何破坏它们，而不是基于码字Xn的整个视图，而是基于通过噪声无记忆通道的Xn的图像。更具体地说，我们的沟通模式可以通过两个渠道来描述。从Alice到Calvin的无记忆信道p(z|x)，以及由Calvin确定的状态Sn控制的从Alice到Bob的任意变化的信道p(y|x，S)。在标准对抗性信道中，状态Sn可能取决于码字Xn，然而在我们的设置中，Sn仅取决于Calvin的观点Zn。近视通道捕捉了广泛的通道，以及无记忆和对抗性(零错误)通道的标准模型之间的桥梁。在这项工作中，我们给出了近视通道容量的上下限。对于一些感兴趣的特殊情况，我们表明我们的界是紧的。我们将我们的结果推广到安全通信的设置中，在安全通信中，我们要求传输的消息对Calvin保密。例如，我们证明了如果(I)Calvin至多可以翻转Alice和Bob之间传送的比特的p个分数，并且(Ii)Calvin通过具有参数q的二进制对称信道来观看Xn，那么一旦Calvin是“足够近视的”(在这种情况下，当Q>；p时)，那么最优通信速率是“盲”的对手(即，根本看不到Xn的对手)的通信速率，这对于标准通信是1-H(P)，对于安全通信是H(Q)-H(P)。我们的一般交流模式也存在类似的现象。
In this work we consider the communication setting in which a sender, Alice, wishes to communicate with a receiver, Bob, over a channel controlled by an adversarial entity, Calvin, who is myopic. Roughly speaking, for blocklength n, the codeword Xn transmitted by Alice is corrupted by Calvin who must base his adversarial decisions, on which characters of Xn to corrupt and how to corrupt them, not on the entire view of the codeword Xn but on Zn, the image of Xn through a noisy memoryless channel. More specifically, our communication model may be described by two channels. A memoryless channel p(z|x) from Alice to Calvin, and an arbitrarily varying channel from Alice to Bob, p(y|x, s) governed by a states Sn determined by Calvin. In standard adversarial channels, the states Sn may depend on the codeword Xn, however in our setting Sn depends only on Calvin's view Zn. The myopic channel captures a broad range of channels and bridges between the standard models of memoryless and adversarial (zero error) channels. In this work we present upper and lower bounds on the capacity of myopic channels. For a number of special cases of interest we show that our bounds are tight. We extend our results to the setting of secure communication in which we require that the transmitted message remain secret from Calvin. For example, we show that if (i) Calvin may flip at most a p fraction of the bits communicated between Alice and Bob, and (ii) Calvin views Xn through a binary symmetric channel with parameter q, then once Calvin is “sufficiently myopic” (in this case, when q > p), then the optimal communication rate is that of an adversary who is “blind” (that is, an adversary that does not see Xn at all), which is 1-H(p) for standard communication, and H(q)-H(p) for secure communication. A similar phenomena exists for our general model of communication.