An Operational Characterization of Mutual Information in Algorithmic Information Theory
An Operational Characterization of Mutual Information in Algorithmic Information Theory
复制标题
DOI：
10.1145/3356867
复制
发表时间：
2019-09-01
影响因子：
2.5
通讯作者：
Zimand, Marius
中科院分区：
文献类型：
--
作者：
Romashchenko, Andrei;Zimand, Marius
我们证明了任意串x和y的互信息在Kolmogorov复杂度意义下等于最长共享密钥的长度，直到对数精度。双方--一方具有x和这对串的复杂性分布，另一方具有y和y和这对串的复杂性分布--可以通过在公共信道上交互的概率协议来建立。对于L和2，可以由L各方从字符串元组(x(1)，...，x(L))建立的最长共享秘密等于元组的复杂性减去将元组分发给各方所需的最小通信量，直到对数精度为止。我们证明了密钥协商协议的通信复杂性，该协议为具有公开随机性的协议产生最大长度的密钥。我们还证明了，如果通信复杂度降到所建立的门限以下，则只能获得非常短的密钥。
We show that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings x and y is equal, up to logarithmic precision, to the length of the longest shared secret key that two parties-one having x and the complexity profile of the pair and the other one having y and the complexity profile of the pair-can establish via a probabilistic protocol with interaction on a public channel. For l > 2, the longest shared secret that can be established from a tuple of strings (x(1),..., x(l)) by l parties-each one having one component of the tuple and the complexity profile of the tuple-is equal, up to logarithmic precision, to the complexity of the tuple minus the minimum communication necessary for distributing the tuple to all parties. We establish the communication complexity of secret key agreement protocols that produce a secret key of maximal length for protocols with public randomness. We also show that if the communication complexity drops below the established threshold, then only very short secret keys can be obtained.