Shared Randomness in Arbitrarily Varying Channels

Sagnik Bhattacharya (UMD)

We study an adversarial communication problem where sender Alice wishes to send a message to receiver Bob over an arbitrarily varying channel (AVC) controlled by a malicious adversary James. We assume that Alice and Bob share randomness unknown to James. Using , Alice first encodes the message to a codeword and transmits it over the AVC. James knows the message , the (randomized) codebook and the codeword . James then inputs a jamming state to disrupt communication; we assume a state-deterministic AVC where completely specifies the channel noise. Bob receives a noisy version of codeword ; it outputs a message estimate using and the shared randomness . We show that for AVCs that are ‘adversary-weakened’, exactly equiprobable and independent bits of shared randomness are both necessary and sufficient for achieving randomized coding capacity. The sufficiency proof is based on deterministic list codes along with a polynomial hashing technique which uses the shared randomness. The converse uses a known approach for binary AVCs and extends it to general ‘adversary-weakened’ AVCs using a notion of confusable codewords.