Message Transmission and Key Establishment: Conditions for Equality of Weak and Strong Capacities

Hadi Ahmadi and Reihaneh Safavi-Naini (University of Calgary, Canada)

Secure communication using noisy resources was first studied in the two contexts of secure message transmission (SMT) by Wyner as well as Csiszar-and-Korner, and secret key establishment (SKE) by Ahlswede-and-Csiszar as well as Maurer. The work defines secrecy (resp. secret-key (SK)) capacity as the highest achievable rate at which a secure message can be sent (resp. a shared key can be established). Maurer and Wolf later focused on SKE and noticed that the secrecy requirement in the SK capacity definition was weak as it required only the ratio between the adversary's information and the key length to be negligible. They suggested a stronger definition of the SK capacity where secrecy requires absolute amount of adversary's information about the key to be negligible. Additionally, they provided an interesting approach to prove the equality of the two SK capacities for the above communication scenarios (setups). Followup work has since studied several setups for SKE by considering the weak notion of SK capacity without discussing whether the results also hold for the strong definition. In this paper, we pose the question whether Maurer-and-Wolf's approach is applicable to those SKE setups studied thereafter, and more importantly, whether the equality of weak and strong SK capacities can be derived in general for all discrete memoryless communication setups. We also extend this study to message transmission and investigate the equality of weak and strong secrecy capacities. We provide a formal treatment of these questions considering in a general description of a communication setup. We show that weak and strong SK capacities are equal for any setup that allows reliable transmission in any direction. For message transmission, we show that the secrecy capacities are equal when the setup allows the sender to use randomness. We furthermore provide trivial counterexamples that show these sufficient conditions are not always necessary for the equality of the capacities. Whether the conditions can be removed or relaxed by tighter (necessary and sufficient) conditions remains an interesting question for future.

FPS 2012 Program