Coded Cooperative Data Exchange for a Secret Key
This addresses secure key generation in networks, but it is incremental as it builds on known cooperative data exchange problems.
The paper tackles the problem of generating a secret key via coded cooperative data exchange, proving that minimizing linear transmissions for this is NP-hard, unlike the polynomial-time solvable traditional version, and shows linear codes can be suboptimal.
We consider a coded cooperative data exchange problem with the goal of generating a secret key. Specifically, we investigate the number of public transmissions required for a set of clients to agree on a secret key with probability one, subject to the constraint that it remains private from an eavesdropper. Although the problems are closely related, we prove that secret key generation with fewest number of linear transmissions is NP-hard, while it is known that the analogous problem in traditional cooperative data exchange can be solved in polynomial time. In doing this, we completely characterize the best possible performance of linear coding schemes, and also prove that linear codes can be strictly suboptimal. Finally, we extend the single-key results to characterize the minimum number of public transmissions required to generate a desired integer number of statistically independent secret keys.