Technical Program

Paper Detail

Paper Title Shared Randomness in Arbitrarily Varying Channels
Paper IdentifierMO4.R7.3
Authors Sagnik Bhattacharya, Indian Institute of Technology, Kanpur, India; Amitalok J. Budkuley, The Chinese University of Hong Kong, Hong Kong SAR of China; Sidharth Jaggi, Chinese University of Hong Kong, Hong Kong SAR of China
Session Codes and Information Theoretic Cryptography
Location Bièvre, Level 5
Session Time Monday, 08 July, 16:40 - 18:00
Presentation Time Monday, 08 July, 17:20 - 17:40
Manuscript  Click here to download the manuscript
Abstract We study an adversarial communication problem where sender Alice wishes to send a message $m$ to receiver Bob over an \emph{arbitrarily varying channel} (AVC) controlled by a malicious adversary James. We assume that Alice and Bob share randomness $K$ unknown to James. Using $K$, Alice first encodes the message $m$ to a codeword $\mathbf{X}$ and transmits it over the AVC. James knows the message $m$, the (randomized) codebook and the codeword $\mathbf{X}$. James then inputs a \emph{jamming state} $\mathbf{S}$ to disrupt communication; we assume a \emph{state-deterministic} AVC where $\mathbf{S}$ completely specifies the channel noise. Bob receives a noisy version $\mathbf{Y}$ of codeword $\mathbf{X}$; it outputs a message estimate $\hat{m}$ using $\mathbf{Y}$ and the shared randomness $K$. We study AVCs, called `adversary-weakened’ AVCs here, where the availability of shared randomness strictly improves the optimum throughput or \emph{capacity} over it than when it is not available; the \emph{randomized coding capacity} characterizes the largest rate possible when $K$ is unrestricted. In this work, we characterize the exact threshold for the amount of shared randomness $K$ so as to achieve the randomized coding capacity for `adversary-weakened’ AVCs. We show that exactly $\log(n)$ equiprobable and independent bits of randomness, shared between Alice and Bob and unknown to adversary James, are both necessary and sufficient for achieving randomized coding capacity for `adversary-weakened’ AVCs. For sufficiency, our achievability is based on a randomized code construction which uses deterministic list codes along with a polynomial hashing technique which uses the shared randomness. Our converse, which establishes the necessity of $\log(n)$ bits of shared randomness, uses a known approach for binary AVCs, and extends it to general `adversary-weakened’ AVCs using a notion of \emph{confusable} codewords.