Universal covertness for discrete memoryless sources

Abstract

Consider a sequence $X^{n}$ of length n emitted by a Discrete Memoryless Source (DMS) with unknown distribution $p_{X}$. The objective is to construct a lossless source code that maps $X^{n}$ to a sequence \widehat {Y}^{m} of length m that is indistinguishable, in terms of Kullback-Leibler divergence, from a sequence emitted by another DMS with known distribution $p_{Y}$. The main result is the existence of a coding scheme that performs this task with an optimal ratio m/n equal to $H(X)/H(Y)$ , the ratio of the Shannon entropies of the two distributions, as n goes to infinity. The coding scheme overcomes the challenges created by the lack of knowledge about $p_{X}$ by a type-based universal lossless source coding scheme that produces as output an almost uniformly distributed sequence, followed by another type-based coding scheme that jointly performs source resolvability and universal lossless source coding. The result recovers and extends previous results that either assume $p_{X}$ or $p_{Y}$ uniform, or $p_{X}$ known. The price paid for these generalizations is the use of common randomness with vanishing rate, whose length scales as the logarithm of n . By allowing common randomness larger than the logarithm of n but still negligible compared to n , a constructive low-complexity encoding and decoding counterpart to the main result is also provided for binary sources by means of polar codes.