On the Public Communication Needed to Achieve SK Capacity in the Multiterminal Source Model.

The focus of this paper is on the public communication required for generating a maximal-rate secret key (SK) within the multiterminal source model of Csiszár and Narayan. Building on the prior work of Tyagi for the two-terminal scenario, we derive a lower bound on the communication complexity, R \text {SK} , defined to be the minimum rate of public communication needed to generate a maximal-rate SK. It is well known that the minimum rate of communication for omniscience, denoted by R \text {CO} , is an upper bound on R \text {SK} . For the class of pairwise independent network (PIN) models defined on uniform hypergraphs, we show that a certain Type \mathcal S condition, which is verifiable in polynomial time, guarantees that our lower bound on R \text {SK} meets the R \text {CO} upper bound. Thus, the PIN models satisfying our condition are R \text {SK} -maximal, indicating that the upper bound R \text {SK} \le R \text {CO} holds with equality. This allows us to explicitly evaluate R \text {SK} for such PIN models. We also give several examples of PIN models that satisfy our Type \mathcal S condition. Finally, we prove that for an arbitrary multiterminal source model, a stricter version of our Type \mathcal S condition implies that communication from all terminals (omnivocality) is needed for establishing an SK of maximum rate. For three-terminal source models, the converse is also true: omnivocality is needed for generating a maximal-rate SK only if the strict Type \mathcal S condition is satisfied. However, for the source models with four or more terminals, counterexamples exist showing that the converse does not hold in general. [ABSTRACT FROM PUBLISHER]