Covert Communication Over Adversarially Jammed Channels
- 12 July 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (9) , 6096-6121
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 Ω(logn)) 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 Ω(√n logn), 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
Funding Information
- University Grants Committee (UGC), Hong Kong, General Research Fund (14300617, 14301519)
This publication has 41 references indexed in Scilit:
- Optimal Error Correction Against Computationally Bounded Noise2005
- A mathematical theory of communicationACM SIGMOBILE Mobile Computing and Communications Review, 2001
- 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
- Elimination of correlation in random codes for arbitrarily varying channelsProbability Theory and Related Fields, 1978
- Computational Complexity of Fourier Transforms Over Finite FieldsMathematics of Computation, 1977
- New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalitiesIEEE Transactions on Information Theory, 1977
- The Capacities of Certain Channel Classes Under Random CodingThe Annals of Mathematical Statistics, 1960
- A Comparison of Signalling AlphabetsBell System Technical Journal, 1952