  A transmitter Alice may wish to reliably transmit a message to a receiver Bob
over a binary symmetric channel (BSC), while simultaneously ensuring that her
transmission is 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.
We consider two scenarios. In our first scenario, we assume that the channel
transition probability from Alice to Bob and Willie is perfectly known to all
parties. Here, even when Alice's (potential) communication scheme is publicly
known to Willie (with 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 this result. In our second scenario, we allow uncertainty
in the knowledge of the channel transition probability parameters. In
particular, we assume that the channel transition probabilities for both Bob
and Willie are uniformly drawn from a known interval. Here, we show that, in
contrast to the previous setting, Alice can communicate O(n) bits of message
reliably and deniably (again, with no common randomness). We give both an
achievability result and a matching converse for this setting. Our work builds
upon the work of Bash et al on AWGN channels (but with common randomness) and
differs from other recent works (by Wang et al and Bloch) in two important ways
- firstly our deniability metric is variational distance (as opposed to
Kullback-Leibler divergence), and secondly, our techniques are significantly
different from these works.
