Reliable, Deniable, Hidable Communication: Using Noise as Camouflage

A transmitter Alice may wish to {\it reliably} transmit a message to a receiver Bob over a binary symmetric channel (BSC), while simultaneously ensuring that her transmission is {\it deniable} from an eavesdropper Willie. That is, if Willie listening to Alice's transmissions over a {"significantly noisier"} BSC than the one to Bob, he should be unable to estimate even whether Alice is transmitting. Even when Alice's (potential) communication scheme is publicly known to Willie (with {\it no} common randomness between Alice and Bob), we prove that over n channel uses Alice can transmit a message of length O(\sqrt{n}) bits to Bob, deniably from Willie. We also prove information-theoretic order-optimality of our results. Finally, we demonstrate that in the scenario when the channel noise parameters are unknown to all parties prior to communication, the communication scaling can be significantly improved, to be linear in n. If time permits, will briefly describe AWGN version of the problem, and also a network version of the problem (the material in this talk is based on several joint works, with Pak Hou Che, Mayank Bakshi, Chung Chan, Zonghao Chen, Alex Sprintson, and Swanand Kadhe).

The 1 hour talk will be followed by an additional half hour with more details for those who are interested.

Bio:  B.Tech. ('00), EE, IIT Bombay,
MS/Ph.D. ('05) EE, CalTech,
Postdoctoral Associate ('06) LIDS, MIT,
Currently Associate Professor, Dept. of Information Engineering, The Chinese University of Hong Kong.
Research interests: Network coding and network error-correcting algorithms, coding theory, steganography, group testing, compressive sensing.