Adversarial wiretap channel with public discussion

Wyner´s elegant model of wiretap channel exploits noise in the communication channel to provide perfect secrecy against a computationally unlimited passive eavesdropper, without requiring a shared key. We consider an adversarial model of wiretap channel in which the adversary is active: it selects a fraction ρ_r of the transmitted codeword to eavesdrop, and a fraction ρ_w to corrupt by “adding” adversarial error. The model is interesting as it also captures networks adversaries in the setting of Secure Message Transmission [7]. It has been proved that secure transmission (in one message-round) is possible if and only if ρ_r + ρ_w <; 1. In this paper we show that if communicants have access to a public discussion channel (authentic communication without secrecy), secure transmission becomes possible even if ρ_r+ρ_w > 1, as long as the union of the sets of read and corrupted components do not cover the whole codeword. This makes the results applicable to a much wider range of scenarios. We formalize the model of AWTPPD protocol, and derive tight bounds for the two communication efficiency measures, information rate and message-round complexity (upper bound, and lower bound respectively). We also construct a rate optimal protocol family with minimum number of message-round. We show an application of these results to the Secure Message Transmission with Public Discussion (SMT-PD). In particular we show a new lower bound on the transmission rate of these protocols, and present a new construction of an optimal SMT-PD protocol.