A Simple and Effciently Verifiable Characterization of the Possibility of Information-Theoretic Key Agreement
The model of information-theoretic secret-key agreement from joint randomness by public discussion was recently extended to the case where the insecure communication is not even authentic. It has been shown that the ability of generating a virtually-secret key is then directly linked to a certain "simulatability" condition formulated in terms of the involved random variables. More generally, this condition is important in the context of identification and authentication among parties sharing some correlated but not necessarily identical partially-secret keys. Unfortunately, the simulatability condition is a priori not very useful since it is not even clear whether it is verifiable in finite time. We introduce a new intuitive formalism, based on a mechanical model for representing the involved quantities, for dealing with discrete joint distributions of random variables and their manipulations by noisy channels, and s how that this representation leads to a simple and efficient characterization of the possibility of secret-key agreement against active adversaries in many cases. The formalism is useful also for solving different problems related to discrete distributions and channels, e.g., to give criteria for the possibility and impossibility of secret-key agreement in the presence of passive opponents.