Covert Communication over Adversarially Jammed Channels
Authors:
- Qiaosheng ZhangQZQiaosheng Zhang
- Mayank BakshiMBMayank Bakshi
- Sidharth JaggiSJSidharth Jaggi
Preprint
Abstract
We consider a situation in which a transmitter Alice may wish to communicate with a receiver Bob over an adversarial channel. An active adversary James eavesdrops on their communication over a binary symmetric channel (BSC(q)), and may maliciously flip (up to) a certain fraction p of their transmitted bits. The communication should be both covert and reliable. Covertness requires that the adversary James should be unable to estimate whether or not Alice is communicating based on his noisy observations, while reliability requires that the receiver Bob should be able to correctly recover Alice's message with high probability. Unlike the setting with passive adversaries considered thus far in the literature, we show that reliable covert communication in the presence of actively jamming adversaries requires Alice and Bob to have a shared key (unknown to James). The optimal throughput obtainable depends critically on the size of this key: 1) When Alice and Bob's shared key is less than 0.5log(n) bits, no communication that is simultaneously covert and reliable is possible. Conversely, when the shared key is larger than 6log(n), the optimal throughput scales as O(\sqrt{n}) --- we explicitly characterize even the constant factor (with matching inner and outer bounds) for a wide range of parameters of interest. 2) When Alice and Bob have a large amount (\omega(\sqrt{n}) bits) of shared key, we present a tight covert capacity characterization for all parameters of interest. 3) When the size of the shared key is moderate (belongs to (\Omega(log(n)), O(\sqrt{n}))), we show an achievable coding scheme as well as an outer bound on the information-theoretically optimal throughput. 4) When Alice and Bob's shared key is O(\sqrt{n}log(n)) bits, we develop a computationally efficient coding scheme for Alice/Bob whose throughput is only a constant factor smaller than information-theoretically optimal.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Covert Communication Over Noisy Channels: A Resolvability PerspectiveIEEE Transactions on Information Theory, 2016
- Hiding information in noise: fundamental limits of covert wireless communicationIEEE Communications Magazine, 2015
- Quantum-secure covert communication on bosonic channelsNature Communications, 2015
- Limits of Reliable Communication with Low Probability of Detection on AWGN ChannelsIEEE Journal on Selected Areas in Communications, 2013
- List-Decoding for the Arbitrarily Varying Channel Under State ConstraintsIEEE Transactions on Information Theory, 2012
- Oblivious Communication Channels and Their CapacityIEEE Transactions on Information Theory, 2008
- Optimal Error Correction Against Computationally Bounded Noise2005
- Reliable communication under channel uncertaintyIEEE Transactions on Information Theory, 1998
- The capacity of the arbitrarily varying channel revisited: positivity, constraintsIEEE Transactions on Information Theory, 1988
- New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalitiesIEEE Transactions on Information Theory, 1977