Covert Communication over Asynchronous Channels with Timing Advantage

We study a problem of covert communication over binary symmetric channels (BSC) in an asynchronous setup. Here, Alice seeks to communicate to Bob over a BSC while trying to be covert with respect to Willie, who observes any communication through possibly a different BSC. When Alice communicates, she transmits a message (using a codeword of length n) at a random time uniformly distributed in a window of size A(w) slots. We assume that Bob has side information about the time of transmission leading to a reduced uncertainty of Ab slots for Bob, where A(b) < A(w). In this setup, we seek to characterize the limits of covert communication as a function of the timing advantage. When Aw is increasing exponentially in n, we characterize the covert capacity as a function of Aw and A(b). When A(w) is increasing sub-exponentially in n, we characterize lower and upper bounds on achievable covert bits and show that positive covert rates are not feasible irrespective of timing advantage. Using numerical work, we illustrate our results for different network scenarios, and also highlight a tradeoff between timing advantage and channel advantage (between Bob and Willie).