Derandomizing Codes for the Adversarial Wiretap Channel of Type II

The adversarial wiretap channel of type II (AWTC-II) is a communication channel that can a) read a fraction of the transmitted symbols up to a given bound and b) induce both errors and erasures in a fraction of the symbols up to given bounds. The channel is controlled by an adversary who can freely choose the locations of the symbol reads, errors and erasures via a process with unbounded computational power. The AWTC-II is an extension of Ozarow’s and Wyner’s wiretap channel of type II to the adversarial channel setting. The semantic-secrecy (SS) capacity of the AWTC-II is partially known, where the best-known lower bound is non-constructive and proven via a random coding argument that uses a large number (that is, exponential in blocklength <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>) of random bits to describe the random code. In this work, we establish a new derandomization result in which we match the best-known lower bound via a non-constructive random code that uses only <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>) random bits. Unlike fully random codes, our derandomized code admits an efficient encoding algorithm and benefits from some linear structure. Our derandomization result is a novel application of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">random pseudolinear codes</i> – a class of non-linear codes first proposed for applications outside the AWTC-II setting, which have <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i>-wise independent codewords where <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i> is a design parameter. As the key technical tool in our analysis, we provide a novel concentration inequality for sums of random variables with limited independence, as well as a soft-covering lemma similar to that of Goldfeld, Cuff and Permuter that holds for random codes with <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i>-wise independent codewords.