Paper 2011/106

Common Randomness and Secret Key Capacities of Two-way Channels

Hadi Ahmadi and Reihaneh Safavi-Naini


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.

Note: The full version includes more details and proofs in the appendix.

Available format(s)
Publication info
Published elsewhere. This is the full version of a paper accepted in ICITS 2011. The original publication is available at
Two-way channelwiretap channelcommon randomness capacitysecret key capacity.
Contact author(s)
hahmadi @ ucalgary ca
2011-03-05: received
Short URL
Creative Commons Attribution


      author = {Hadi Ahmadi and Reihaneh Safavi-Naini},
      title = {Common Randomness and Secret Key Capacities of Two-way Channels},
      howpublished = {Cryptology ePrint Archive, Paper 2011/106},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.