Universal Covertness for Discrete Memoryless Sources

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.