CIF: Small: Key Dissemination over Networks

The resource of shared randomness, i.e., shared keys, plays a fundamental role in the theory and practice of network communication systems. A uniformly distributed key, shared among some network users and, at times, hidden from others, appears as a central resource in a variety of communication tasks such as secure communication, private communication, distributed computing, statistical inference, distributed learning, and more. Given the central role of shared randomness in applications critical to modern technology, there is significant importance in the design of efficient high-rate communication schemes that support key dissemination over networks. Traditional schemes for key distribution treat keys as source-generated messages and as such do not necessarily benefit from certain flexibilities that are inherent to the task of key dissemination. This project takes up the challenge of developing communication schemes tailor-made to fit the task of key dissemination, and as such the project suggests novel technology expected to impact the distribution of shared randomness in resource-constrained network systems. Traditional studies of communication, which address the transfer of messages from their source of generation to their intended destination, may be used to (securely) establish shared keys. However, such a methodology is suboptimal in the context of shared random keys, since distributing keys requires only the distribution of shared randomness; distributing keys does not require the reconstruction of source information. Removing the requirement of source reconstruction grants a flexibility to the communication process which gives rise to the potential of increased key-rates when compared to traditional forms of communication that require source reconstruction. This project initiates the study of key dissemination in the context of complex multi-source multi-terminal networks through the methodology of network coding, and seeks a comprehensive theory for both noiseless and noisy network topologies. By foregoing the traditional communication requirement to reconstruct sources and focusing instead only on reconstructing common randomness, the research is expected to yield efficient, high-rate communication strategies, that outperform traditional schemes, thereby advancing the area of key dissemination. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.