2017/10/16 by Andrei Romashchenko, Romashchenko, Andrei, Marius Zimand +1 · 1 citation
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #Benford’s Law and Fraud Detection #Cryptography and Data Security
paper · pdf · doi:10.48550/arxiv.1710.05984
We show that the mutual information, in the sense of Kolmogorov complexity,\nof any pair of strings x and y is equal, up to logarithmic precision, to\nthe length of the longest shared secret key that two parties, one having x\nand the complexity profile of the pair and the other one having y and the\ncomplexity profile of the pair, can establish via a probabilistic protocol with\ninteraction on a public channel. For \ℓ > 2, the longest shared secret that\ncan be established from a tuple of strings (x1, \… , x_\ℓ) by \ℓ\nparties, each one having one component of the tuple and the complexity profile\nof the tuple, is equal, up to logarithmic precision, to the complexity of the\ntuple minus the minimum communication necessary for distributing the tuple to\nall parties. We establish the communication complexity of secret key agreement\nprotocols that produce a secret key of maximal length, for protocols with\npublic randomness. We also show that if the communication complexity drops\nbelow the established threshold, then only very short secret keys can be\nobtained.\n