(i.e., the Plotkin point) of the suffix. Therefore, for simplicity of
presentation, we let James forget the chunk-wise composition of
${\mathcal{C}}^{\prime}$ in the suffix and only use the average composition
$P_{{\mathbf{x}}^{>\alpha}}$.

Once James has chosen ${\mathcal{C}}^{\prime}$ (and the associated
${\mathcal{M}}^{\prime}$ and ${\mathcal{R}}^{\prime}$), we will also reveal
this particular subcode to Bob. This will make Bob have access to knowledge
that he is not supposed to have in the original model. Under he error
probability under the optimal decoder can cannot increase. Therefore, our
lower bound on error probability will continue to hold for Bob without such
knowledge.

####  VII-B2 DMC attack in the prefix

In the prefix, James causally observes
${\underline{x}}(1),{\underline{x}}(2),\cdots,{\underline{x}}(\alpha n)$. He
samples the jamming symbols in the following way: independently for each
$1\leq i\leq\alpha n$,

$\displaystyle{\underline{\mathbf{s}}}(i)$ $\displaystyle\sim
V_{{\mathbf{s}}|{\mathbf{x}}={\underline{x}}(i),{\mathbf{u}}^{\leq\alpha}={\underline{u}}^{\leq\alpha}(i)}.$

####  VII-B3 Posterior distribution

Observing ${\underline{x}}^{\leq\alpha}\in{\mathcal{X}}^{\alpha n}$, James can
compute Bob’s observation
${\underline{y}}^{\leq\alpha}=W({\underline{x}}^{\leq\alpha},{\underline{s}}^{\leq\alpha})\in{\mathcal{Y}}^{\alpha
n}$ in the prefix since he himself designed
${\underline{s}}^{\leq\alpha}\in{\mathcal{S}}^{\alpha n}$ and the channel law
is given by a deterministic function
$W\colon{\mathcal{X}}\times{\mathcal{S}}\to{\mathcal{Y}}$. Given
${\underline{y}}^{\leq\alpha}$, he can further compute the posterior
distribution of
$({\mathbf{m}},{\mathbf{r}})\in{\mathcal{M}}\times{\mathcal{R}}$ conditioned
on ${\underline{y}}^{\leq\alpha}$. In fact, he can compute the joint
distribution
$P_{({\mathbf{m}},{\mathbf{r}}),{\mathbf{y}}^{\leq\alpha}}\in\Delta(({\mathcal{M}}\times{\mathcal{R}})\times{\mathcal{Y}}^{\alpha
n})$ as follows:

$\displaystyle
P_{({\mathbf{m}},{\mathbf{r}}),{\underline{\mathbf{y}}}^{\leq\alpha}}((m,r),{\underline{y}}^{\leq\alpha})$
$\displaystyle=\frac{1}{MN}\sum_{({\underline{s}}(1),\cdots,{\underline{s}}(\alpha
n))\in{\mathcal{S}}^{\alpha
n}}\prod_{i=1}^{n}\left(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}({\underline{s}}(i)|{\underline{x}}_{(m,r)}(i),{\underline{u}}^{\leq\alpha}(i))W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}({\underline{y}}(i)|{\underline{x}}_{(m,r)}(i),{\underline{s}}(i))\right).$

The conditional distribution
$P_{({\mathbf{m}},{\mathbf{r}})|{\mathbf{y}}^{\leq\alpha}}$ can therefore be
computed from the above joint distribution. Define then
$P^{\prime}_{({\mathbf{m}},{\mathbf{r}})|{\mathbf{y}}^{\leq\alpha}={\underline{y}}^{\leq\alpha}}$
as the restriction of
$P_{({\mathbf{m}},{\mathbf{r}})|{\mathbf{y}}^{\leq\alpha}={\underline{y}}^{\leq\alpha}}$
to the subset ${\mathcal{M}}^{\prime}\times{\mathcal{R}}^{\prime}$:

$\displaystyle
P^{\prime}_{({\mathbf{m}},{\mathbf{r}})|{\mathbf{y}}^{\leq\alpha}={\underline{y}}^{\leq\alpha}}((m,r))$
$\displaystyle=\frac{1}{Z({\underline{y}}^{\leq\alpha})}P_{({\mathbf{m}},{\mathbf{r}})|{\mathbf{y}}^{\leq\alpha}={\underline{y}}^{\leq\alpha}}((m,r))\mathds{1}{\left\\{(m,r)\in{\mathcal{M}}^{\prime}\times{\mathcal{R}}^{\prime}\right\\}}$
(46)

and $Z({\underline{y}}^{\leq\alpha})$ is a normalizing factor

$\displaystyle Z({\underline{y}}^{\leq\alpha})$
$\displaystyle\coloneqq\sum_{(m,r)\in{\mathcal{M}}^{\prime}\times{\mathcal{R}}^{\prime}}P_{({\mathbf{m}},{\mathbf{r}})|{\mathbf{y}}^{\leq\alpha}={\underline{y}}^{\leq\alpha}}((m,r)).$

Note that
$P^{\prime}_{({\mathbf{m}},{\mathbf{r}})|{\mathbf{y}}^{\leq\alpha}={\underline{y}}^{\leq\alpha}}$
is in fact consistent with Bob’s posterior distribution on
$({\mathbf{m}},{\mathbf{r}})$ given his observation
${\underline{y}}^{\leq\alpha}$ since we assume that Bob knows
${\mathcal{M}}^{\prime}\times{\mathcal{R}}^{\prime}$.

####  VII-B4 Symmetrization in the suffix

James samples
$({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})\in{\mathcal{M}}\times{\mathcal{R}}$
as follows

$\displaystyle({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})\sim
P^{\prime}_{({\mathbf{m}},{\mathbf{r}})|{\mathbf{y}}^{\leq\alpha}={\underline{y}}^{\leq\alpha}}.$

Using this spoofing message-key pair, James computes the encoding
$\operatorname{Enc}({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})={\underline{x}}_{({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}\in{\mathcal{X}}^{n}$.
Oftentimes we will write ${\underline{\mathbf{x}}}^{\prime}$ for simplicity.

Let ${\underline{v}}^{>\alpha}\in({\mathcal{U}}^{>\alpha})^{(1-\alpha)n}$ to
be determined below. For each $i=\alpha n+1,\alpha n+2,\cdots,n$, suppose
$({\underline{x}}(i),{\underline{\mathbf{x}}}^{\prime}(i))=(x,x^{\prime})$ for
some $(x,x^{\prime})\in{\mathcal{X}}^{2}$. Upon observing
${\underline{x}}(i)$, James dynamically assigns time-sharing symbols to each
time index in a greedy manner. If it happens to be the case that
$\left\|T_{{\underline{x}}^{>\alpha},{\underline{\mathbf{x}}}^{\prime>\alpha}}-\widehat{P}_{{\mathbf{x}},{\mathbf{x}}^{\prime}}\right\|_{\infty}\leq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{CP}(\delta)}}$,
then after $i=n$, each entry of the time-sharing sequence
${\underline{v}}^{>\alpha}$ will be assigned values from $[K^{\prime}]$ so
that

$\displaystyle\left\|T_{{\underline{v}}^{>\alpha},{\underline{x}}^{>\alpha},{\underline{\mathbf{x}}}^{\prime>\alpha}}-P_{{\mathbf{v}}}P_{{\mathbf{x}}|{\mathbf{v}}}^{\otimes
2}\right\|_{\infty}$
$\displaystyle\leq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{CP}(\delta)}}.$
(47)

Then James samples ${\underline{\mathbf{s}}}(j)$ as follows

$\displaystyle{\underline{\mathbf{s}}}(j)$ $\displaystyle\sim
V_{{\mathbf{s}}|{\mathbf{x}}={\underline{x}}(j),{\mathbf{x}}^{\prime}={\underline{\mathbf{x}}}^{\prime}(j),{\mathbf{u}}^{>\alpha}=u}.$

If James is not able to assign values to ${\underline{v}}^{>\alpha}$ in a way
that is consistent with
$P_{{\mathbf{v}}}P_{{\mathbf{x}}|{\mathbf{v}}}^{\otimes 2}$, then this
indicates that
$\left\|T_{{\underline{x}}^{>\alpha},{\underline{\mathbf{x}}}^{\prime>\alpha}}-\widehat{P}_{{\mathbf{x}},{\mathbf{x}}^{\prime}}\right\|_{\infty}>{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{CP}(\delta)}}$
and he declares an attack failure.

If at any time $i<n$ in any stage of the attack, James runs out of his jamming
budget, i.e., the jamming sequence
$({\underline{\mathbf{s}}}(1),\cdots,{\underline{\mathbf{s}}}(i))$ already
violates the power constraint $\lambda_{{\mathbf{s}}}$, then he declares an
attack failure.

###  VII-C Analysis of the babble-only attack

The error analysis of the babble-only attack described in Section VII-A will
be completely subsumed by the following analysis for the babble-and-push
attack (described in Section VII-B) by setting $\alpha=1$. We therefore omit
the analysis of the former and proceed with that of the latter.

###  VII-D Analysis of the babble-and-push attack

Define

$\displaystyle{\mathcal{E}}_{0}$
$\displaystyle\coloneqq\left\\{({\mathbf{m}},{\mathbf{r}})\in{\mathcal{M}}^{\prime}\times{\mathcal{R}}^{\prime}\right\\}.$
(48)

Since a message-key pair uniquely specifies a codeword, by Equation 40, we
have the following lemma.

######  Lemma 11.

For ${\mathcal{E}}_{0}$ defined in Equation 48, it holds that
$\Pr\left[{\mathcal{E}}_{0}\right]\geq c$ where $c>0$ is given by Equation 40.

In the rest of the analysis, we will condition on ${\mathcal{E}}_{0}$ and
suppress the notation for conditioning.

Conditioned on ${\mathcal{E}}_{0}$, the joint distribution of the triple
$({\mathbf{m}},{\underline{\mathbf{x}}},{\underline{\mathbf{y}}}^{\leq\alpha})$
is given by

$\displaystyle
P_{{\mathbf{m}},{\underline{\mathbf{x}}},{\underline{\mathbf{y}}}^{\leq\alpha}}(m,{\underline{x}},{\underline{y}}^{\leq\alpha})$
$\displaystyle=\frac{1}{Z}\sum_{{\underline{s}}^{\leq\alpha}\in{\mathcal{S}}^{n\alpha}}\frac{1}{|{\mathcal{M}}|}P_{{\underline{\mathbf{x}}}|{\mathbf{m}}}({\underline{x}}|m)V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}({\underline{s}}(i)|{\underline{x}}(i),{\underline{u}}^{\leq\alpha})W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}({\underline{y}}(i)|{\underline{x}}(i),{\underline{s}}^{\leq\alpha}(i))\mathds{1}{\left\\{{\underline{x}}\in{\mathcal{C}}^{\prime}\right\\}}$
(49)

where

$\displaystyle Z$
$\displaystyle\coloneqq\mathop{\Pr}_{({\mathbf{m}},{\mathbf{r}})\sim{\mathcal{M}}\times{\mathcal{R}}}\left[{\underline{x}}_{({\mathbf{m}},{\mathbf{r}})}\in{\mathcal{C}}^{\prime}\right]=\Pr\left[{\mathcal{E}}_{0}\right].$

W.r.t. the above joint distribution, define

$\displaystyle{\mathcal{A}}_{1}\coloneqq\left\\{{\underline{y}}^{\leq\alpha}\in{\mathcal{Y}}^{n\alpha}:H({\mathbf{m}}|{\underline{\mathbf{y}}}^{\leq\alpha}={\underline{y}}^{\leq\alpha})\geq
n\delta/4\right\\},\quad{\mathcal{E}}_{1}\coloneqq\left\\{{\underline{\mathbf{y}}}^{\leq\alpha}\in{\mathcal{A}}_{1}\right\\}.$
(50)

We will exhibit a lower bound on the probability of ${\mathcal{E}}_{1}$, that
is, we will show that with at least a constant probability, the the
transmitted message ${\mathbf{m}}$ has a nontrivial amount of residual entropy
given the received vector ${\underline{\mathbf{y}}}^{\leq\alpha}$ in the first
stage.

######  Lemma 12.

For ${\mathcal{E}}_{0},{\mathcal{E}}_{1}$ defined in Equations 48 and 50, it
holds that

$\displaystyle\Pr\left[{\mathcal{E}}_{1}\,|\,{\mathcal{E}}_{0}\right]$
$\displaystyle\geq\frac{\delta}{4}-\frac{1}{n}\log\frac{1}{c},$

where $c>0$ is given by Equation 40.

###### Proof.

By the Data Processing Inequality (Lemma 20),

$\displaystyle I({\mathbf{m}};{\underline{\mathbf{y}}}^{\leq\alpha})$
$\displaystyle\leq
I({\underline{\mathbf{x}}}^{\leq\alpha};{\underline{\mathbf{y}}}^{\leq\alpha})$
$\displaystyle\leq\sum_{u\in{\mathcal{U}}^{\leq\alpha}}I({\underline{\mathbf{x}}}^{(u)};{\underline{\mathbf{y}}}^{(u)})$
$\displaystyle\leq\sum_{u\in{\mathcal{U}}^{\leq\alpha}}n\varepsilon
I({\mathbf{x}}_{u}^{\leq\alpha};{\mathbf{y}}_{u}^{\leq\alpha})$ (51)
$\displaystyle=n\alpha\sum_{u\in{\mathcal{U}}^{\leq\alpha}}\frac{1}{\alpha
K}I({\mathbf{x}}_{u}^{\leq\alpha};{\mathbf{y}}_{u}^{\leq\alpha})$
$\displaystyle=n\alpha
I({\mathbf{x}}^{\leq\alpha};{\mathbf{y}}^{\leq\alpha}|{\mathbf{u}}^{\leq\alpha}).$
(52)

All information measures involving
${\mathbf{m}},{\underline{\mathbf{x}}},{\underline{\mathbf{y}}}^{\leq\alpha}$
are computed according to Equation 49. In Equation 51,
$({\mathbf{x}}_{u}^{\leq\alpha},{\mathbf{y}}_{u}^{\leq\alpha})$ is distributed
according to
$P_{{\mathbf{x}}_{u}^{\leq\alpha},{\mathbf{y}}_{u}^{\leq\alpha}}\in\Delta({\mathcal{X}}\times{\mathcal{Y}})$
defined as

$\displaystyle
P_{{\mathbf{x}}_{u}^{\leq\alpha},{\mathbf{y}}_{u}^{\leq\alpha}}(x,y)$
$\displaystyle=\sum_{s\in{\mathcal{S}}}P_{{\mathbf{x}}|{\mathbf{u}}=u}(x)V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}=u}(s|x)W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x,s).$

In Equation 52, the mutual information is evaluated according to
$P_{{\mathbf{u}}^{\leq\alpha},{\mathbf{x}}^{\leq\alpha},{\mathbf{y}}^{\leq\alpha}}\in\Delta({\mathcal{U}}^{\leq\alpha}\times{\mathcal{X}}\times{\mathcal{Y}})$
defined as

$\displaystyle
P_{{\mathbf{u}}^{\leq\alpha},{\mathbf{x}}^{\leq\alpha},{\mathbf{y}}^{\leq\alpha}}(u,x,y)$
$\displaystyle=\sum_{s\in{\mathcal{S}}}\frac{1}{\alpha
K}P_{{\mathbf{x}}|{\mathbf{u}}}(x|u)V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}(s|x,u)W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x,s).$

Therefore,

$\displaystyle
H({\mathbf{m}}|{\underline{\mathbf{y}}}^{\leq\alpha})=H({\mathbf{m}})-I({\mathbf{m}};{\underline{\mathbf{y}}}^{\leq\alpha})\geq
nR-\log\frac{1}{c}-n\alpha
I({\mathbf{x}}^{\leq\alpha};{\mathbf{y}}^{\leq\alpha}|{\mathbf{u}}^{\leq\alpha})\geq
n\delta/2-\log\frac{1}{c}.$

The first inequality follows since conditioned on ${\mathcal{E}}_{0}$,
${\mathbf{m}}$ is uniformly distributed in ${\mathcal{M}}^{\prime}$, and we
use the bound $|{\mathcal{M}}^{\prime}|\geq c2^{nR}$. To see the latter bound,
one simply notes that $|{\mathcal{M}}^{\prime}|$ is obviously at least the LHS
of Equation 40 since the inner summation (over ${\underline{x}}$) of the LHS
is at most $1$. The second inequality above follows from the choice of the
rate (see Equation 44) and the guarantee of the subcode (see Equation 45).

We now argue that the event ${\mathcal{E}}_{1}$ has a nontrivial probability
to happen. This follows from a Markov-type argument.

$\displaystyle n\delta/2-\log\frac{1}{c}$ $\displaystyle\leq
H({\mathbf{m}}|{\underline{\mathbf{y}}}^{\leq\alpha})=\sum_{{\underline{y}}^{\leq\alpha}\in{\mathcal{Y}}^{n\alpha}}\Pr\left[{\underline{\mathbf{y}}}^{\leq\alpha}={\underline{y}}^{\leq\alpha}\right]H({\mathbf{m}}|{\underline{\mathbf{y}}}^{\leq\alpha}={\underline{y}}^{\leq\alpha})$
$\displaystyle=\sum_{{\underline{y}}^{\leq\alpha}\in{\mathcal{A}}_{1}}+\sum_{{\underline{y}}^{\leq\alpha}\not\in{\mathcal{A}}_{1}}\Pr\left[{\underline{\mathbf{y}}}^{\leq\alpha}={\underline{y}}^{\leq\alpha}\right]H({\mathbf{m}}|{\underline{\mathbf{y}}}^{\leq\alpha}={\underline{y}}^{\leq\alpha})$
$\displaystyle\leq\Pr\left[{\mathcal{E}}_{1}\,|\,{\mathcal{E}}_{0}\right]\cdot
nR+(1-\Pr\left[{\mathcal{E}}_{1}\,|\,{\mathcal{E}}_{0}\right])\cdot{n\delta}/{4}\leq\Pr\left[{\mathcal{E}}_{1}\,|\,{\mathcal{E}}_{0}\right]\cdot
n+{n\delta}/{4}.$

Therefore
$\Pr\left[{\mathcal{E}}_{1}\,|\,{\mathcal{E}}_{0}\right]\geq\delta/4$. ∎

Let $({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})$ be the message-key pair
that James sampled during the second stage of his attack. For James attack to
be successful, it is required that the spoofing message
${\mathbf{m}}^{\prime}$ is different from the Alice’s chosen message
${\mathbf{m}}$. This will indeed be the case with a constant probability.

It was shown in [DJLS13] that as long as the entropy of a source distribution
is high, then i.i.d. samples from that distribution are unlikely to collide.

######  Lemma 13 ([DJLS13]).

Let ${\mathcal{V}}$ be a finite set and $P\in\Delta({\mathcal{V}})$. Let
${\mathbf{v}}_{1},\cdots,{\mathbf{v}}_{k}$ be i.i.d. samples from $P$. Then

$\displaystyle\Pr\left[\left|\left\\{{\mathbf{v}}_{1},\cdots,{\mathbf{v}}_{k}\right\\}\right|=k\right]\geq$
$\displaystyle\left(\frac{H(P)-1-\log k}{\log|{\mathcal{V}}|}\right)^{k-1}.$

Let

$\displaystyle{\mathcal{E}}_{2}$
$\displaystyle\coloneqq\left\\{{\mathbf{m}}\neq{\mathbf{m}}^{\prime}\right\\},$
(53) $\displaystyle{\mathcal{E}}_{3}$
$\displaystyle\coloneqq\left\\{\left\|T_{{\underline{x}}_{({\mathbf{m}},{\mathbf{r}})}^{>\alpha},{\underline{x}}_{({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}^{>\alpha}}-\widehat{P}_{{\mathbf{x}},{\mathbf{x}}^{\prime}}\right\|_{\infty}\leq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{CP}(\delta)}}\right\\}.$
(54)

Since conditioned on ${\underline{\mathbf{y}}}^{\leq\alpha}$, ${\mathbf{m}}$
and ${\mathbf{m}}^{\prime}$ are i.i.d. according to
$P^{\prime}_{({\mathbf{m}},{\mathbf{r}})|{\underline{\mathbf{y}}}^{\leq\alpha}}$
(cf. Equation 46), Lemma 13 immediately yields a lower bound on
$\Pr\left[{\mathcal{E}}_{2}\,|\,{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\right]$.

######  Lemma 14.

For ${\mathcal{E}}_{0},{\mathcal{E}}_{1},{\mathcal{E}}_{2}$ defined in
Equations 48, 50 and 53, respectively, it holds that

$\displaystyle\Pr\left[{\mathcal{E}}_{2}\,|\,{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\right]$
$\displaystyle\geq{\frac{n\delta/2-1-\log 2}{\log
M}}\geq{\frac{\delta}{2}-\frac{1}{n}}.$

We then would like to lower bound
$\Pr\left[{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}\,|\,{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\right]$.
To this end, we first recall a useful combinatorial theorem (which we call the
_Generalized Plotkin Bound_) proved in [WBBJ19]. It concerns a structural
property of a generic set of sequences.

######  Theorem 15 (Generalized Plotkin bound, [WBBJ19]).

Let ${\mathcal{X}}$ be a finite set and
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{input}(\delta)}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{CP}(\delta)}}>0$
be small constants. There exists a large constant
$N_{\textnormal{Plokin}}\in{\mathbb{Z}}_{\geq 1}$ depends on
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{input}(\delta)}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{CP}(\delta)}},|{\mathcal{X}}|$
but not on $n$ such that for any sufficiently large $n\in{\mathbb{Z}}_{\geq
1}$ and any set
$\left\\{{\underline{x}}_{1},\cdots,{\underline{x}}_{M}\right\\}\subset{\mathcal{X}}^{n}$
of distinct vectors satisfying

  1. 1.

$\left\|T_{{\underline{x}}}-P_{\mathbf{x}}\right\|_{\infty}\leq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{input}(\delta)}}$
for some $P_{\mathbf{x}}\in\Delta({\mathcal{X}})$;

  2. 2.

$M\geq N_{\textnormal{Plotkin}}$,

there must exist $1\leq i\neq j\leq M$ and
$P_{{\mathbf{x}},{\mathbf{x}}^{\prime}}\in{\mathsf{CP}}(P_{\mathbf{x}})$ such
that

$\displaystyle\left\|T_{{\underline{x}}_{i},{\underline{x}}_{j}}-P_{{\mathbf{x}},{\mathbf{x}}^{\prime}}\right\|_{\infty}$
$\displaystyle\leq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{CP}(\delta)}}.$

We now use Theorem 15 to prove a lower bound on
$\Pr\left[{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}\,|\,{\mathcal{E}}_{1}\right]$.

######  Lemma 16.

For ${\mathcal{E}}_{0},{\mathcal{E}}_{1},{\mathcal{E}}_{2},{\mathcal{E}}_{3}$
defined in Equations 48, 50, 53 and 54, respectively, it holds that

$\displaystyle\Pr\left[{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}\,|\,{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\right]$
$\displaystyle\geq\frac{1}{N^{2}}\left(\frac{\delta}{2}-\frac{1+\log
N}{n}\right)^{N-1},$

where $N=N_{\textnormal{Plotkin}}\in{\mathbb{Z}}_{\geq 1}$ is given by Theorem
15. In particular $N$ depends only on
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{input}(\delta)}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{CP}(\delta)}},|{\mathcal{X}}|$,
but not on $n$.

###### Proof.

Let $N\in{\mathbb{Z}}_{\geq 1}$ be a sufficiently large constant to be
specified later and
$({\mathbf{m}}_{1},{\mathbf{r}}_{1}),\cdots,({\mathbf{m}}_{N},{\mathbf{r}}_{N})$
be i.i.d. according to
$P^{\prime}_{({\mathbf{m}},{\mathbf{r}})|{\mathbf{y}}^{\leq\alpha}={\underline{y}}^{\leq\alpha}}$.
Define

$\displaystyle{\mathcal{E}}_{2}^{\prime}$
$\displaystyle\coloneqq\left\\{\left|{\left\\{{\mathbf{m}}_{1},\cdots,{\mathbf{m}}_{N}\right\\}}\right|=N\right\\},\quad{\mathcal{E}}_{i,j}\coloneqq\left\\{{\mathbf{m}}_{i}\neq{\mathbf{m}}_{j}\right\\}\cap\left\\{\left\|T_{{\underline{x}}_{({\mathbf{m}}_{i},{\mathbf{r}}_{i})}^{>\alpha},{\underline{x}}_{({\mathbf{m}}_{j},{\mathbf{r}}_{j})}^{>\alpha}}-\widehat{P}_{{\mathbf{x}},{\mathbf{x}}^{\prime}}\right\|_{\infty}\leq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{CP}(\delta)}}\right\\}.$

Now, for one thing, we have by the union bound

$\displaystyle\Pr\left[{\mathcal{E}}_{2}^{\prime}\cap\bigcup_{1\leq i,j\leq
N}{\mathcal{E}}_{i,j}\,|\,{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\right]$
$\displaystyle\leq
N^{2}\Pr\left[{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}\,|\,{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\right].$
(55)

For another thing,

$\displaystyle\Pr\left[{\mathcal{E}}_{2}^{\prime}\cap\bigcup_{1\leq i,j\leq
N}{\mathcal{E}}_{i,j}\,|\,{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\right]$
$\displaystyle=\Pr\left[{\mathcal{E}}_{2}^{\prime}\,|\,{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\right]\Pr\left[\bigcup_{1\leq
i,j\leq
N}{\mathcal{E}}_{i,j}\,|\,{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}^{\prime}\right]=\Pr\left[{\mathcal{E}}_{2}^{\prime}\,|\,{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\right],$
(56)

where the last equality follows since by the Generalized Plotkin bound
(Theorem 15), the event $\bigcup_{i,j=1}^{N}{\mathcal{E}}_{i,j}$ happens with
probability $1$ given
${\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}^{\prime}$.
Specifically, once $N$ is chosen to be larger than $N_{\textnormal{Plotkin}}$
given by Theorem 15, ${\mathcal{E}}_{1}$ implies the existence of a pair of
(distinct) codewords whose joint type is approximately completely positive.

By Lemma 13,

$\displaystyle\Pr\left[{\mathcal{E}}_{2}^{\prime}\,|\,{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\right]$
$\displaystyle\geq\left(\frac{n\delta/2-1-\log N}{\log M}\right)^{N-1}.$ (57)

Therefore, Equations 55, 56 and 57 imply the following lower bound

$\displaystyle\Pr\left[{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}\,|\,{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\right]$
$\displaystyle\geq\frac{1}{N^{2}}\left(\frac{n\delta/2-1-\log N}{\log
M}\right)^{N-1}\geq\frac{1}{N^{2}}\left(\frac{\delta}{2}-\frac{1+\log
N}{n}\right)^{N-1},$

as promised in Lemma 16. ∎

Let

$\displaystyle{\mathcal{E}}_{4}$
$\displaystyle\coloneqq\left\\{T_{{\underline{\mathbf{s}}}}\in\lambda_{{\mathbf{s}}}\right\\}.$
(58)

######  Lemma 17 (Concentration of jamming cost).

For
${\mathcal{E}}_{0},{\mathcal{E}}_{1},{\mathcal{E}}_{2},{\mathcal{E}}_{3},{\mathcal{E}}_{4}$
defined in Equations 48, 50, 53, 54 and 58, respectively, it holds that

$\displaystyle\Pr\left[{\mathcal{E}}_{4}\,|\,{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}\right]$
$\displaystyle\geq 1-e^{-\Omega(\delta^{2}n)}.$

###### Proof.

Conditioned on ${\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}$,
during the symmetrization phase of the attack (Section VII-B4), James is able
to learn a time-sharing sequence
${\underline{v}}^{>\alpha}\in({\mathcal{U}}^{>\alpha})^{(1-\alpha)n}$ that is
consistent with the completely positive structure of
$\widehat{P}_{{\mathbf{x}},{\mathbf{x}}^{\prime}}$. That is, Equation 47
holds. This implies that the cost of the suffix jamming vector
${\underline{\mathbf{s}}}^{>\alpha}$ is feasible with high probability.
Indeed, by the Chernoff bound (Lemma 21),

$\displaystyle\Pr\left[\left\|T_{{\underline{\mathbf{s}}}^{>\alpha}|{\underline{x}}_{({\mathbf{m}},{\mathbf{r}})}^{>\alpha},{\underline{x}}_{({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}^{>\alpha},{\underline{v}}^{>\alpha}}-V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}\right\|_{\infty}>\frac{\delta}{8}\,|\,{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}\right]$
$\displaystyle=\Pr\left[\exists(v,x,x^{\prime})\in{\mathcal{U}}^{>\alpha}\times{\mathcal{X}}^{2},\left\|T_{{\underline{\mathbf{s}}}^{>\alpha}|{\underline{x}}_{({\mathbf{m}},{\mathbf{r}})}^{>\alpha},{\underline{x}}_{({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}^{>\alpha},{\underline{v}}^{>\alpha}}(\cdot|x,x^{\prime},v)-V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}(\cdot|x,x^{\prime},v)\right\|_{\infty}\geq\frac{\delta}{8}\,|\,{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}\right]$
$\displaystyle\leq\sum_{(v,x,x^{\prime})\in{\mathcal{U}}^{>\alpha}\times{\mathcal{X}}^{2}}\sum_{s\in{\mathcal{S}}}\Pr\left[\left|T_{{\underline{\mathbf{s}}}^{>\alpha}|{\underline{x}}_{({\mathbf{m}},{\mathbf{r}})}^{>\alpha},{\underline{x}}_{({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}^{>\alpha},{\underline{v}}^{>\alpha}}(s|x,x^{\prime},v)-V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}(s|x,x^{\prime},v)\right|>\frac{\delta}{8}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}(s|x,x^{\prime},v)\,|\,{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}\right]$
$\displaystyle\leq\sum_{(v,x,x^{\prime},s)\in{\mathcal{U}}^{>\alpha}\times{\mathcal{X}}^{2}\times{\mathcal{S}}}2\exp\left(-\frac{(\delta/8)^{2}}{3}nP_{\mathbf{v}}(v)P_{{\mathbf{x}}|{\mathbf{v}}}(x|v)P_{{\mathbf{x}}|{\mathbf{v}}}(x^{\prime}|v)V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}(s|x,x^{\prime},v)\right)$
$\displaystyle=e^{-\Omega(\delta^{2}n)}.$ (59)

Similarly, the jamming cost in the prefix is also bounded with high
probability

$\displaystyle\Pr\left[\left\|T_{{\underline{\mathbf{s}}}^{\leq\alpha}|{\underline{x}}_{({\mathbf{m}},{\mathbf{r}})}^{\leq\alpha},{\underline{u}}^{\leq\alpha}}-V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}\right\|_{\infty}>\frac{\delta}{8}\right]\leq\sum_{(u,x,s)\in{\mathcal{U}}^{\leq\alpha}\times{\mathcal{X}}\times{\mathcal{S}}}2\exp\left(-\frac{(\delta/8)^{2}}{3}n\varepsilon
V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}(s|x,u)\right)=e^{-\Omega(\delta^{2}n)}.$
(60)

By the triangle inequality, Equations 59 and 60 imply

$\displaystyle\left\|T_{{\underline{u}}^{\leq\alpha},{\underline{x}}_{({\mathbf{m}},{\mathbf{r}})}^{\leq\alpha}}(\cdot|u)T_{{\underline{\mathbf{s}}}^{\leq\alpha}|{\underline{x}}_{({\mathbf{m}},{\mathbf{r}})}^{\leq\alpha},{\underline{u}}^{\leq\alpha}}-P_{{\mathbf{u}}^{\leq\alpha}}P_{{\mathbf{x}}|{\mathbf{u}}^{\leq\alpha}}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}\right\|_{\infty}$
$\displaystyle\leq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{input}(\delta)}}+\delta/8+{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{input}(\delta)}}\delta/8\leq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{input}(\delta)}}+\delta/4,$
(61)
$\displaystyle\left\|T_{{\underline{v}}^{>\alpha}}T_{{\underline{x}}_{({\mathbf{m}},{\mathbf{r}})}^{>\alpha},{\underline{x}}_{({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}^{>\alpha}|{\underline{v}}^{>\alpha}}T_{{\underline{\mathbf{s}}}^{>\alpha}|{\underline{x}}_{({\mathbf{m}},{\mathbf{r}})}^{>\alpha},{\underline{x}}_{({\mathbf{m}},{\mathbf{r}}^{\prime})}^{>\alpha},{\underline{v}}^{>\alpha}}-P_{{\mathbf{v}}}P_{{\mathbf{x}}|{\mathbf{v}}}^{\otimes
2}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}\right\|_{\infty}$
$\displaystyle\leq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{CP}(\delta)}}+\delta/8+{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{CP}(\delta)}}\delta/8\leq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{CP}(\delta)}}+\delta/4,$
(62)

with high probability. Note that

$\displaystyle T_{{\underline{\mathbf{s}}}}$
$\displaystyle=\alpha\left[T_{{\underline{u}}^{\leq\alpha}}T_{{\underline{x}}_{({\mathbf{m}},{\mathbf{r}})}^{\leq\alpha}|{\underline{u}}^{\leq\alpha}}T_{{\underline{\mathbf{s}}}^{\leq\alpha}|{\underline{x}}_{({\mathbf{m}},{\mathbf{r}})}^{\leq\alpha},{\underline{u}}^{\leq\alpha}}\right]_{{\mathbf{s}}^{\leq\alpha}}+(1-\alpha)\left[T_{{\underline{v}}^{>\alpha}}T_{{\underline{x}}_{({\mathbf{m}},{\mathbf{r}})}^{>\alpha},{\underline{x}}_{({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}^{>\alpha}|{\underline{v}}^{>\alpha}}T_{{\underline{\mathbf{s}}}^{>\alpha}|{\underline{x}}_{({\mathbf{m}},{\mathbf{r}})}^{>\alpha},{\underline{x}}_{({\mathbf{m}},{\mathbf{r}}^{\prime})}^{>\alpha},{\underline{v}}^{>\alpha}}\right]_{{\mathbf{s}}^{>\alpha}}.$

Define

$\displaystyle P_{{\mathbf{s}}}$
$\displaystyle\coloneqq\alpha\left[P_{{\mathbf{u}}^{\leq\alpha}}P_{{\mathbf{x}}|{\mathbf{u}}^{\leq\alpha}}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}\right]_{{\mathbf{s}}^{\leq\alpha}}+(1-\alpha)\left[P_{{\mathbf{v}}}P_{{\mathbf{x}}|{\mathbf{v}}}^{\otimes
2}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}\right]_{{\mathbf{s}}^{>\alpha}}.$

Equations 61 and 62 further imply

$\displaystyle\left\|T_{{\underline{\mathbf{s}}}}-P_{{\mathbf{s}}}\right\|_{\infty}$
$\displaystyle\leq|{\mathcal{U}}^{\leq\alpha}||{\mathcal{X}}||{\mathcal{S}}|({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{input}(\delta)}}+\delta/4)+|{\mathcal{U}}^{>\alpha}||{\mathcal{X}}|^{2}|{\mathcal{S}}|({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{CP}(\delta)}}+\delta/4).$
(63)

Since
$P_{{\mathbf{s}}}\in\mathrm{int}_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}(\lambda_{{\mathbf{s}}})$
and
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}$
was set to be larger than the RHS of Equation 63, we have
$T_{{\underline{\mathbf{s}}}}\in\lambda_{{\mathbf{s}}}$ with probability
$1-e^{-\Omega(\delta^{2}n)}$ by the triangle inequality. ∎

######  Lemma 18 (Lower bound on error probability).

For any code with a (potentially stochastic) encoder-decoder pair
$(\operatorname{Enc},\operatorname{Dec})$ and the babble-and-push attack
$\mathrm{Jam}$ described in Section VII-B, the average error probability
defined in Equation 1 is lower bounded as follows:

$\displaystyle
P_{{\mathrm{e}},\mathrm{avg}}(\operatorname{Enc},\operatorname{Dec},\mathrm{Jam})$
$\displaystyle\geq\frac{c}{2}\cdot\left(\frac{\delta}{4}-\frac{1}{n}\log\frac{1}{c}\right)\cdot\frac{1}{N^{2}}\left(\frac{\delta}{2}-\frac{1+\log
N}{n}\right)^{N-1}\cdot\left(1-e^{-\Omega(\delta^{2}n)}\right),$

where $c>0$ is given by Equation 40 and
$N=N_{\textnormal{Plotkin}}\in{\mathbb{Z}}_{\geq 1}$ is given by Theorem 15,
both independent of $n$.

###### Proof.

Since conditioned on ${\underline{\mathbf{y}}}^{\leq\alpha}$,
$({\mathbf{m}},{\mathbf{r}}^{\prime})$ and
$({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})$ are i.i.d. (more specifically,
independent and both following the posterior distribution
$P^{\prime}_{({\mathbf{m}},{\mathbf{r}})|{\underline{\mathbf{y}}}^{\leq\alpha}={\underline{y}}^{\leq\alpha}}$),
we have

$\displaystyle
P_{{\underline{\mathbf{y}}}^{\leq\alpha},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}({\underline{y}}^{\leq\alpha},(m,r),(m^{\prime},r^{\prime}))=$
$\displaystyle
P_{{\underline{\mathbf{y}}}^{\leq\alpha}}({\underline{y}}^{\leq\alpha})P_{({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})|{\underline{\mathbf{y}}}^{\leq\alpha}}((m,r),(m^{\prime},r^{\prime})|{\underline{y}}^{\leq\alpha})$
$\displaystyle=$ $\displaystyle
P_{{\underline{\mathbf{y}}}^{\leq\alpha}}({\underline{y}}^{\leq\alpha})P^{\prime}_{({\mathbf{m}},{\mathbf{r}})|{\underline{\mathbf{y}}}^{\leq\alpha}}((m,r)|{\underline{y}}^{\leq\alpha})P^{\prime}_{({\mathbf{m}},{\mathbf{r}})|{\underline{\mathbf{y}}}^{\leq\alpha}}((m^{\prime},r^{\prime})|{\underline{y}}^{\leq\alpha})$
$\displaystyle=$ $\displaystyle
P_{{\underline{\mathbf{y}}}^{\leq\alpha}}({\underline{y}}^{\leq\alpha})P_{({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime}),({\mathbf{m}},{\mathbf{r}})|{\underline{\mathbf{y}}}^{\leq\alpha}}((m,r),(m^{\prime},r^{\prime})|{\underline{y}}^{\leq\alpha})$
$\displaystyle=$ $\displaystyle
P_{{\underline{\mathbf{y}}}^{\leq\alpha},({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime}),({\mathbf{m}},{\mathbf{r}})}({\underline{y}}^{\leq\alpha},(m,r),(m^{\prime},r^{\prime})).$
(64)

We also claim that conditioned on
${\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}$,

$\displaystyle
P_{{\underline{\mathbf{y}}}^{>\alpha}|{\underline{\mathbf{y}}}^{\leq\alpha},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}=P_{{\underline{\mathbf{y}}}^{>\alpha}|{\underline{\mathbf{y}}}^{\leq\alpha},({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime}),({\mathbf{m}},{\mathbf{r}})}.$
(65)

To see this, by Bayes’ theorem,

$\displaystyle
P_{{\underline{\mathbf{y}}}^{>\alpha}|{\underline{\mathbf{y}}}^{\leq\alpha},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}$
$\displaystyle=P_{{\underline{\mathbf{y}}}^{>\alpha},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})|{\underline{\mathbf{y}}}^{\leq\alpha}}/P_{({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})|{\underline{\mathbf{y}}}^{\leq\alpha}}.$
(66)

The distribution in the denominator, as we just argued (Equation 64), is
conditionally exchangeable. For the numerator, we have

$\displaystyle
P_{{\underline{\mathbf{y}}}^{>\alpha},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})|{\underline{\mathbf{y}}}^{\leq\alpha}}({\underline{y}}^{>\alpha},(m,r),(m^{\prime},r^{\prime})|{\underline{y}}^{\leq\alpha})$
$\displaystyle=P^{\prime}_{({\mathbf{m}},{\mathbf{r}})|{\underline{\mathbf{y}}}}((m,r)|{\underline{y}}^{\leq\alpha})P^{\prime}_{({\mathbf{m}},{\mathbf{r}})|{\underline{\mathbf{y}}}}((m^{\prime},r^{\prime})|{\underline{y}}^{\leq\alpha})$
$\displaystyle\qquad\sum_{{\underline{s}}\in{\mathcal{S}}^{n}}\prod_{i=\alpha
n+1}^{n}\left(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}({\underline{s}}(i)|{\underline{x}}_{(m,r)}(i),{\underline{x}}_{(m^{\prime},r^{\prime})}(i),{\underline{v}}^{>\alpha}(i))W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}({\underline{y}}(i)|{\underline{x}}_{(m,r)}(i),{\underline{s}}(i))\right)$
$\displaystyle=P^{\prime}_{({\mathbf{m}},{\mathbf{r}})|{\underline{\mathbf{y}}}}((m,r)|{\underline{y}}^{\leq\alpha})P^{\prime}_{({\mathbf{m}},{\mathbf{r}})|{\underline{\mathbf{y}}}}((m^{\prime},r^{\prime})|{\underline{y}}^{\leq\alpha})$
$\displaystyle\qquad\prod_{i=\alpha
n+1}^{n}\sum_{{\underline{s}}(i)\in{\mathcal{S}}}\left(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}({\underline{s}}(i)|{\underline{x}}_{(m,r)}(i),{\underline{x}}_{(m^{\prime},r^{\prime})}(i),{\underline{v}}^{>\alpha}(i))W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}({\underline{y}}(i)|{\underline{x}}_{(m,r)}(i),{\underline{s}}(i))\right)$
$\displaystyle=P^{\prime}_{({\mathbf{m}},{\mathbf{r}})|{\underline{\mathbf{y}}}}((m^{\prime},r^{\prime})|{\underline{y}}^{\leq\alpha})P^{\prime}_{({\mathbf{m}},{\mathbf{r}})|{\underline{\mathbf{y}}}}((m,r)|{\underline{y}}^{\leq\alpha})$
$\displaystyle\qquad\prod_{i=\alpha
n+1}^{n}\sum_{{\underline{s}}(i)\in{\mathcal{S}}}\left(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}({\underline{s}}(i)|{\underline{x}}_{(m^{\prime},r^{\prime})}(i),{\underline{x}}_{(m,r)}(i),{\underline{v}}^{>\alpha}(i))W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}({\underline{y}}(i)|{\underline{x}}_{(m^{\prime},r^{\prime})}(i),{\underline{s}}(i))\right)$
(67)
$\displaystyle=P_{{\underline{\mathbf{y}}}^{>\alpha},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})|{\underline{\mathbf{y}}}^{\leq\alpha}}({\underline{y}}^{>\alpha},(m^{\prime},r^{\prime}),(m,r)|{\underline{y}}^{\leq\alpha}).$
(68)

where Equation 67 follows since
$V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}\in{\mathcal{V}}$
(cf. Definition 10) and therefore satisfies the symmetrization equation.
Combining Equations 64, 66 and 68 proves Equation 65.

Now, consider the joint distribution of
$({\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime}))$
given
${\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}$.

$\displaystyle
P_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}$
$\displaystyle=P_{{\underline{\mathbf{y}}}^{\leq\alpha},{\underline{\mathbf{y}}}^{>\alpha},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}})}$
$\displaystyle=P_{{\underline{\mathbf{y}}}^{\leq\alpha},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}P_{{\underline{\mathbf{y}}}^{>\alpha}|{\underline{\mathbf{y}}}^{\leq\alpha},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}$
$\displaystyle=P_{{\underline{\mathbf{y}}}^{\leq\alpha},({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime}),({\mathbf{m}},{\mathbf{r}})}P_{{\underline{\mathbf{y}}}^{>\alpha}|{\underline{\mathbf{y}}}^{\leq\alpha},({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime}),({\mathbf{m}},{\mathbf{r}})}$
$\displaystyle=P_{{\underline{\mathbf{y}}},({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime}),({\mathbf{m}},{\mathbf{r}})}.$

Define
$Q_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}$
as a truncated version of
$P_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}$
in which ${\underline{y}}$ results only from feasible ${\underline{s}}$.
Specifically,

$\displaystyle
Q_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}({\underline{y}},(m,r),(m^{\prime},r^{\prime}))$
$\displaystyle\coloneqq\frac{1}{|{\mathcal{M}}||{\mathcal{R}}|}\sum_{{\underline{s}}^{\leq\alpha}\in{\mathcal{S}}^{\alpha
n}}\prod_{i=1}^{\alpha
n}\left[V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}({\underline{s}}^{\leq\alpha}(i)|{\underline{x}}_{(m,r)}(i),{\underline{u}}^{\leq\alpha}(i))W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}({\underline{y}}^{\leq\alpha}(i)|{\underline{x}}_{(m,r)}(i),{\underline{s}}^{\leq\alpha}(i))\right]P_{({\mathbf{m}},{\mathbf{r}})|{\underline{\mathbf{y}}}^{\leq\alpha}}((m^{\prime},r^{\prime})|{\underline{y}}^{\leq\alpha})$
$\displaystyle\qquad\sum_{{\underline{s}}^{>\alpha}\in{\mathcal{S}}^{(1-\alpha)n}}\prod_{i=\alpha
n+1}^{n}\left[V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}({\underline{s}}^{>\alpha}(i)|{\underline{x}}_{(m,r)}(i),{\underline{x}}_{(m^{\prime},r^{\prime})}(i),{\underline{v}}^{>\alpha}(i))W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}({\underline{y}}^{>\alpha}(i)|{\underline{x}}_{(m,r)}(i),{\underline{s}}^{>\alpha}(i))\right]\mathds{1}_{{\mathcal{E}}_{4}}.$
(69)

We also define
$\overline{Q}_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}$
as the same expression as Equation 69 with $\mathds{1}_{{\mathcal{E}}_{4}}$
replaced with $\mathds{1}_{{\mathcal{E}}_{4}^{c}}$. Note that

$\displaystyle{Q}_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}$
$\displaystyle=P_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}-\overline{Q}_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}}^{\prime},{\mathbf{r}}^{\prime})}.$

Suppose $\operatorname{Dec}\colon{\mathcal{Y}}^{n}\to[M]$ is the (potentially
stochastic) decoder associated with ${\mathcal{C}}$. Let
$P_{\widehat{{\mathbf{m}}}|{\underline{\mathbf{y}}}}$ denote the conditional
distribution induced by $\operatorname{Dec}$. Then

$\displaystyle
P_{{\mathrm{e}},\mathrm{avg}}(\operatorname{Enc},\operatorname{Dec},\mathrm{Jam})=\sum_{(m,r),(m^{\prime},r^{\prime}),{\underline{y}}}Q_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}},{\mathbf{r}}^{\prime})}({\underline{y}},(m,r),(m^{\prime},r^{\prime}))\sum_{\widehat{m}\neq
m}P_{\widehat{{\mathbf{m}}}|{\underline{\mathbf{y}}}}(\widehat{m}|{\underline{y}})$
$\displaystyle\geq\sum_{(m,r),(m^{\prime},r^{\prime}),{\underline{y}}}\left(P_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}},{\mathbf{r}}^{\prime})}({\underline{y}},(m,r),(m^{\prime},r^{\prime}))-\overline{Q}_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}},{\mathbf{r}}^{\prime})}({\underline{y}},(m,r),(m^{\prime},r^{\prime}))\right)\mathds{1}_{{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}}\sum_{\widehat{m}\neq
m}P_{\widehat{{\mathbf{m}}}|{\underline{\mathbf{y}}}}(\widehat{m}|{\underline{y}})$
$\displaystyle=\sum_{(m,r),(m^{\prime},r^{\prime}),{\underline{y}}}P_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}},{\mathbf{r}}^{\prime})}({\underline{y}},(m,r),(m^{\prime},r^{\prime}))\mathds{1}_{{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}}\sum_{\widehat{m}\neq
m}P_{\widehat{{\mathbf{m}}}|{\underline{\mathbf{y}}}}(\widehat{m}|{\underline{y}})$
$\displaystyle\qquad-\sum_{(m,r),(m^{\prime},r^{\prime}),{\underline{y}}}\overline{Q}_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}},{\mathbf{r}}^{\prime})}({\underline{y}},(m,r),(m^{\prime},r^{\prime}))\mathds{1}_{{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}}\sum_{\widehat{m}\neq
m}P_{\widehat{{\mathbf{m}}}|{\underline{\mathbf{y}}}}(\widehat{m}|{\underline{y}}).$

The second term can be upper bounded as follows:

$\displaystyle\sum_{(m,r),(m^{\prime},r^{\prime}),{\underline{y}}}\overline{Q}_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}},{\mathbf{r}}^{\prime})}({\underline{y}},(m,r),(m^{\prime},r^{\prime}))\mathds{1}_{{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}}\sum_{\widehat{m}\neq
m}P_{\widehat{{\mathbf{m}}}|{\underline{\mathbf{y}}}}(\widehat{m}|{\underline{y}})$
$\displaystyle\leq\sum_{(m,r),(m^{\prime},r^{\prime}),{\underline{y}}}\overline{Q}_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}},{\mathbf{r}}^{\prime})}({\underline{y}},(m,r),(m^{\prime},r^{\prime}))\mathds{1}_{{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}}$
$\displaystyle=\Pr\left[{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}\cap{\mathcal{E}}_{4}^{c}\right]$
$\displaystyle=\Pr\left[{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}\right]\Pr\left[{\mathcal{E}}_{4}^{c}\,|\,{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}\right].$

For the first term, we have

$\displaystyle\sum_{(m,r),(m^{\prime},r^{\prime}),{\underline{y}}}P_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}},{\mathbf{r}}^{\prime})}({\underline{y}},(m,r),(m^{\prime},r^{\prime}))\mathds{1}_{{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}}\sum_{\widehat{m}\neq
m}P_{\widehat{{\mathbf{m}}}|{\underline{\mathbf{y}}}}(\widehat{m}|{\underline{y}})$
$\displaystyle=\sum_{(m^{\prime},r^{\prime}),(m,r),{\underline{y}}}P_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}},{\mathbf{r}}^{\prime})}({\underline{y}},(m^{\prime},r^{\prime}),(m,r))\mathds{1}_{{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}}\sum_{\widehat{m}\neq
m^{\prime}}P_{\widehat{{\mathbf{m}}}|{\underline{\mathbf{y}}}}(\widehat{m}|{\underline{y}})$
$\displaystyle=\sum_{(m,r),(m^{\prime},r^{\prime}),{\underline{y}}}P_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}},{\mathbf{r}}^{\prime})}({\underline{y}},(m,r),(m^{\prime},r^{\prime}))\mathds{1}_{{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}}\sum_{\widehat{m}\neq
m^{\prime}}P_{\widehat{{\mathbf{m}}}|{\underline{\mathbf{y}}}}(\widehat{m}|{\underline{y}}).$

Therefore,

$\displaystyle
2\sum_{(m,r),(m^{\prime},r^{\prime}),{\underline{y}}}P_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}},{\mathbf{r}}^{\prime})}({\underline{y}},(m,r),(m^{\prime},r^{\prime}))\mathds{1}_{{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}}\sum_{\widehat{m}\neq
m}P_{\widehat{{\mathbf{m}}}|{\underline{\mathbf{y}}}}(\widehat{m}|{\underline{y}})$
$\displaystyle\geq\sum_{(m,r),(m^{\prime},r^{\prime}),{\underline{y}}}P_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}},{\mathbf{r}}^{\prime})}({\underline{y}},(m,r),(m^{\prime},r^{\prime}))\mathds{1}_{{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}}\left(\sum_{\widehat{m}\neq
m}P_{\widehat{{\mathbf{m}}}|{\underline{\mathbf{y}}}}(\widehat{m}|{\underline{y}})+\sum_{\widehat{m}\neq
m^{\prime}}P_{\widehat{{\mathbf{m}}}|{\underline{\mathbf{y}}}}(\widehat{m}|{\underline{y}})\right).$
(70)

Note that

$\displaystyle\sum_{\widehat{m}\neq
m}P_{\widehat{{\mathbf{m}}}|{\underline{\mathbf{y}}}}(\widehat{m}|{\underline{y}})+\sum_{\widehat{m}\neq
m^{\prime}}P_{\widehat{{\mathbf{m}}}|{\underline{\mathbf{y}}}}(\widehat{m}|{\underline{y}})$
$\displaystyle=\sum_{\widehat{m}}P_{\widehat{{\mathbf{m}}}|{\underline{\mathbf{y}}}}(\widehat{m}|{\underline{y}})\left(\mathds{1}{\left\\{\widehat{m}\neq
m\right\\}}+\mathds{1}{\left\\{\widehat{m}\neq m^{\prime}\right\\}}\right)$
$\displaystyle\geq\min_{\widehat{m}}\left\\{\mathds{1}{\left\\{\widehat{m}\neq
m\right\\}}+\mathds{1}{\left\\{\widehat{m}\neq m^{\prime}\right\\}}\right\\}$
$\displaystyle=\mathds{1}{\left\\{m\neq m^{\prime}\right\\}}.$ (71)

Substituting Equation 71 into Equation 70, we get

$\displaystyle
2\sum_{(m,r),(m^{\prime},r^{\prime}),{\underline{y}}}P_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}},{\mathbf{r}}^{\prime})}({\underline{y}},(m,r),(m^{\prime},r^{\prime}))\mathds{1}_{{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}}\sum_{\widehat{m}\neq
m}P_{\widehat{{\mathbf{m}}}|{\underline{\mathbf{y}}}}(\widehat{m}|{\underline{y}})$
$\displaystyle\geq\sum_{(m,r),(m^{\prime},r^{\prime}),{\underline{y}}}P_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}},{\mathbf{r}}^{\prime})}({\underline{y}},(m,r),(m^{\prime},r^{\prime}))\mathds{1}_{{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}}\mathds{1}{\left\\{m\neq
m^{\prime}\right\\}}$
$\displaystyle=\sum_{(m,r),(m^{\prime},r^{\prime}),{\underline{y}}}P_{{\underline{\mathbf{y}}},({\mathbf{m}},{\mathbf{r}}),({\mathbf{m}},{\mathbf{r}}^{\prime})}({\underline{y}},(m,r),(m^{\prime},r^{\prime}))\mathds{1}_{{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}}$
(72)
$\displaystyle=\Pr\left[{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}\right].$

In Equation 72, we remove $\mathds{1}{\left\\{m\neq m^{\prime}\right\\}}$
since the event coincides with ${\mathcal{E}}_{2}$. Finally, the overall error
probability is at least

$\displaystyle
P_{{\mathrm{e}},\mathrm{avg}}(\operatorname{Enc},\operatorname{Dec},\mathrm{Jam})$
$\displaystyle\geq\frac{1}{2}\Pr\left[{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}\right]-\Pr\left[{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}\right]\Pr\left[{\mathcal{E}}_{4}^{c}\,|\,{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}\right]$
$\displaystyle\geq\frac{1}{2}\Pr\left[{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\cap{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}\right]\left(1-2\cdot
e^{-\Omega(\delta^{2}n)}\right)$
$\displaystyle=\frac{1}{2}\Pr\left[{\mathcal{E}}_{0}\right]\Pr\left[{\mathcal{E}}_{1}\,|\,{\mathcal{E}}_{0}\right]\Pr\left[{\mathcal{E}}_{2}\cap{\mathcal{E}}_{3}\,|\,{\mathcal{E}}_{0}\cap{\mathcal{E}}_{1}\right]\left(1-e^{-\Omega(\delta^{2}n)}\right)$
$\displaystyle\geq\frac{c}{2}\cdot\frac{\delta}{4}\cdot\frac{1}{N^{2}}\left(\frac{\delta}{2}-\frac{1+\log
N}{n}\right)^{N-1}\cdot\left(1-e^{-\Omega(\delta^{2}n)}\right).$

This finishes the proof of Lemma 18. ∎

##  Appendix A Basic tools

We recall some useful facts.

######  Lemma 19 (Markov).

If $X$ is a nonnegative random variable with mean $\mathbb{E}\left[X\right]$
then for any $a>0$ we have $\Pr\left[X\geq
a\right]\leq{\mathbb{E}\left[X\right]}/{a}$.

######  Lemma 20 (Data processing).

If $X\to Y\to Z$ is a Markov chain, then $I(X;Z)\leq I(X;Y)$.

######  Lemma 21 (Chernoff).

Let $X_{1},\cdots,X_{n}$ be independent $\\{0,1\\}$-valued random variables
and $S\coloneqq\sum_{i=1}^{n}X_{i}$. Then for any $\delta\in[0,1]$,

$\displaystyle\Pr\left[\left|S-\mathbb{E}\left[S\right]\right|\geq\delta\mathbb{E}\left[S\right]\right]$
$\displaystyle\leq
2\exp\left(-\frac{\delta^{2}}{3}\mathbb{E}\left[S\right]\right).$

## References

  * [BBT60] David Blackwell, Leo Breiman, and A. J. Thomasian.  The Capacity of a Class of Channels under Random Coding.  Ann. of Mathematical Statistics, 31(3):558–567, 1960.
  * [BS14] R. Bassily and A. Smith.  Causal Erasure Channels.  In Proc. ACM Symp. on Discrete Algorithms (SODA), Hong Kong, China, January 2014.
  * [CJL15] Zitan Chen, Sidharth Jaggi, and Michael Langberg.  A characterization of the capacity of online (causal) binary channels.  In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 287–296, 2015.
  * [CJL19] Zitan Chen, Sidharth Jaggi, and Michael Langberg.  The capacity of online (causal) $q$-ary error-erasure channels.  IEEE Transactions on Information Theory, 65(6):3384–3411, 2019\.
  * [CN88a] Imre Csiszár and Prakash Narayan.  Arbitrarily varying channels with constrained inputs and states.  IEEE Trans. Inf. Theory, 34:27–34, 1988.
  * [CN88b] Imre Csiszár and Prakash Narayan.  The Capacity of the Arbitrarily Varying Channel Revisited : Positivity, Constraints.  IEEE Trans. Inf. Theory, 34:181–193, 1988.
  * [DJL13] B.K. Dey, S. Jaggi, and M. Langberg.  Codes Against Online Adversaries: Large Alphabets.  IEEE Trans. Inf. Theory, 59:3304–3316, June 2013.
  * [DJLS10] Bikash Kumar Dey, Sidharth Jaggi, Michael Langberg, and Anand D. Sarwate.  Coding against delayed adversaries.  In International Symposium on Information Theory (ISIT), pages 285–289, 2010.
  * [DJLS13] B.K. Dey, S. Jaggi, M. Langberg, and A.D. Sarwate.  Upper Bounds on the Capacity of Binary Channels With Causal Adversaries.  IEEE Trans. Inf. Theory, 59:3753–3763, June 2013.
  * [Eri85] T. Ericson.  Exponential error bounds for random codes in the arbitrarily varying channel.  IEEE Transactions on Information Theory, 31(1):42–48, 1985.
  * [LDJ+18] Tongxin Li, Bikash Kumar Dey, Sidharth Jaggi, Michael Langberg, and Anand D Sarwate.  Quadratically constrained channels with causal adversaries.  In International Symposium on Information Theory (ISIT), pages 621–625. IEEE, 2018.
  * [LJD09] Michael Langberg, Sidharth Jaggi, and Bikash Kumar Dey.  Binary causal-adversary channels.  In International Symposium on Information Theory (ISIT), pages 2723–2727, Seoul, South Korea, June 28–July 3 2009.
  * [Maz14] Arya Mazumdar.  On the capacity of memoryless adversary.  In International Symposium on Information Theory (ISIT), pages 2869–2873, 2014.
  * [Sha48] C. Shannon.  A Mathematical Theory of Communication.  Bell System Technical Journal, 27:379–423, 623–656, 1948.
  * [SRL21] Vinayak Suresh, Eric Ruzomberka, and David J. Love.  Stochastic-adversarial channels: Online adversaries with feedback snooping.  In 2021 IEEE International Symposium on Information Theory (ISIT), pages 497–502, 2021.
  * [WBBJ19] Xishi Wang, Amitalok J Budkuley, Andrej Bogdanov, and Sidharth Jaggi.  When are large codes possible for AVCs?  In International Symposium on Information Theory (ISIT), pages 632–636, 2019.