Matthieu R. Bloch | Correction to "Polar codes for Covert Communications over Asynchronous Discrete Memoryless Channels"

This is a small correction to the proof of Lemma 11 in [1]. Many thanks to Ishaque Ashar for discovering the error.

Erroneous statement

The erroneous statement is after Eq. (79) in the proof of Lemma 11. We claimed that the Markov chain $Z_{1 : i - 1}^{1 : n} - C W_{i}^{'} - Z_{i}^{1 : n}$ holds. However, looking at the dependencies introduced through the chaining in Fig. 3, we see that the correct Markov chain is instead $Z_{i}^{1 : n} - C W_{i}^{'} - Z_{i + 1 : b_{n}}^{1 : n}$ .

Fixing the error

Fortunately, there is an easy correction. By Pinsker’s inequality,

V ({\tilde{p}}_{Z_{1 : b_{n}}^{1 : n}}, \prod_{i = 1}^{b_{n}} {\tilde{p}}_{Z_{i}^{1 : n}}) \leq D ({\tilde{p}}_{Z_{1 : b_{n}}^{1 : n}} ‖ \prod_{i = 1}^{b_{n}} {\tilde{p}}_{Z_{i}^{1 : n}}) .

The relative entropy can then be bounded as

\begin{aligned} (1) & D ({\tilde{p}}_{Z_{1 : b_{n}}^{1 : n}} ‖ \prod_{i = 1}^{b_{n}} {\tilde{p}}_{Z_{i}^{1 : n}}) & = \sum_{i = 1}^{b_{n}} D ({\tilde{p}}_{Z_{i}^{1 : n} | Z_{i + 1 : b_{n}}^{1 : n}} ‖ {\tilde{p}}_{Z_{i}^{1 : n}} | {\tilde{p}}_{Z_{i + 1 : b_{n}}^{1 : n}}) \\ (2) & = \sum_{i = 1}^{b_{n}} I ({\tilde{Z}}_{i}^{1 : n}; {\tilde{Z}}_{i + 1 : b_{n}}^{1 : n}) \\ (3) & \leq \sum_{i = 1}^{b_{n}} I ({\tilde{Z}}_{i}^{1 : n}; C W_{i}^{'} {\tilde{Z}}_{i + 1 : b_{n}}^{1 : n}) \\ (4) & = \sum_{i = 1}^{b_{n}} [I ({\tilde{Z}}_{i}^{1 : n}; C W_{i}^{'}) + \underset{= 0}{\underset{⏟}{I ({\tilde{Z}}_{i}^{1 : n}; {\tilde{Z}}_{i + 1 : b_{n}}^{1 : n} | C W_{i}^{'})}}] \\ (5) & = \sum_{i = 1}^{b_{n}} I ({\tilde{Z}}_{i}^{1 : n}; C W_{i}^{'}) \\ (6) & \leq b_{n} δ_{n}^{(5)} \end{aligned}

Therefore, $V ({\tilde{p}}_{Z_{1 : b_{n}}^{1 : n}}, \prod_{i = 1}^{b_{n}} {\tilde{p}}_{Z_{i}^{1 : n}}) \leq \sqrt{b_{n} δ_{n}^{(5)}} \leq b_{n} \sqrt{δ_{n}^{(5)}} .$

References

G. Frèche, M. Bloch, and M. Barret, “Polar Codes for Covert Communications over Asynchronous Discrete Memoryless Channels,” Entropy, vol. 20, no. 1, p. 3, Dec. 2017.

This paper introduces an explicit covert communication code for binary-input asynchronous discrete memoryless channels based on binary polar codes, in which legitimate parties exploit uncertainty created by both the channel noise and the time of transmission to avoid detection by an adversary. The proposed code jointly ensures reliable communication for a legitimate receiver and low probability of detection with respect to the adversary, both observing noisy versions of the codewords. Binary polar codes are used to shape the weight distribution of codewords and ensure that the average weight decays as the block length grows. The performance of the proposed code is severely limited by the speed of polarization, which in turn controls the decay of the average codeword weight with the block length. Although the proposed construction falls largely short of achieving the performance of random codes, it inherits the low-complexity properties of polar codes.

@article{Freche2017, author = {Fr\`eche, Guillaume and Bloch, Matthieu and Barret, Michel}, title = {Polar Codes for Covert Communications over Asynchronous Discrete Memoryless Channels}, journal = {Entropy}, year = {2017}, volume = {20}, number = {1}, pages = {3}, month = dec, issn = {1099-4300}, doi = {10.3390/e20010003}, file = {:2017-Freche-Entropy.pdf:PDF}, groups = {Steganography and covert communications, Polar codes} }