Wyner's elegant model of wiretap channel exploits noise in the communication channel to provide perfect secrecy against a computationally unlimited eavesdropper without requiring a shared key. We consider an adversarial model of wiretap channel proposed in [18,19] where the adversary is active: it selects a fraction @math of the transmitted codeword to eavesdrop and a fraction @math of the codeword to corrupt by "adding" adversarial error. It was shown that this model also captures network adversaries in the setting of 1-round Secure Message Transmission [8]. It was proved that secure communication (1-round) is possible if and only if @math . In this paper we show that by allowing communicants to have access to a public discussion channel (authentic communication without secrecy) secure communication becomes possible even if @math . We formalize the model of protocol and for two efficiency measures, information rate and message round complexity derive tight bounds. We also construct a rate optimal protocol family with minimum number of message rounds. We show application of these results to Secure Message Transmission with Public Discussion (SMT-PD), and in particular show a new lower bound on transmission rate of these protocols together with a new construction of an optimal SMT-PD protocol.
Channels with adversarial errors have been widely considered in recent years. In this paper we propose a new type of adversarial channel that is defined by two parameters ρr and ρw, specifying the read and write power of the adversary: for a codeword of length n, adversary can read ρrn components and add an error vector of weight up to ρwn to the codeword. We give our motivations, define performance criteria for codes that provide reliable communication over these channels, and describe two constructions, one deterministic and one probabilistic, for these codes. We discuss our results and outline our direction for future research. We introduce randomized Limited View (LV) adversary codes that provide protection against an adversary that uses their partial view of the channel to construct an adversarial error vector that is added to the channel. For a codeword of length N, the adversary selects a subset of size ρrN of components to “see”, and then “adds” an adversarial error vector of weight ρwN to the codeword. Performance of the code is measured by the probability of the decoder failure in recovering the sent message. An (N, qRN, δ)-limited view adversary is a code of rate R that ensures that the success chance of the adversary in making decoder to fail is bounded by δ. Our main motivation to study these codes is providing protection for wireless communication at the physical layer of networks. We formalize the definition of adversarial error and decoder failure, construct a code with efficient encoding and decoding that allows the adversary to, depending on the code rate, read up to half of the sent codeword and add error on the same coordinates. The code is non-linear, has an efficient decoding algorithm, and is constructed using a message authentication code (MAC) and a Folded Reed-Solomon (FRS) code. The decoding algorithm uses an innovative approach that combines the list decoding algorithm of the FRS codes and the MAC verification algorithm to eliminate the exponential size of the list output from the decoding algorithm. We discuss our results and future work.