Computationally Efficient Covert Communication
arXiv:1607.02014
Abstract
In this paper, we design the first computationally efficient codes for simultaneously reliable and covert communication over Binary Symmetric Channels (BSCs). Our setting is as follows: a transmitter Alice wishes to potentially reliably transmit a message to a receiver Bob, while ensuring that the transmission taking place is covert with respect to an eavesdropper Willie (who hears Alice's transmission over a noisier BSC). Prior works show that Alice can reliably and covertly transmit O(\sqrt{n}) bits over n channel uses without any shared secret between Alice and Bob. One drawback of prior works is that the computational complexity of the codes designed scales as 2^{Θ(\sqrt{n})}. In this work we provide the first computationally tractable codes with provable guarantees on both reliability and covertness, while simultaneously achieving the best known throughput for the problem.
Submitted to IEEE Transactions on Information Theory