The Effort to Agree: Information-theoretic Limits and Practical Discussion Schemes

Project: Research

View graph of relations

Description

In a network in which users may have different private knowledge, how much can they agree on after some discussion? It is intuitive that more discussion generally leads to greater consensus. However, finding the precise cost-benefit trade-off between the amount of discussion and agreement is non-trivial yet essential for developing effective network communication schemes. This project considers the secret key agreement problem, where users have public discussions to generate a common secret key. The objective is to characterize the maximum amount of secret key that the users can share after a limited amount of discussion, and to develop effective discussion schemes that can approach the theoretical limit. The secret key can then be used to support provably secure communication among the users.The optimal trade-off between key rate and discussion rate is unknown, even for the two-user case. Nevertheless, with appropriate simplifications, the PI and others have made substantial progress in the more pragmatic case involving multiple users. The idea is to consider different tractable models of practical interest, derive computable bounds and optimality conditions for different discussion strategies, and identify the limitations and potential improvements with conjectures and concrete examples that can possibly be solved with the help of an automatic information inequality prover. By continuing this approach, this project is expected to generate successively more challenging and general subproblems that inspire new models, proof techniques, and discussion schemes.Partial solutions also exist that suggest interesting connections to machine learning problems. For instance, with no restrictions on the amount of public discussion, the maximum key rate can be regarded as a multivariate extension of Shannon’s mutual information: a quantity measuring the amount of mutual information in the private knowledge of the users. This has recently inspired a new framework for clustering features according to their mutual information. Additionally, with limited public discussion, the problem is related to the information-bottleneck method for feature extraction. Recently, such an information-theoretic approach has been applied to deep learning studies with promising results. Deep learning has also been used to automatically construct information-theoretically secure communication schemes. This project will elucidate such connections using the information-bottleneck method and deep learning to solve the secret key agreement problem. The network information theory developed under the secret key agreement problem will also help understand and improve machine learning techniques.

Detail(s)

Project number9048120
Grant typeECS
StatusFinished
Effective start/end date1/12/188/05/23