Covert Communication over Adversarially Jammed Channels
Authors:
- Qiaosheng ZhangQZQiaosheng Zhang
- Mayank BakshiMBMayank Bakshi
- Sidharth JaggiSJSidharth Jaggi
Preprint
Abstract
Suppose that a transmitter Alice potentially wishes to communicate with a receiver Bob over an adversarially jammed binary 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 based on his observations. We consider a setting where the communication must be simultaneously covert as well as reliable, i.e., James should be unable to accurately distinguish whether or not Alice is communicating, while Bob should be able to correctly recover Alice's message with high probability regardless of the adversarial jamming strategy. We show that, unlike the setting with passive adversaries, covert communication against active adversaries requires Alice and Bob to have a shared key (of length at least Omega(log n)) even when Bob has a better channel than James. We present lower and upper bounds on the information-theoretically optimal throughput as a function of the channel parameters, the desired level of covertness, and the amount of shared key available. These bounds match for a wide range of parameters of interest. We also develop a computationally efficient coding scheme (based on concatenated codes) when the amount of shared key available is $\Omega(\sqrt{n} \log n)$, and further show that this scheme can be implemented with much less amount of shared key when the adversary is assumed to be computationally bounded.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- 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
- Network Information Theory2011
- 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
- Rate-distortion theory for the Shannon cipher systemIEEE Transactions on Information Theory, 1997
- 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