2016/07/07 by Qiaosheng Zhang, Zhang, Qiaosheng, Mayank Bakshi +3 · 1 citation
Computer Science · Engineering · #Advanced Steganography and Watermarking Techniques #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Wireless Communication Security Techniques
paper · pdf · doi:10.48550/arxiv.1607.02014
openalex publication_date 2016/07/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(√(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Θ(√(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.