Derandomizing Codes for the Binary Adversarial Wiretap Channel of Type II

We revisit the binary adversarial wiretap channel (AWTC) of type II in which an active adversary can read a fraction r and flip a fraction p of codeword bits. The semantic-secrecy capacity of the AWTC II is partially known, where the best-known lower bound is non-constructive, proven via a random coding argument that uses a large number (that is exponential in blocklength n) of random bits to seed the random code. In this paper, we establish a new derandomization result in which we match the best-known lower bound of 1 − H <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> (p) − r, where H <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> (•) is the binary entropy function, via a random code that uses a small seed of only O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) bits. Our random code construction is a novel application of pseudolinear codes – a class of non-linear codes that have k-wise independent codewords when chosen at random where k is a design parameter. As the key technical tool in our analysis, we provide a soft-covering lemma in the flavor of Goldfeld, Cuff and Permuter (Trans. Inf. Theory 2016) that holds for random codes with k-wise independent codewords.