论文标题
算法信息理论中秘密关键协议的沟通复杂性
Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory
论文作者
论文摘要
众所周知，从Kolmogorov复杂性的意义上讲，任何一对字符串X和Y的相互信息都等于两方可以通过概率协议与公共通道上的交互作用建立的最长共享秘密密钥的长度，假设当事各方分别为他们的输入X和Y。我们为当事方可以使用私人随机位来源的设置确定了此问题最严重的通信复杂性。我们表明，对于某些X，即使当事方必须就秘密密钥达成共识，该密钥的大小比X和Y之间的相互信息小得多，秘密密钥协议的沟通复杂性也不会减少。另一方面，我们讨论了x，y的示例，以便协议的通信复杂性随派生的秘密键的大小而逐渐下降。主要结果的证明使用适当图的光谱特性和膨胀器混合引理以及信息理论技术。
It is known that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings x and y is equal to the length of the longest shared secret key that two parties can establish via a probabilistic protocol with interaction on a public channel, assuming that the parties hold as their inputs x and y respectively. We determine the worst-case communication complexity of this problem for the setting where the parties can use private sources of random bits. We show that for some x, y the communication complexity of the secret key agreement does not decrease even if the parties have to agree on a secret key whose size is much smaller than the mutual information between x and y. On the other hand, we discuss examples of x, y such that the communication complexity of the protocol declines gradually with the size of the derived secret key. The proof of the main result uses spectral properties of appropriate graphs and the expander mixing lemma, as well as information theoretic techniques.
