Talk Prof. Navin Kashyap, IT-SOC Distinguished Lecturer: “The Communication Complexity of Secret Key Generation”
Title
- "The Communication Complexity of Secret Key Generation"
Abstract
- We consider the problem of secret key generation within the multiterminal source model of Csiszar and Narayan. In this model, there are a finite number, m, of terminals, the i-th terminal having access to i.i.d. realizations of a discrete random variable Xi. The joint distribution of (X1,...,Xm) is known to everyone. The terminals communicate over a noiseless public channel, using which they must agree upon a secret key that is essentially independent of the public communication. The secret key capacity, defined to be the largest rate of a secret key that can be generated by the m terminals, was determined by Csiszar and Narayan in 2004.
In this talk, we examine the secret key generation problem from the angle of its communication complexity, which we define to be the minimum sum rate of communication required to generate a secret key of a given rate. Equivalently, we address the question of what is the largest rate of a secret key that can be generated using a communication of total rate R. We provide an overview of what we know so far about this problem. In particular, we provide a complete and precise answer for the important special case of the pairwise independent network (PIN) model.
This is joint work with Chung Chan, Manuj Mukherjee and Qiaoqiao Zhou.