Paper 2011/106 Original: eprint.iacr.org/2011/106 ↗

Common Randomness and Secret Key Capacities of Two-way Channels

Abstract

Common Randomness Generation (CRG) and Secret Key Establishment (SKE) are fundamental primitives that are used in information-theoretic coding and cryptography. We study these two problems over the two-way channel model of communication, introduced by Shannon. In this model, the common randomness (CK) capacity is defined as the maximum number of random bits per channel use that the two parties can generate. The secret key (SK) capacity is defined similarly when the random bits are also required to be secure against a passive adversary. We provide lower bounds on the two capacities. These lower bounds are tighter than those one might derive based on the previously known results. We prove our lower bounds by proposing a two-round, two-level coding construction over the two-way channel. We show that the lower bound on the common randomness capacity can also be achieved using a simple interactive channel coding (ICC) method. We furthermore provide upper bounds on these capacities and show that the lower and the upper bounds coincide when the two-way channel consists of two independent (physically degraded) one-way channels. We apply the results to the case where the channels are binary symmetric.