1

Quadratically Constrained Myopic Adversarial
Channels
Yihan Zhang˚ , Shashank Vatedka˚ , Sidharth Jaggi˚ and Anand Sarwate:
of Information Engineering, The Chinese University of Hong Kong
: Dept. of Electrical and Computer Engineering, Rutgers, The State University of New Jersey
˚ Dept.

arXiv:1801.05951v1 [cs.IT] 18 Jan 2018

Abstract
We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the
transmitter and the jammer. The jamming signal is assumed to be a function of the codebook, and a noncausal but noisy observation
of the transmitted codeword. For a certain range of the noise-to-signal ratios (NSRs) of the transmitter and the jammer, we are
able to characterize the capacity of this channel under deterministic encoding. For the remaining NSR regimes, we determine
the capacity under the assumption of a small amount of common randomness (at most Oplogpnqq bits in one sub-regime, and
at most Opn2 q bits in the other sub-regime) available to the encoder-decoder pair. Our proof techniques involve a novel myopic
list-decoding result for achievability and a Plotkin-type push attack for the converse in a subregion of the NSRs, which may be
of independent interest.
A short video explaining our work is available at https://youtu.be/0015 W xhLM.

I. I NTRODUCTION AND PRIOR WORK
Consider a point-to-point communication system where a transmitter, Alice, wants to send a message to a receiver, Bob,
through a channel distorted by additive noise. She does so by encoding the message to a length-n codeword, which is fed
into the channel. The transmitted codeword is distorted by noise. Much of traditional communication and information theory
has focussed on the scenario where the noise is independent of the transmitted signal and the coding scheme. We study the
case where communication takes place in the presence of a malicious jammer (whom we call James) who tries to ensure that
Bob is unable to recover the transmitted message. The channel is a discrete-time, real-alphabet channel, and the codeword
transmitted by Alice is required to satisfy a quadratic power constraint. It is assumed that the coding scheme is known to all
three parties, and James also observes a noisy version of the transmitted signal (hence the term myopic). The jamming signal
is required to satisfy a separate power constraint, but otherwise can be a noncausal function of the noisy observation and the
coding scheme.
This problem is part of the general framework of arbitrarily varying channels (AVCs), introduced by Blackwell et al. [1]. The
quadratically constrained AVC (also called the Gaussian AVC) was studied by Blachman [2], who gave upper and lower bounds
on the capacity of the channel under the assumption that James observes a noiseless version of the transmitted codeword (a.k.a.
the omniscient adversary). The lower bound used a sphere packing argument similar to the one used to prove the GilbertVarshamov (GV) bound for binary linear codes. The upper bound was based on Rankin’s upper bound on the number of
non-intersecting spherical caps that can be placed on a sphere [3]. The quadratically constrained AVC is closely related to
the sphere-packing problem where the objective is to find the densest arrangement of ?
identical n-dimensional balls of radius
?
nN subject to the constraint that the center of each ball lies within a ball of radius nP . An exact characterization of the
capacity of this problem is not known, though inner [2] and outer bounds [4], [5] are known. At the other end of the spectrum,
Hughes and Narayan [6], and later Csiszár and Narayan [7], studied the problem with an “oblivious” James, who knows the
codebook, but does not see the transmitted codeword. They showed that if private randomness is available at the encoder, the
capacity of the oblivious adversarial channel is equal to that of an additive white Gaussian noise (AWGN) channel (where the
noise variance is equal to the power constraint imposed on James). The capacity exhibits a phase transition: The capacity is is
equal to that of the corresponding AWGN channel for N ă P , but is zero for N ě P . These omniscient and oblivious cases
are two extreme instances of the general myopic adversary that we study in this paper.
The work closest to that in this paper is by Sarwate [8], who characterized the capacity of this channel under the assumption
that James knows a noisy version of the transmitted signal, but Alice’s codebook is shared only with Bob. This can be
interpreted as a myopic channel with an unlimited amount of common randomness (or shared secret key) between Alice and
Bob. A related model was studied by Haddadpour et al. [9], who assumed that James knows the message, but not the exact
codeword transmitted by Alice. In this setup, Alice has access to private randomness which is crucially used to pick a codeword
for a given message. However, Alice and Bob do not share any common randomess. Game-theoretic versions of the problems
have also been considered in the literature, notably by Médard [10], Shafiee and Ulukus [11] and Baker and Chao [12]. Shafiee
1 This work was partially funded by a grant from the University Grants Committee of the Hong Kong Special Administrative Region (Project No. AoE/E02/08) and RGC GRF grants 14208315 and 14313116. The work of Shashank Vatedka was supported in part by CUHK Direct Grants 4055039 and 4055077.

2

Fig. 1: The setup studied in this paper.

and Ulukus [11] considered a more general two-sender scenario, while Baker and Chao [12] studied a multiple antenna version
of the problem.
Communication in the presence of a myopic jammer has also received considerable attention in the discrete-alphabet case
(see [13] and references therein). We would like to draw connections to the bit-flip adversarial problem where communication
takes place over a binary channel, and James observes the codeword through a binary symmetric channel (BSC) with crossover
probability q. He is allowed to flip at most np bits, where 0 ă p ă 1{2 can be interpreted as his “jamming power.” Dey et
al. [13] showed that when James is sufficiently myopic, i.e., q ą p, the capacity is equal to 1 ´ Hppq. In other words, he can
do no more damage than an oblivious adversary. As we will see in the present article, this is not true for the quadratically
constrained case. We will show that as long as the omniscient list-decoding capacity for Bob is greater than the AWGN channel
capacity for James, the capacity is equal to a certain myopic list-decoding capacity for Bob.
Let us formally describe the problem. The setup is illustrated in Fig. 1. Alice wants to send a message m to Bob. The message
is assumed to be uniformly chosen from t0, 1unR , where R ą 0 is a parameter called the rate. Alice and Bob additionally
have nkey bits of shared secret key, k. This key is kept private from James. Alice encodes the message m (using k) to a
codeword x P Rn , which is transmitted across the channel. Let C denote the set of all possible codewords (the codebook).
Due to potential randomness at the encoder either privately known only to the encoder (stochastic encoding) or shared secretly
with the decoder (randomized encoding), the codebook rate Rcode – n1 log |C| could be different from the message rate
? R
(which we sometimes simply refer to as the rate). The codebook must satisfy a power constraint of P ą 0, i.e. }x}2 ď nP
for all x P C. James sees z “ x ` sz , where sz is additive white Gaussian noise (AWGN) with mean zero and variance σ 2 . He
chooses a jamming vector s P Rn as a noncausal
? function of z, the codebook C, and private randomness. The jamming vector
is also subject to a power constraint: }s}2 ď nN for some N ą 0. Bob obtains y “ x ` s, and decodes this to a message
p The message is said to have been conveyed reliably if m
p “ m. The probability of error, Pe , is defined as the probability
m.
p ‰ m, where the randomness is over sz , the key k, and the private random bits available to James. In all our code
that m
constructions1 , we will assume that Alice and Bob may share a secret key, but the mapping from pm, kq to x is deterministic.
In other words, Alice does not possess any source of additional private randomness. Conversely, all our impossibility results
are robust to the presence of private randomness at the encoder (since in some AVC scenarios, private randomness is known
to boost capacity — e.g. [14]) We will study the problem with different amounts of common randomness shared by Alice and
Bob and unknown to James, and present results in each case.
We say that a rate R ą 0 is achievable if there exists a sequence (in increasing n) of codebooks for which the probability
of error goes to zero as n Ñ 8. The supremum of all achievable rates is called the capacity of the channel.
II. O RGANIZATION OF THE PAPER
We give a summary of our results and proof techniques in Sec. III. These are also compactly summarized in Table I. Notation
and preliminaries are described in Sec. VI. This is followed by a formal description of results. In Sec. VIII, we describe Sarwate’s
results for infinite common randomness and give a formal proof of the converse. Sec. IX contains our results with linear and
1 An exception is Appendix B, where we show that private randomness does not increase the capacity of the omniscient adversarial channel. However, we
have reason to believe (albeit unsupported by formal proof) that additional private randomness may increase the achievable rate — this is part of our ongoing
investigation.

3

Fig. 2: Capacity of the myopic adversarial channel for nkey “ 8 [8]. The x-axis denotes the NSR from Alice to Bob (with
noise from James) and the y-axis denotes NSR from Alice to James (with AWGN added).

(a)

(b)

Fig. 3: Achievable rates for myopic list-decoding for (a) nkey “ 0 and (b) nkey “ 0.2n bits of common randomness.
logarithmic amounts of common randomness with Lemmas IX.5 and IX.6 summarizing the results. Our results on list-decoding
are described in Sec. IX-A, with Theorem X.1 giving the main result. Results with deterministic encoding are presented in
Sec. X. Sec. XI contains a detailed proof of Theorem IX.3, and Sec. XII gives the proof of Theorem X.1. Appendix B has a
note on why private randomness does not improve the capacity if James is omniscient. Some of the technical details of proofs
appear in the other appendices. Frequently used notation is summarized in Table II.
III. OVERVIEW OF RESULTS AND PROOF TECHNIQUES
A. Results
We now briefly describe our results and proof techniques. It is helpful to visualize our results using a N {P versus σ 2 {P
plot similar to the one shown in Fig. 2. Sarwate [8] showed that
ˆ with an infinite?amount of˙common randomness, the capacity
is RLD –

1
2

log

P
N

in the red region, and RLD,myop –

1
2

log

pP `σ 2 qpP `N q´2P
N σ2

N pP `σ 2 q

in the blue region2 . The capacity

is zero in the grey region.
In this article, we derive results for three different regimes of common randomness: (1) nkey “ Θpnq, (2) nkey “ Θplog nq,
and (3) nkey “ 0.
‚ We prove a general result for list-decoding in presence of a myopic adversary. For an omniscient adversary, the listP
decoding capacity is RLD “ 21 log N
. This is a folklore result, but we give a proof of this statement in Appendix C for
completeness. When the adversary is myopic, and the encoder-decoder pair share Opnq bits of common randomness, we
2 The authors would like to take this opportunity to point out an error in [8], in which it was claimed (without proof) that the capacity even with an infinite
amount of common randomness equals zero when N {P ą 1. This is incorrect.

4

Region where
upper and lower bounds
do not match

Fig. 4: Capacity with nkey “ 0.2n. We have a complete characterization in the solid regions but nonmatching upper and lower
bounds in the dotted regions.
2

P
give achievable rates for list-decoding. This is equal to RLD for σP ď N
´ 1, and is larger than RLD in a certain regime
2
P
σ
(depending on the amount of common randomness) where P ą N ´ 1. The achievable rates are illustrated in Fig. 3.
With no common randomness, we can achieve RLD and RLD,myop in the red and blue regions of Fig. 3a respectively.
If Alice and Bob share nkey bits, then RLD,myop is achievable in a larger region. For instance, if nkey “ 0.2n, then the
blue region can be expanded to give Fig. 3b.
‚ When common randomness is present, we combine our list-decoding result with [15, Lemma 13] to give achievable rates
for reliable communication over the myopic adversarial channel. Let us first discuss
the˘ case the amount of common
`
randomness is linear in n, i.e., nkey “ nRkey for some Rkey ą 0. If Rkey ě 21 log 1 ` σP2 ´ RLD,myop , then we are able
to give a complete characterization
`
˘of the capacity of the channel for all values of the NSRs. We can achieve everything
in Fig. 2. If Rkey ă 21 log 1 ` σP2 ´ RLD,myop , then we are able to characterize the capacity in only a sub-region of
the NSRs. This is illustrated in Fig. 4 and Fig. 5 for different amounts of Rkey . In the dotted regions, we only have
nonmatching upper and lower bounds. It is worth pointing out that no fixed Rkey will let us achieve RLD,myop in the
entire blue region of Fig. 2. However, for every point in the blue region, there exists a finite value of Rkey such that
RLD,myop is achievable at that point. In other words, an Rkey “ Opnq is sufficient to achieve RLD,myop at every point in
the interior of the blue region in Fig. 2.
‚ For the nkey “ Θplog nq case, we are able to find the capacity in the red and blue regions in Fig. 6. In the dotted regions,
we have nonmatching upper and lower bounds.
‚ For nkey “ 0, we require a more involved approach to find the capacity. We use some of the results on myopic listdecoding in our bounds for the probability of error. We find the capacity in the red, blue and grey regions in Fig. 7, but
only have nonmatching upper and lower bounds in the dotted green and white regions.
‚ We show that if James is omniscient, then private randomness at the encoder does not help improve the capacity. This is
based on a similar observation made by Dey et al. [14] for the bit-flip adversarial channel. See Appendix B for details.
The variation of the regions of the noise-to-signal ratios (NSR) where we can obtain achievable rates is illustrated in Fig. 8. As
seen in the figure, even Θplog nq bits of common randomness is sufficient to ensure that the red and blue regions are expanded.
An additional Θpnq bits can be used to expand the blue region even further, eventually achieving everything in Fig. 2. The

5

Fig. 5: Capacity with nkey “ n.
rates derived in this paper are compared with prior work in Table I.3
B. Proof techniques for converse results
We begin by outlining the proof techniques used in our converse results as they are easier to describe.
1) Scale-and-babble: The scale-and-babble attack is a strategy that reduces the channel from Alice to Bob into an AWGN
channel. James expends a certain amount of power in cancelling the transmitted signal, and the rest in adding independent
Gaussian noise. Since the capacity of the AWGN channel cannot be increased using common randomness, the scale-and-babble
attack gives an upper bound that is valid for all values of nkey . This technique gives us the rate region illustrated in Fig. 9.
The capacity is upper bounded by RLD in the red region, RLD,myop in the blue region, and is zero in the grey region.
We would like to remark that the scale-and-babble attack is not an original idea of this work. This proof was suggested by
Sarwate [8], and is an application of a more general technique proposed by Csiszár and Narayan [16] to convert and AVC into
a discrete memoryless channel. Nevertheless we give a complete proof to keep the paper self-contained.
2) Symmetrization attacks: Symmetrization attacks give us upper bounds on the throughput when Alice and Bob do not
share a secret key. We give two attacks for James: a z-aware symmetrization attack and a z-agnostic symmetrization attack.
In the z-aware symmetrization attack, James picks a codeword x1 from Alice’s codebook uniformly at random and independently of z. He transmits px1 ´ zq{2 — since z “ x ` sz for some vector sz with N p0, σ 2 q components, therefore Bob
receives px ` x1 ´ sz q{2. If x ‰ x1 , then Bob makes a decoding error with nonvanishing probability. This attack is inspired
by a technique used to prove the Plotkin bound for bit-flip channels. The symmetrization attack lets us prove that the capacity
2
is zero when σP ď 4 N
P ´ 2 (Fig. 10a). The z-aware attack is novel in the context of myopic channels, but is also inspired by
similar ideas in [17].
The z-agnostic symmetrization argument lets us show that the capacity is zero for N ą P (Fig. 10b). James picks a
codeword x1 as before but instead transmits s “ x1 . Bob receives x ` x1 and we can show that the probability of error is
3 Many prior works (example Medard, Sarwate, etc) also consider additional random noise on the channel from Alice to Bob. In principle the techniques
in this paper carry over directly even to that setting, but for ease of exposition we choose not to present those results.

6

Region where
upper and lower bounds
do not match

Fig. 6: Capacity with nkey “ Θplog nq.
nonvanishing. The z-agnostic symmetrization attack was used by Csiszár and Narayan [7] to show that the capacity of the
oblivious adversarial channel is zero for N ą P .
These symmetrization arguments are not valid when nkey ą 0. Indeed, we will show that strictly positive rates can be
achieved in the symmetrizable regions with even Ωplog nq bits of common randomness. However, the scale-and-babble attack
is resilient to common randomness since it involved reducing the channel into an equivalent AWGN channel, and the capacity
of the AWGN channel cannot be increased using common randomness.
Combining the the three techniques give us the upper bounds in Fig. 11.
C. Proof techniques for achievability results
The proofs in the three regimes of nkey outlined above involve some common techniques. We now give a high-level description
of some of the ideas. Fundamental to the achievability proofs is the concept of list-decoding. In all the achievability proofs,
we use random spherical codes C “ txpm,
kq : 1 ď m ď 2nR , 1 ď k ď 2nkey u, where each xpm, kq is sampled independently
?
n
and uniformly from the sphere S p0, nP q.
1) Myopic list-decoding: This is a central idea in our proofs, and a novel contribution of this work. The broad idea is that to
use myopicity to ensure that James is unable to uniquely recover the transmitted codeword. We show that if the codebook rate is
sufficiently large, then there are exponentially many codewords that potentially confuse James. Due to the confusion, no attack
strategy by James is as bad as the one he could instantiate in the omniscient case. We study the list-decoding problem, where
instead of recovering the transmitted message uniquely, Bob tries to output a polypnq sized list that includes the transmitted
codeword. Since James is myopic, we could hope to achieve rates greater than the omniscient list-decoding capacity RLD .
Even with nkey “ 0, we can achieve a higher rate, equal to RLD,myop , in the blue region in Fig. 3a. The blue region can be
expanded with a larger amount of common randomness, as seen in Fig. 3b. We will in fact show that the list-decoding capacity
is equal to Cmyop,rand if nkey is large enough.
Let us briefly outline the
? proof technique. We show that conditioned `on z, the
˘ transmitted codeword lies in a strip
approximately at a distance nσ 2 from z. If the codebook rate exceeds 12 log 1 ` σP2 , then this strip will contain exponentially
many codewords. All these codewords are roughly at the same distance from z and are therefore nearly indistinguishable from
the one actually transmitted. We operate under the assumption of a more powerful adversary who has, in addition to z, access

7

Region where
upper and lower bounds
do not match

Fig. 7: Capacity with no common randomness. Here, RGV –

1
2

´
log

P2
4N pP ´N q

¯
1tP ě2N u .

Fig. 8: Expansion of the achievable rate regions for the myopic adversarial channel with different amounts of common
randomness. A rate of RLD is achievable in the red and orange regions, whereas RLD,myop is achievable in the regions
with different shades of blue. With Ωpnq bits of common randomness, a rate of at least RLD is achievable whenever P ą N .

8

Fig. 9: Upper bounds on capacity as obtained from the scale-and-babble attack. These outer bounds are valid for all values of
nkey .

(a)

(b)

Fig. 10: Regions where the (a) z-agnostic symmetrization argument and (b) z-aware symmetrization argument gives zero
capacity. Note that these are valid only for nkey “ 0. However, they continue to hold even if the encoder has access to private
randomness.

Fig. 11: Upper bounds on capacity for nkey “ 0.

9

Fig. 12: Currently, our reverse list-decoding arguments, an integral part of our proof techniques for nkey “ 0, are only valid in
the red and blue regions, which present bottlenecks in our analysis of the scenario when no common randomness is available.
As ongoing work, we are trying to expand the region where reverse list-decoding is possible.

to an oracle. This is a matter of convenience and will greatly simplify our proofs. The oracle reveals an exponential subset of
the codewords (that includes x) from the strip. We call this the oracle-given set (OGS). We prove that for most codewords in
the OGS, no attack vector s can eventually force a list-size greater than polypnq as long as the
? rate is less than C
?myop,rand .
To prove this result, we obtain a bound on the typical area of the decoding region S n´1 p0, nP q X B n px ` s, nN q. We
will show that for certain
of the noise-to-signal ratios, the volume of the decoding region is typically much less than
? regimes
?
AreapCapn´1 px ` s, nN , nP qq. This lets us get an improvement over the omniscient list-decoding capacity.
2) Reverse list-decoding: This is a technique used to obtain achievable rates in the case where Alice and Bob
? do not
share any common randomness. Given an attack vector s, we say that x1 confuses x if x1 lies within B n px ` s, nN q. In
list-decoding, we attempt to find the number of codewords that could potentially confuse the transmitted codeword. Our goal
in the list-decoding problem is to keep the number of confusable codewords to a minimum. In reverse list-decoding, we ask
the opposite question: Given a potentially confusing codeword, how many codewords in the strip could this confuse??
For every codeword x1 and attack vector s, we could define the reverse list-size as |tx P Str : }x ` s ´ x1 }2 ď nN u|.
In other words, this is the number of codewords in the strip which when translated by s, are confusable with x1 . Our goal is
to keep this as small as possible (in fact,
` polypnq)
˘ for all possible attack vectors s. We show that small reverse list-sizes are
P
guaranteed as long as 21 log N
ą 12 log 1 ` σP2 , i.e. in red and blue regions of Fig. 12.
3) Going from list-decoding to unique decoding: Obtaining results for unique decoding uses two different approaches that
depends on the amount of common randomness.
‚ Linear/logarithmic amount of common randomness: Langberg [18] gave a combinatorial technique to convert any listdecodable code (with no common randomness) for a binary channel into a uniquely decodable code with Ωplog nq bits of
common randomness. This was later generalized by Sarwate [15] to arbitrary AVCs. This when combined with our result
on myopic list-decoding will give us an achievable rate for reliable communication over the myopic channel.
‚ No common randomness: The ideas in myopic list-decoding can be used to show that there are at most polypnq codewords
that can potentially confuse the exponentially many codewords in the OGS. Using reverse list-decoding, we can conclude
that each codeword outside the OGS can confuse at most polypnq codewords in the OGS. Using this, and a “grid argument”
along the lines of [13], we can show that the probability of decoding error is vanishingly small.
4) Two uses of the common randomness: When Alice and Bob have only Oplog nq bits of common randomness, k is only
used to find the true message from the list using the approach proposed in [18], [15]. However, when Alice and Bob have
Ωpnq bits of shared secret key, there are two different uses for k.
Recall from our discussion above that to obtain an improvement over omniscient list-decoding, we must ensure that James is
sufficiently confused about the true codeword. If he can recover x with high probability, then there would be no hope of achieving
rates greater than RLD . When Alice and Bob share linear amounts of common randomness, all but a Oplog nq amount of this
is used to ensure that the strip contains exponentially many codewords. This is done by generating 2nkey ´Θplog nq independent
codebooks, each containing 2nR codewords. Based on the realization of the key, Alice picks the appropriate codebook for
encoding. Since Bob knows the key, he can use this codebook for decoding. However, James does not have access to the
shared secret key and to him, all the 2nR`nkey ´Θplog nq codewords are equally likely to have been transmitted. This ensures
that James is sufficiently confused about the true codeword. The remaining Oplog nq bits are then used to disambiguate the
list at the decoder.

10

Bounds on the capacity of the adversarial channel with quadratic constraints
5
Cobli
4.5

RRankin

4

RGV

3.5

CLD

RLP

Rate

3
2.5
2
1.5
1
0.5
0
0

0.2

0.4

0.6
0.8
N/P (NSRBob)

1

1.2

1.4

Fig. 13: Achievable rates for the quadratically constrained adversarial channel — prior work.

IV. C OMPARISON WITH OTHER WORK
We now describe the similarities and differences with three closely related works.
Sarwate [8] derived the capacity of the myopic adversarial channel with unlimited common randomness. Our ideas are
inspired by this work, although the techniques used are different. This is in some sense a continuation of [8], with a restriction
on the amount of shared secret key. In [8], the codebook was privately shared by Alice and Bob. A minimum angle decoder
was used, and the achievable rate was the solution to an optimization problem identical to what we obtain in our analysis of
myopic list-decoding. The converse used the scale-and-babble attack that we describe in a subsequent section. When Alice
and Bob share Ωpnq bits of common randomness, we find that the upper bound is indeed optimal. We were unable to obtain
an improved improved upper bound for smaller amounts of common randomness. However, we do give an improved converse
for certain NSRs using symmetrization when there is no common randomness shared by the encoder-decoder pair.
Dey et al. [13] studied the discrete myopic adversarial channel. We borrow several proof techniques from their paper to
obtain results when nkey “ 0. This includes the ideas of blob list-decoding, reverse list-decoding, and the grid argument to
prove that the probability of error is vanishingly small even when transmitting at rates above RGV , despite the fact that the
jamming pattern may be correlated with the transmission. However, there are several differences between our work and the
discrete case. A key difference between this work and [13] is our use of myopic list-decoding. A direct extension of the
P
techniques in [13] would only let us achieve rates up to the omniscient list-decoding capacity 12 log N
. The study of myopic
list-decoding is novel, and is one of the main contributions of this work. Furthermore, the random variables involved in this
work are continuous which introduces several challenges. Several arguments involving union bounds and fixed distances do
not go through directly from the discrete setting. We overcome some of these by quantizing the relevant random variables,
a standard trick to reduce the continuous variables to discrete. In [13], the oracle-given set was chosen to be a subset of
codewords all at the same distance from the vector received by James. All codewords in the OGS would then have the same
posterior probability given James’ observation and the OGS. As sz is Gaussian in our case, such an argument cannot be used.
Instead, we choose the OGS from a thin strip. Given z and the OGS, the codewords are not uniformly distributed. However,
we carefully choose the thickness of the strip to be small enough to ensure that this posterior distribution is close to being
uniform. Due to the random variables being continuous, dealing with the quadratically constrained case requires a more careful
analysis involving many more slackness parameters than the discrete analog.
The symmetrization argument we use in Section X-2 is inspired by the “scaled babble-and-push” attack studied by Li et
al. [17]. This studies the attack where James generates an independent codeword x1 and transmits px1 ´ zq{2, and lets us prove
that the capacity is zero in the regime where σ 2 {P ă 4N {P ´ 2.
We could extend this idea, along the lines of the scaled babble-and-push attack [17] in the following manner. In a subset
of codeword indices, James uses the scale-and-babble attack. In the remaining indices i, he transmits px1i ´ zi q{2. We could
2
P
hope to get an improved converse in the regime 1 ď N
ď 1 ` σP ď N {P1 ´1 . We were unsuccessful in analyzing this and it
has been left as future work.
V. N OTATION
Random variables are denoted by lower case Latin letters in boldface, e.g., m, x, s, etc. Their realizations are denoted by
corresponding letters in plain typeface, e.g., m, x, s, etc. Vectors of length n, where n is the block-length, are denoted by lower
case Latin letters with an underline, e.g., x, s, x, s, etc. The i-th entry of a vector is denoted by a subscript i, e.g., xi , si , xi , si ,
etc. Matrices are denoted by capital Latin letters in boldface.

11

Reference

Rate

Folklore
(Appendix C)

RLD –

HughesNarayan [6]
CsiszárNarayan [7]
Blachman [2]
KabatianskyLevenshtein [4]

1
2

´
log

P
N

¯
for list-decoding

Cobli,rand – CAWGN –

1
2

´

P
N

log 1 `

¯

Cobli – CAWGN 1tP ěN u

where α –

P `2
4

?

1
2

N pP ´N q

N pP ´N q
1
log
2

,β–
´ ¯

P ´2
4

?

σ2 “ 0

0

σ2 “ 8

8

σ2 “ 8

0

σ2 “ 0

0

σ2 “ 0

0

N pP ´N q

ˆ
Cmyop,rand “ RLD,myop –

N pP ´N q

P
N

Cmyop,rand “ RLD –
Sarwate [8]

Common
randomness

¯

P
log 2N
1tP ě2N u
´
¯
P2
1tP ě2N u
ě RGV – 21 log 4N pP
´N q
ď RLP – ?
pα log α ´ β log βq1tP?ě2N u ,

Comni ď RRankin –
Comni
Comni

´

Level of myopicity

1
2

log

2

pP `σ qpP `N q´2P
N σ2

?

N pP `σ 2 q

˙

Cmyop,rand “ 0

ď

σ2
P

ě max

σ2
P

ď

1
N {P

N
P

´1
!

1
N {P

´ 1,

N
P

Cmyop “ RLD,myop
RGV ď Cmyop ď RLD
RGV ď Cmyop ď RLD,myop
Cmyop “ 0
Cmyop “ RLD
Cmyop “ RLD,myop
RLD ď Cmyop ď RLD,myop
Cmyop “ 0
Cmyop “ RLD
Cmyop “ RLD,myop

RLD ď Cmyop ď RLD,myop

σ2
P

Cmyop “ 0

ď

N
P

8

)
´1

´1

2
1
´ 1 ď σP ď N1{P ´ 1
1´N {P
!
)
2
1
σ
ě max N1{P ´ 1, 1´N
´1
P
{P
!
)
2
1
4N
´ 2 ď σP ď min N1{P ´ 1, 1´N
´1
P !
{P
)
2
1
max N1{P ´ 1, 4 N
´ 2 ď σP ď 1´N
´1, N
P
{P
P
2
σ
ď 4N
´ 2 or N
ě1
P
P
P
σ2
ď N1{P ´ 1
P
!
)
σ2
ě max N1{P ´ 1, 4 N
´1
P
!
)P
2
max N1{P ´ 1, N
´ 1 ď σP ď 4 N
´1
P
P
σ2
N
ď
´
1
P
P
σ2
ď N1{P ´ 1
P
!
)
σ2
ě max N1{P ´ 1, N
´1 ,
P
P
¯
´
and Rkey ą 12 log 1 ` σP2 ´ RLD,myop
!
)
σ2
ě max N1{P ´ 1, N
´1 ,
P
´ P ¯
and Rkey ă 12 log 1 ` σP2 ´ RLD,myop

Cmyop “ RLD

This work

σ2
P

0
ď1

Θplog nq

nRkey

´1

TABLE I: Summary of known results for the adversarial channel with quadratic constraints. Here, 1tP ěN u is 1 when P ě N
and zero otherwise. Rates known in prior work are plotted in Fig. 13.

Capacity with Ω(n) bits of common randomness
3.5
NSRJames = 10.0
NSRJames = 1.5
NSRJames = 0.3

3

2.5

Rate

2

1.5

1

0.5

0
0

0.2

0.4

0.6

0.8

1
1.2
N/P (NSRBob)

1.4

1.6

1.8

2

Fig. 14: Capacity of the myopic adversarial channel with Ωpnq bits of common randomness. Here NSRJames – σ 2 {P .

12

Fig. 15: Capacity of the myopic adversarial channel with different amounts of common randomness. Here, RN C pnkey q denotes
the region where our upper and lower bounds do not meet.
Capacity with Θ(log(n)) bits of common randomness
1.2
N/P=1.0
N/P=0.75
N/P=0.5
N/P=0.2

1.1
1
0.9

Rate

0.8
0.7
0.6
0.5
0.4
0.3
0.2
0

5

10
σ2/P

15

20

Fig. 16: Capacity of the myopic adversarial channel as a function of σ 2 {P .

Sets are denoted by capital Latin letters in calligraphic typeface, e.g., C, I, etc. In particular, an pn ´ 1q-dimensional sphere
in Euclidean space centered at x of radius r is denoted by
S n´1 px, rq “ ty P Rn : }y}2 “ ru.
An n-dimensional ball in Euclidean space centered at x of radius r is denoted by
B n px, rq “ ty P Rn : }y}2 ď ru.
As shown in Figure 17a, an pn ´ 1q-dimensional cap centered at x of radius r living on an pn ´ 1q-dimensional sphere of
radius r1 is denoted by
Capn´1 px, r, r1 q “ ty P S n´1 pr1 q : }y ´ x}2 ď ru
“ B n px, rq X S n´1 pO, r1 q.
As shown in Figure 17b, an pn ´ 1q-dimensional strip centered at x´ and x` of radii r´ and r` is denoted by
Strn´1 px´ , x` , r´ , r` q “tx P S n´1 prq : }x ´ x´ }2 ě r´ , }x ´ x` }2 ď r` u
“B n px´ , r´ qc X B n px` , r` q X S n´1 pO, rq,

13

(a) An pn ´ 1q-dimensional cap Capn´1 px, r, r1 q centered
n´1
px´ , x` , r´ , r` q
at x of radius r living on an pn ´ 1q-dimensional sphere of (b) An pn ´ 1q-dimensional strip Str
1
centered
at
x
and
x
of
radii
r
and
r` .
radius r .
´
`
´

Fig. 17: The geometry of caps and strips.
b
b
2 ´
2 “ |x x |. An n-dimensional shell centered at x of inner radius r and outer radius
where r satisfies r2 ´ r´
r2 ´ r`
´ `
in
rout , where rout ą rin , is denoted by
˙
ˆ
rin ` rout
rout ´ rin
˘
Shn px, rin , rout q “Shn x,
2
2
n
n
“B px, rout qzB px, rin q.
Let Areap¨q denote the Lebesgue area of an Euclidean surface and let Volp¨q denote the Lebesgue volume of a Euclidean body.
For M P Zą0 , we let rM s denote the set of first M positive integers t1, 2, ¨ ¨ ¨ , M u.
The probability mass function of a discrete random variable x or a random vector x is denoted by px or px . Here with a
slight abuse the notation, we use the same to denote the probability density function (p.d.f.) of x or x if they are continuous.
If every entry of x is independently and identically distributed (i.i.d.) according to px , then we write x „ pbn
x . In other words,
px pxq “ pbn
x pxq –

n
ź

px pxi q.

i“1

Let U pΩq denote the uniform distribution over some probability space Ω. Let N pµ, Σq denote the n-dimensional Gaussian
distribution with mean vector µ and covariance matrix Σ.
The indicator function is defined as, for any A Ď Ω and x P Ω,
#
1, x P A
.
1A pxq “
0, x R A
At times, we will slightly abuse notation by saying that 1A is 1 when relation A is satisfied and zero otherwise. We use
standard Bachmann-Landau (Big-Oh) notation for asymptotic functions. All logarithms are to the base two.
We use Hp¨q to denote interchangeably Shannon entropy and differential entropy; the exact meaning will usually be clear
from context.
VI. P RELIMINARIES
Arbitrarily Varying Channel (AVC). A channel with a state controlled by an adversarial jammer is called an AVC in the
literature. James’ jamming strategy is a (potentially probabilistic)
map which, based on his observation, constructs an attack
?
vector s satisfying his maximum power constraint }s}2 ď nN ,
J : Rn
z

Ñ Rn
.
Þ
Ñ
s

Code. An deterministic encoder is a deterministic map which encodes a message to a codeword of length
? n, where n is called
block-length or the number of channel uses, satisfying Alice’s maximum power constraint }xpmq}2 ď nP ,
Enc : t0, 1unR
m

Ñ Rn
,
Þ
Ñ
xpmq

where R is the rate of the system. Alice uses her encoder to encode the set of messages t0, 1unR and get a codebook
nR
txpmqu2m“1 which is simply the collection of codewords.

14

A deterministic decoder is a deterministic function which matches Bob’s observation to a reconstruction of the message,
Dec : Rn
y

Ñ t0, 1unR
.
p
ÞÑ m

A pn, R, P, N q-deterministic-code C is an deterministic encoder/decoder pair pEnc, Decq. Sometimes we also slightly abuse
2nR
the notation and call the set of codewords txpmqum“1
a code.
We distinguish between three types of codes:
nR
‚ Deterministic codes: The encoder is a deterministic map from t0, 1u
to Rn , and the decoder is a deterministic map
n
nR
from R to t0, 1u .
‚ Stochastic codes: The encoder and decoder are allowed to use private randomness. If Alice and Bob has nA and nB bits
of private randomness respectively, then a stochastic encoder is a map
Enc : t0, 1unR ˆ t0, 1unA
pm, kA q
while the decoder is a map

‚

Dec : Rn ˆ t0, 1unB
py, kB q

Ñ Rn
,
ÞÑ xpm, kq

Ñ t0, 1unR
.
p
ÞÑ m

Here, kA is known only to Alice while kB is known only to Bob.
Randomized codes: Alice and Bob share nkey “ nRkey bits of common randomness, which is kept secret from James.
They may additionally have nA and nB bits of private randomness respectively. The encoder is a map
Enc : t0, 1unR ˆ t0, 1unA ˆ t0, 1unkey
pm, kA , kq
while the decoder is a map

Dec : Rn ˆ t0, 1unB ˆ t0, 1unkey
py, kB , kq

Ñ Rn
,
Þ
Ñ
xpm, kA , kq
Ñ t0, 1unR
.
ÞÑ m
p

Here, k is known to Alice and Bob, but not to James. The private randomness kA is known only to Alice, while kB is
known only to Bob.
In all our code constructions, we will not use any private randomness, i.e., nA “ nB “ 0. However, our converse results are
true for all values of nA and nB .
Probability of error. A decoding error occurs when Bob’s reconstruction does not match Alice’s message. The average (over
messages) probability of error Peavg (also denoted by Pe for notational brevity in this paper) is defined as
p ‰ mq “
Pe “ Ppm

nR
2ÿ

m“1

p ‰ m, m “ mq “
Ppm

1
2nR

nR
2ÿ

p ‰ m|m “ mq.
Ppm

m“1

where the probability is taken over the private randomness in the encoder/decoder, the common randomness shared by Alice
and Bob, the noise to James, and any additional randomness he may use in choosing s. For deterministic codes,
p ‰ m|m “ mq
Ppm
ż
ż
“
pz|x pz|xpmqqps|z ps|zq1tDecpxpmq`sq‰mu dz ds.
?
n
Bn p0, nN q R

For stochastic codes,
p ‰ m|m “ mq
Ppm
ż ÿ
ż
ÿ
“
kB

pz|x pz|xpm, kA qqps|z ps|zq1tDecpxpm,kA q`s,kB q‰mu dz ds.

?
n kA
Bn p0, nN q R

For randomized codes,
p ‰ m|m “ mq
Ppm
ż
ż ÿÿ
ÿ
“
kB

?

Bn p0, nN q

Rn

kA k

pz|x pz|xpm, kA , kqqps|z ps|zq1tDecpxpm,kA ,kq`s,kB ,kq‰mu dz ds.

15

Rate and capacity. A rate R is said to be achievable if there exists a sequence of pn, R, P, N q-codes C pnq labelled by blockpnq
length n such that each code in the sequence has rate Rpnq at least R and average probability of error Pe vanishing in n,
i.e.,
@n, Rpnq ě R, and lim Pepnq “ 0.
nÑ8

The capacity C of a communication system is the supremum of all achievable rates.
Remark VI.1. While sticking with maximum power constraint and average probability of error, we will strictly distinguish
between different criteria for James’ power constraints and Bob’s probability of error.
1) Maximum vs. average power constraint for James. We will not use average power constraint for James. Otherwise, no
positive rate is achievable under both maximum and average probability of error. This is because James can focus only
on a small constant fraction of codewords and allocate large enough power to completely corrupt them to ensure Bob has
no hope to decode them. Then Bob’s (maximum/average) probability of error is bounded away from zero while James’
jamming strategy still satisfies his average power constraint.
2) Maximum vs. average probability of error. As we know, in information theory, an achievability result under maximum
probability of error is stronger than that under average one, while it is the other way round for a converse result. In
adversarial channel model, if we adopt maximum probability of error, notice that it suffices for James to corrupt the
transmission of only one message. Thus we may assume that James knows the transmitted message a priori (but not
necessarily the transmitted codeword if Alice uses stochastic encoding where a message potentially corresponds to a bin
of codewords). This can be done by an AWGN-like attack.
More formal justification of these criteria and their effect on capacity is given in Hughes–Narayan [6]. The authors defined
the notion λ-capacity for different criteria.
Probability distributions of interest. Alternatively, the system can be described using probability distributions. We assume the
messages are uniformly distributed, i.e., pm “ U pr2nR sq. Given the message to be transmitted, the codewords are distributed
according to px|m . Notice that it is not necessarily a 0-1 distribution, i.e., the codeword may not be entirely determined by the
message, as Alice may have access to some private randomness and use stochastic encoding. Each message may be attached
with many codewords and Alice samples one codeword according to the distribution px|m and transmits it. James receives a
corrupted version z of x through an AWGN channel specified by
bn
bn
pbn
z|x pz|xq “ pz|x px ` pz ´ xq|xq “ psz pz ´ xq,
2
where pbn
sz “ N p0, σ In q. Based on his observation, James designs an attack vector s according to his jamming strategy
specified by psz |z . Again, notice that it is not necessarily a 0-1 distribution as James may have access to private randomness
and the output of his jamming may not be deterministic. Then Bob receives y which is the sum of x and s. In particular, y
is a deterministic function of the codeword transmitted in the main channel and the attack vector added to it, i.e.,

py|x,s py|x, sq “ 1ty“x`su .
p using a (potentially stochastic) decoder specified by pm
Based on his observation, Bob reconstructs m
x |y .
Area and volume. The area of an pn ´ 1q-dimensional Euclidean sphere of radius r is given by
AreapS n´1 p¨, rqq “

2π n{2 n´1
r
.
Γpn{2q

It can be lower bounded by the volume of an pn ´ 1q-dimensional ball centered at x of radius r since the intersection of an
pn ´ 1q-dimensional sphere and an pn ´ 1q-dimensional hyperplane is an pn ´ 1q-dimensional ball, as shown in Figure 18, i.e.,
AreapCapn´1 px, r, r1 qq ě VolpB n´1 px, rqq.
The area of a cap can also be upper bounded by a sphere of the same radius, i.e.,
1
AreapS n´1 px, rqq ď AreapS n´1 px, rqq.
2
The volume of an n-dimensional Euclidean ball of radius r is given by
AreapCapn´1 px, r, r1 qq ď

VolpB n p¨, rqq “

π n{2
rn .
Γpn{2 ` 1q

More facts about high-dimensional geometry can be found in the notes by Ball [19].
Basic tail bounds. Standard tail bounds (see, for instance, the monograph by Boucheron et al. [20]) on Gaussians and χ2 distributions are used at times throughout this paper.
´
¯
2
Fact VI.2. If g „ N p0, σ 2 q, then P p|g| ě q ď exp ´ 2σ
.
2

16

Fig. 18: Approximation of surface area. The surface area of a cap Capn´1 px, r, r1 q is upper bounded by that of a sphere
S n´1 px, rq. It is lower bounded by the volume of a lower dimensional ball B n´1 px, rq since the intersection of an pn ´ 1qdimensional hyperplane parallel to the bottom of the cap passing through x and the ball B n pO, r1 q whose surface the cap lives
on is an pn ´ 1q-dimensional ball B n´1 px, rq.

Fig. 19: The geometry corresponding to the tail bound of |xa, by|.
Fact VI.3. If g „ N p0, σ 2 In q, then }g}22 has (scaled) χ2 -distribution and
ˆ 2 ˙

2
2
p}g}
ě
nσ
p1
`
qq
ď
exp
´ n ,
P
2
4
ˆ 2 ˙

2
2
Pp}g}2 ď nσ p1 ` qq ď exp ´ n ,
2
ˆ 2 ˙

2
2
Pp}g}2 R nσ p1 ` qq ď 2 exp ´ n .
4
Lemma VI.4. Fix ζ ą 0 and b P Rn . If a is isotropically distributed on the sphere S n´1 p0, }a}2 q, then
´

Pp|xa, by| ą δq ď 2

pn´1qn2 ζ 2
2
2}a}2
2 }b}2

.

Proof. Let eb denote the unit vector along b, i.e., eb “ b{}b}2 . Notice that |xa, by| ą nζ if and only if |xe, eb y| ą
if and only if e lies on one of two caps (shown in Figure 19) of height 1 ´ }a}nζ
. Thus we have
2 }b}2
˙
ˆ
nζ
Pp|xa, by| ą nζq “ P |xe, eb y| ą
}a}2 }b}2
´
´
¯¯
b
b
nζ
n2 ζ 2
n´1
2 Area Cap
,
1
´
,
1
2
2
}a}2 }b}2 }b}2
}a}2 }b}2
“
AreapS n´1 p0, 1qq
¯¯
´
´ b
2ζ2
Area S n´1 0, 1 ´ }a}n2 }b}
2
2
2
ď
AreapS n´1 p0, 1qq
¨
˚
´ n´1
2 log˝

“2

˛
1´

1
n2 ζ 2
2
}a}2
2 }b}2

‹
‚

nζ
}a}2 }b}2 ,

i.e.,

17

´

ď2

pn´1qn2 ζ 2
2
2}a}2
2 }b}2

´

1
1´x

where the last step follows from the inequality log

,

¯
ě logp1 ` xq ě x for small enough positive x.

We now state a general lemma that will be useful in proving list-decoding results. This essentially says that if codewords
are chosen i.i.d. according to a uniform distribution, then the probability that more than n3 codewords lie within any set
of sufficiently small volume is super-exponentially vanishing in n. A proof of this lemma for discrete case appeared in
Langberg’s [21, Lemma 2.1] paper. We give a general form and its proof for completeness.
nR

Lemma VI.5. Suppose A Ď Rn and C “ txpmqu2m“1 Ď A contains 2nR , R ą 0 uniform samples from A. If V Ď A such that
for some small enough constant ν ą 0
p – Ppx P V q “

µpV q
ď 2´pR`νqn ,
µpAq

nR
´νn
,
Ep|V X C|q “ p2 “ 2

where µp¨q denotes the Lebesgue measure of a measurable subset of Rn , then there exists some constant C “ Cpc, ν, Rq ą 0,
s.t.,
2
´Cn3
.
Pp|V X C| ě cn q ď 2
Proof.
nR
2ÿ

˙
nR
2nR i
p p1 ´ pq2 ´i
Pp|V X C| ě cn q “
i
i“cn2
ˆ nR ˙
2
nR
2
2
ď2nR
pcn p1 ´ pq2 ´cn
cn2
ˆ nR ˙cn2
2
2 e
nR
2´pR`νqn¨cn
ď2
2
cn
2

ˆ

“2nR`cRn
3

“2´cνn

3

`cplog eqn2 ´cn2 logpcn2 q´cpR`νqn3

´2cn2 log n`pc log e´c log cqn2 `nR

3

ď2´Cn .

Remark VI.6. The above lemma indicates that the number of codewords falling into V is small (say at most polypnq) w.h.p.
as long as we can get an exponentially small upper bound on the expected number of such codewords.
VII. O UR RESULTS
We now describe the results in this paper w.r.t. decreasing values of nkey . We start with the case when there is an unlimited
amount of common randomness available between Alice and Bob. We make no claim of novelty in this result. The achievability
was given by Sarwate [8], and he also claimed the converse. For the sake of completeness, we give the converse, which will
also be useful later.
VIII. C APACITY OF THE MYOPIC ADVERSARIAL CHANNEL WHEN Rkey “ 8
Sarwate [8] showed the following:
Lemma VIII.1 ([8]). As shown in Figure 20, the capacity of the myopic adversarial channel with an unlimited amount of
common randomness is
$
P
σ2
1
1
’
’RLD – 2 log N , ˆ
P ď N {P ´ 1
’
˙
?
&
!
)
pP `σ 2 qpP `N q´2P N pP `σ 2 q
σ2
1
N
Cmyop,rand “ RLD,myop – 12 log
.
(VIII.2)
,
ě
max
´
1,
´
1
2
Nσ
P
N {P
P
’
’
’
2
%0,
σ
N
P ď P ´1
An important point to note here is that the capacity is not necessarily zero when N ă P . As we shall see in subsequent
sections, even a small amount of common randomness can let us achieve a positive rate in parts of this region.
The achievability part of the proof uses a random coding argument. The converse can be proved by specifying an attack
for James that instantiates an AWGN channel from Alice to Bob having the capacity given by (VIII.2). The converse is quite
straightforward and was skipped in [8]. A rigorous proof is presented in the next section for completeness. We also feel that
this gives us some insight as to what optimal attack strategies for James might be, and hence give a detailed argument.

18

Σ2
3.0

P

2.5
2.0
1.5
1.0
0.5
N
0.0

0.2

0.4

0.6

0.8

1.0

1.2

1.4

P

Fig. 20: Results on Gaussian AVCs due to Sarwate [8]. For N {P ă 1 the results are identical as in this paper (though we
provide a finer characterization on the amount of common randomness needed. For N {P ě 1, [8] gave an incorrect claim that
Cmyop,rand = 0. This is corrected in this work, in Section VIII-A.
A. Proof of converse: “scale-and-babble” attack
The converse involves what we call a “scale-and-babble” attack strategy for James. This attack essentially converts the
myopic channel into an equivalent AWGN channel. Since the capacity of the AWGN channel cannot be increased using
common randomness, this gives us an upper bound on the capacity for all values of nkey . We make no claim about the
originality of this proof, as the strategy is well-known (and maybe dates back to Blachman [2], as suggested by Sarwate [8]).
But we nevertheless provide the details to keep the paper self-contained.
The strategy for James is the following: he uses a certain fraction of his power to subtract a negatively scaled version of
his observation; the remainder of his power is used to add AWGN. Specifically,
s “ β p´αz ` gq “ β p´αpx ` sz q ` gq,
where4

#
β“

1, ?

nN
}´αz`g}2

} ´ αz ` g}2 ď
1
“: β , otherwise

?

nN

(VIII.3)

,

a
α ą 0 is a constant to be optimized subject to N ´ α2 pP ` σ 2 q ě 0, i.e., α ď N {pP ` σ 2 q. Also, g „ N p0, γ 2 In q with
?
γ2
α2 pP ` σ 2 q ` 1´
“ N , for a small  ą 0. Therefore, γ 2 “ pN ´ α2 pP ` σ 2 qqp1 ´ q, and P p} ´ αz ` g}2 ą nN q “ 2´Ωpnq .
Then
#
?
x ´ αpx ` sz q ` g “ p1 ´ αqx ´ αsz ` g,
} ´ αz ` g}2 ď nN
y “x`s“
.
x ` β 1 p´αpx ` sz q ` gq “ p1 ´ β 1 αq x ´ β 1 αsz ` β 1 g, otherwise
The scaling factor β is introduced to satisfy the power constraint. Note that the channel above is not exactly an AWGN channel.
However, the probability that β ‰ 1 is exponentially small in n. We have the following claim, formally proved in Appendix D.
Claim VIII.4. Fix 0 ă  ă 1, and let α be nonnegative. If γ 2 – pN ´ α2 pP ` σ 2 qqp1 ´ q, then the capacity of the channel
(VIII.3) from x to y is upper bounded as follows
ˆ
˙
1
p1 ´ αq2 P
C ă log 1 ` 2 2
.
(VIII.5)
2
α σ ` γ2
Using Claim VIII.4, we have
ˆ
˙
ˆ
˙
1
p1 ´ αq2 P
1
p1 ´ αq2 P
log 1 ` 2 2
“
log
1
`
` gp, δS q,
2
α σ ` γ2
2
N ´ α2 P
a
where gp, δS q Ñ 0 as  Ñ 0. Since this holds for every  ą 0, and every 0 ă α ď N {pP ` σ 2 q, we can say that
ˆ
˙
1
p1 ´ αq2 P
Că
min
log
1
`
.
(VIII.6)
?
N ´ α2 P
0ăαď N {pP `σ 2 q 2
Că

4 Here,

β is a factor introduced to handle atypicality in the noise. As we show subsequently, the value of β is 1 with high probability.

19

f HΑL
3.0

f HΑL
3.0

2.5

2.5

2.0

2.0

1.5

1.5

1.0

1.0

0.5

0.5

0.0

0.2

0.4

0.6

0.8

1.0

Α

0.0

0.2

(a) f pαq with N {P “ 0.9.

0.4

0.6

0.8

1.0

Α

(b) f pαq with N {P “ 1.1.

Fig. 21: Optimization of f pαq.
2

P
1
Denote f pαq “ p1´αq
N ´α2 P and Rpαq “ 2 logp1 ` f pαqq. The minimum points of f pαq are α “ N {P, 1.
1) N {P ă 1 (See Figure 21a with P {N “ 1.1).
a
2
a) If N {P ă N {pP ` σ 2 q, i.e., σP ă N1{P ´ 1, then
ˆ ˙
1
1
P
Rpαq “ logp1 ` f pN {P qq “ log
.
?min
2
2
N
α:αď N {pP `σ 2 q
a
2
b) If N {P ě N {pP ` σ 2 q, i.e., σP ě N1{P ´ 1, then
˜
˜c
¸¸
1
N
Rpαq “ log 1 ` f
?min
2
P ` σ2
α:αď N {pP `σ 2 q
˜
¸
a
pP ` σ 2 qpP ` N q ´ 2P N pP ` σ 2 q
1
“ log
– RLD,myop .
2
N σ2

Notice that if σ Ñ 8, the channel becomes oblivious, since
˜
¸
a
ˆ
˙
pP ` σ 2 qpP ` N q ´ 2P N pP ` σ 2 q
P
1
1
“ log 1 `
,
lim log
σÑ8 2
N σ2
2
N
consistent with the oblivious capacity of quadratically constrained channels.
2) N {P ă 1 (See Figure 21b with P {N “ 0.9).
a
2
a) If N {pP ` σ 2 q ě 1, i.e., σP ď N
P ´ 1, then
α:αď

a
b) If N {pP ` σ 2 q ă 1, i.e.,

2

σ
P

ą

N
P

?min

N {pP `σ 2 q

Rpαq “

1
logp1 ` f p1qq “ 0.
2

´ 1, then

˜
˜c
¸¸
1
N
Rpαq “ log 1 ` f
“ RLD,myop .
?min
2
P ` σ2
α:αď N {pP `σ 2 q
The upper bound of capacity given by the scale-and-babble attack is shown in Figure 22.
The scale-and-babble attack converts the adversarial channel into an equivalent AWGN channel. The capacity of the pointto-point AWGN channel cannot be increased using private/common randomness. Therefore, the upper bounds obtained using
this technique hold regardless of whether deterministic/stochastic/randomized codes are used, and regardless of the amount
of common randomness shared by the encoder and decoder (since common randomness/stochastic encoding do not boost the
capacity of DMCs).
IX. L INEAR AND SUBLINEAR AMOUNTS OF COMMON RANDOMNESS
We now discuss two possibilities: (1) nkey is Θpnq, and (2) nkey is Θplog nq. The rate given by Lemma VIII.1 is an upper
bound on the capacity in both cases. We will show that this is achievable in a subregion of the NSRs. Our approach will
involve a myopic list-decoding argument, which we will prove next. We will combine this with Langberg’s [18] technique
which uses Θplog nq bits of common randomness to disambiguate the list and give us a result for unique decoding. Before we
state the main results, we take a brief detour to discuss classical and myopic list-decoding.

20

Fig. 22: The upper bound of capacity given by scale-and-babble attack.

A. List-decoding
Consider the quadratic adversarial channel model where James observes z, which is a noisy copy of x. We study the listdecoding problem, which we now describe. In the list-decoding problem, the decoder is not required to recover the transmitted
message exactly but can instead output a (small) list of messages with the guarantee that the true message is in the list. We
are typically interested in list-sizes that are constant or grow as a low-degree polynomial function of the blocklength.
Definition IX.1. Fix R ą 0 and nkey ě 0. A codebook C “ txpm, kq : 1 ď m ď 2nR , 1 ď k ď 2nkey u is said to be
pP, N, Lq-list-decodable at rate R with nkey bits of common randomness if
?
‚ }xpm, kq}2 ď
nP for all m, k; and
?
‚ for all possible randomized functions s – spC, zq satisfying P p}s}2 ď
nN q “ 1, we have
?
pkq
n
Pp|B px ` s, nN q X C | ą Lq “ op1q.
where C pkq – txpm, kq : 1 ď m ď 2nR u. In the above equation, the averaging is over the randomness in5 m, k, s and
sz .
A rate R is said to achievable for pP, N, Lq-list-decoding with nkey bits of common randomness if there exist sequences of
codebooks (in increasing n) that are pP, N, Lq-list-decodable. The list-decoding capacity is the supremum over all achievable
rates.
As a warm-up, let us consider the omniscient adversary. We have the following folk theorem.
P
Lemma IX.2. Let σ “ 0 and nkey “ 0. If  – 12 log N
´ R ą 0, then R is achievable for pP, N, Ωp 1 log 1 qq-list-decoding.
1
P
If R ą 2 log N , then no sequence of codebooks of rate R is pP, N, nOp1q q-list-decodable. Therefore, for polynomial list-sizes,
P
the list-decoding capacity is equal to 21 log N
.

Although the above result is folklore, we are not aware of a reference with a formal proof of this statement. For completeness,
and to keep the paper self-contained, we give a proof in Appendix C.
B. List-decoding with a myopic adversary
In the case where σ ą 0, we can achieve a higher list-decoding rate for certain values of N {P and σ 2 {P . We show that when
noise level to James is large enough (he is “sufficiently myopic”), he
? is unable to exactly determine s from z. Conditioned
on z, the transmitted codeword lies in a thin strip which is roughly nσ 2 away from z. If R is large enough, then the strip
will contain exponentially many codewords, and James cannot distinguish the true codeword from the others. Since we use a
random code, these codewords are roughly uniformly distributed over the strip. An effective value of s for one codeword on
the strip (in the sense of ensuring maximum confusion for Bob) may be ineffective for most of the remaining codewords. As
a result, there is no single direction where James can align s in order to guarantee the level of confusion that he could have
if he were omniscient. This is what will let us achieve a higher rate.
5 Note that we are using an average probability of error in our work. This is different from a maximum probability of error, where the list-size is required
to be less than or equal to L for every codeword. On the other hand, we are satisfied with this being true for all but a vanishingly small fraction of the
codewords.

21

We will consider the case nkey “ nRkey , for some Rkey ě 0. Even the case when Rkey “ 0 is non-trivial – see Figure 3a
for a region.
Theorem IX.3. For pP, N, Opn4 qq-list-decoding, the capacity is lower bounded as follows
!
)
#
2
RLD,myop , if σP ě max N1{P ´ 1, N
´
1
and RLD,myop ` Rkey ą
P
Cmyop,list ě
RLD ,
otherwise

1
2

`
log 1 `

P
σ2

˘
.

These are summarized in Fig. 3.
The rate RLD is achievable even in presence of an omniscient adversary. The main contribution of this work is in showing
that myopicity indeed does help, and we can obtain a higher rate of RLD,myop in a certain regime. It is interesting to note
that even when nkey “ 0, the myopic list-decoding capacity is nonzero for sufficiently large values of σ 2 {P . Furthermore,
increasing rates of common randomness (Rkey ) help us get achieve higher list-decoding rates as seen from Fig. 3. We now
provide a sketch of the proof, but relegate the details to Sec. XI.
1) Proof sketch: First, observe that that RLD is achievable as long as N ă P . This is true since RLD is achievable even
with an omniscient adversary (Lemma IX.2). The nontrivial step is in showing that a higher rate of RLD,myop is achievable in
a certain regime of the NSRs. We will prove the achievability using
random spherical codes. The 2npR`Rkey q codewords are
?
n´1
sampled independently and uniformly at random from S
p0, nP q. We study the probability that this random codebook is
not pP, N, Opn4 qq-list-decodable.
?
Conditioned on z, the true codeword x lies in a `thin strip˘ at distance approximately nσ 2 to z. We show that as long
as the codebook rate R ` Rkey is greater than 12 log 1 ` σP2 , this strip (with high probability) contains exponentially many
codewords, thereby causing sufficient confusion for James. This condition effectively limits the values of the NSRs where
RLD,myop is achievable.
For ease of analysis, we assume that James has access to an oracle, which reveals a subset of 2n codewords from the strip.
This set is guaranteed to contain the true codeword. Clearly, the oracle only makes James more powerful, and any result that
holds in this setting also continues to be valid when there is no oracle. The codewords in the oracle-given set are all independent
(over the randomness in the codebook) and are approximately uniformly (which we call quasi-uniformly) distributed over the
strip. The codewords outside the oracle-given set are independent of these, and are uniformly distributed over the sphere.
We then fix an attack vector s, and bound the probability that this forces a list-size greater than L for a nonvanishing
fraction
?
? of
the codewords in the oracle-given set. To do so, we find the typical area of the decoding region B n px`s, nN qXS n´1 p0, nP q
by computing the
? typical norm of y. This decoding region is a cap, whose area is maximized when the radius of the cap
(see Sec. V) is nN . This is would be the result of James’ attack if he were?omniscient. However, due to the randomness
in sz and his uncertainty about x, the typical radius is considerably less than nN . It is this reduction in the typical radius
that helps us achieve rates above RLD . The value of the typical radius is the solution of an optimization problem, which is
identical to the one we obtain when analyzing the scale-and-babble attack in Sec. VIII-A.
With an upper bound on the typical decoding volume, we can bound the probability that there are more than L codewords
in the decoding region. We separately handle the codewords within and outside the oracle-given set. The probability that a
fixed s causes list-decoding failure for a nonvanishing fraction of codewords in the oracle-given set is found to decay doubly
exponentially in n. We complete the proof using a covering argument for s and taking a union bound over all representative
attack vectors s.
C. Achievable rate using Θpnq bits of CR
The following lemma by Sarwate (originally proved by Langberg [18] for the bit-flip channel) says that a list-decodable
code can be converted to a uniquely decodable code with an additional Oplog nq bits of common randomness. Although the
lemma was stated in the context of discrete AVCs with deterministic encoding, the proof goes through even without these
restrictions. We can use our list-decodable code as a black box in the following lemma to go from a list-decodable code to a
uniquely decodable code.
For an arbitrary AVC W, we define an pn, R, L, q-list-decodable code as one which has blocklength n, message rate R,
and achieves a list-size of L with probability 1 ´ .
Lemma IX.4 (Lemma 13, [15]). Suppose we have a deterministic pn, R, L, q-list-decodable code for an AVC W. If the
encoder-decoder pair share nk bits of common randomness, then there exists a blocklength-n code of rate R ´ n2nk such that
the decoder can recover the transmitted message with probability 1 ´  ´ 1 , where
2nLR
1 –
.
nk 2nk {2
The above lemma says that an additional nk “ 2 logpnLq bits of common randomness is sufficient to disambiguate the list.
If L “ nOp1q , then the nk required is only logarithmic, and the penalty in the rate nk {p2nq is vanishing in n.

22

We can therefore use this with our myopic list-decoding result in Theorem IX.3 to obtain achievable rates. Combining this
with the converse in Lemma VIII.1, we obtain
Lemma IX.5. If Alice and Bob share nRkey bits of common randomness, then the capacity is
$
!
)
`
˘
σ2
1
N
1
P
’
’
&RLD,myop , if P ě max N {P ´ 1, P ´ 1 and Rkey ą 2 log 1 ` σ2 ´ RLD,myop
σ2
1
Cmyop “ RLD ,
.
P ď N {P ´ 1
’
’
%0
N
σ2
ď ´1
P

P

Furthermore,
RLD ď Cmyop ď RLD,myop

"
*
ˆ
˙
σ2
1
N
1
P
if
ě max
´ 1,
´ 1 , and Rkey ă log 1 ` 2 ´ RLD,myop .
P
N {P
P
2
σ

These results are pictorially summarized in Figs. 4 and 5.
The rates achievable for different values of the NSRs are illustrated in Fig. 4 and Fig. 5 for different values of Rkey . Our
scheme achieves capacity in the red and blue regions of Fig. 4 and 5. In the white dotted region, RLD is a lower bound on the
capacity, as guaranteed by Lemma IX.5. However, we can achieve RLD,myop with an infinite amount of common randomness.
Hence, there is a small gap between the upper and lower bounds in this region. In the cyan dotted region, RLD ă 0 and our
lower bound is trivial, while the converse says that the capacity is upper bounded by RLD,myop .
D. Achievable rates with Θplog nq bits of CR
Lemma IX.4 says that Θplog nq bits of common randomness is sufficient to disambiguate the list. Using this with
` Theo-˘
rem IX.3 for Rkey “ 0, we have Lemma IX.6. Note that when Rkey “ 0, the condition RLD,myop ` Rkey ą 12 log 1 ` σP2
2
reduces to σP ě 4 N
P ´ 1.
Lemma IX.6. When nkey “ Θplog nq, the capacity of the myopic adversarial channel is:
$
!
)
2
’
’RLD,myop , if σP ě max N1{P ´ 1, 4 N
&
P ´1
σ2
1
Cmyop “ RLD ,
.
P ď N {P ´ 1
’
’
2
%0
σ
N
P ď P ´1
Furthermore,

"
RLD ď Cmyop ď RLD,myop

if max

*
1
N
σ2
N
´ 1,
´1 ď
ď 4 ´ 1.
N {P
P
P
P

These results are summarized in Fig. 6.
These results are illustrated in Fig. 6. We have matching upper and lower bounds in the red, blue, and grey regions. As in
the previous subsection, there is a nontrivial gap between the upper and lower bounds in the green and white regions.
X. N O COMMON RANDOMNESS
When Alice and Bob do not have access to a shared secret key, the achievabilities above are not valid, and in some regions,
tighter converses can be obtained. This scenario requires more work, and we are able to prove the following result.
Theorem X.1. The capacity of the myopic adversarial channel with Θplog nq bits of common randomness is given by
$
1
σ2
1
’
if 1´N
’
{P ´ 1!ď P ď N {P ´ 1
&RLD ,
)
2
1
1
Cmyop “ RLD,myop , if σP ě max 1´N
.
´
1,
´
1
{P
N {P
’
’
%0,
σ2
N
N
if
ď 4 ´ 2 or
ě1
P

P

P

In the other regimes, we have
RGV ď Cmyop ď

$
&RLD ,
%RLD,myop

!
)
σ2
1
1
if 4 N
P ´!2 ď P ď min N)
{P ´ 1, 1´N {P ´ 1
σ2
1
if max N1{P ´ 1, 4 N
P ´ 2 ď P ď 1´N {P ´ 1 and

N
P

.
ď1

23

1) Proof sketch: The proof involves two parts:
The upper bounds are obtained using Lemma VIII.1, and symmetrization arguments described in Sec. X-2.
‚ The achievability involves a combination of list-decoding and reverse list-decoding, and the grid argument. We give a
high-level description below. For the rigorous proof, see Sec. XII.
The achievability proof uses several ideas from our discussion on myopic list-decoding in Sec. IX-B1. As discussed in
Sec. IX-B1, the transmitted codeword lies in a strip. We can only prove our result in the
myopic case, i.e.,
` sufficiently
˘
when the strip contains exponentially many codewords. This is possible only if R ą 12 log 1 ` σP2 . Just as in the proof of
myopic list-decoding, we assume that James has access to an oracle-given set. Our goal is to show that there exists no attack
strategy for James that would cause decoding failure for a nonvanishing
fraction of codewords in the oracle-given set.
?
Fix an s. We say that a codeword x1 confuses x if B n px ` s, nN q contains x1 . From James’ perspective, the codewords in
the oracle-given set are (approximately6 ) equally likely to have been transmitted. We say that decoding fails if the attack vector
chosen by James causes x to be confused with another codeword. To
? analyze this, we study the effect of s simultaneously
over all codewords in the oracle-given set. The set tB n pxpmq ` s, nN q : m P Orclu forms a “blob.” We show that with
high probability, the probability that the blob contains more than n4 confusing codewords7 is vanishingly small. This ensures
that there are only a polynomial number of codewords that could potentially confuse the exponentially many codewords in the
oracle-given set (OGS).
We then find the number of codewords xpmq in the OGS that could potentially be confused by a fixed x1 . We call this reverse
list-decoding, and show that each x1 can confuse only polynomially many codewords in the OGS. Our reverse list-decoding
2
1
argument holds if σP ě 1´N
{P ´ 1.
We combine the “blob” list-decoding and reverse list-decoding results and give a combinatorial argument to show that the
probability of a fixed s causing a decoding error for a nonvanishing fraction of codewords in the OGS is super-exponentially
decaying in n. We then use a standard covering argument for s and show that the average probability of decoding error is also
vanishing in n. This will complete the proof of Theorem X.1.
2) An improved converse using symmetrization: When the encoder is a deterministic map from the set of messages to Rn ,
we can give a better upper bound for certain values of the NSRs. This attack is based on the scaled babble-and-push attack
designed by Li et al. [17] for the quadratically constrained channel with a causal adversary. The basic idea in a symmetrization
argument is to make sure that Bob is equally confused between the actual transmitted codeword and a random codeword
independently chosen by James. Bob will then be unable to distinguish between the two codewords and therefore makes an
error with positive probability.
‚

Lemma X.2. If nkey “ 0, then C “ 0 when N ě P or

σ2
P

ă 4N
P ´ 2.

Proof. The first part is considerably simpler, and involves a z-agnostic symmetrization argument. If N ě P , then James can
mimic Alice. A simple attack strategy is the following: He generates a message m1 uniformly at random, and independently of
everything else. Using the same encoding strategy that Alice uses, this is mapped to a codeword s “ x1 which is transmitted.
Bob receives x ` x1 , and unless m1 “ m, he will be unable to determine whether Alice sent m or m1 . The probability of
error is therefore bounded away from zero, and this is true for all R ą 0. Therefore, the capacity is zero when N ě P .
2
To prove the second part, when σP ă 4 N
P ´ 2, we use a z-aware symmetrization attack. Since James is myopic, he has to do
more work to make Bob equally confused between m and m1 . Here, James picks a random codeword x1 uniformly from the
codebook and “pushes” z to the midpoint of z and x1 . Bob is then unable to distinguish between x and x1 , and will therefore
make an error with positive probability.
If N ě P , then Bob can mimic Alice by generating a message m1 uniformly at random, independently of everything else,
and then transmitting the corresponding codeword (say x1 ). Bob receives x ` x1 , and with probability 1 ´ 2´nR is unable to
determine whether Alice transmitted m or m1 . Therefore, the probability of error is always bounded away from zero.
2
r
r
For the case when σP ă 4 N
P ´ 2, we give a slightly different attack. James samples m „ pm , x „ px|m , both independently
of Alice, and setting
1
1
s “ β pr
x ´ zq “ β pr
x ´ x ´ sz q,
2
2
where
$
?
›1
›
› pr
›
&1,
nN
2 x ´ zq 2 ď
?
β“
,
(X.3)
nN
1
% } 1 prx´zq} “: β , otherwise
2
2
such that

#
y “x`s“

6 We
7 The

?
›1
›
› pr
x ` 12 pr
x ´ x ´ sz q “ 21 pr
x ` xq ´ 12 sz ,
x ´ zq›2 ď nN
2
`
˘
.
r ´ 21 β 1 sz , otherwise
x ´ x ´ sz q “ 1 ´ 21 β 1 x ` 12 β 1 x
x ` 12 β 1 pr

add this qualifier since all points in the strip are not equidistant from z.
degree of the polynomial here is not important, but is chosen to be 4 for convenience. What matters is that the list-size grows polynomially in n.

24

We introduce β merely to ensure that the attack vector always satisfies James’ power constraint. The probability We don’t care
much about the second case in Equation X.3, since the probability of the second case instantiating goes to zero. Hence, even
if Bob can perfectly decode the message in the second case, we show that in the first case his probability of error is going to
be bounded away from 0. Assume we operate at a rate R. The probability of error can be lower bounded by
p ‰ mq
Pe “ Ppm
?
p ‰ m, }s}2 ď nN q
ě Ppm
?
?
p ‰ m|}s}2 ď nN q
“ Pp}s}2 ď nN q Ppm
?
1
ě Pp}s}2 ď nN q,
2
where the last inequality comes from the following argument. Suppose that James has enough power to push the output y to
rq{2. Even if sz “ 0 and Bob knew that his observation y “ px ` x
rq{2 8 , he cannot distinguish whether x or x
r was
the px ` x
transmitted with probability less
than
1{2.
?
The probability P p}s}2 ď nN q can be bounded by Markov inequality. Specifically,
˜›
›2 ¸
›
›
1
2
x ´ x ´ sz q››
Ep}s}2 q “ E ›› pr
2
2
1
“ pEp}r
x}22 q ` Ep}x}22 q ` Ep}sz }22 q ´ 2 Epxr
x, xyq ´ 2 Epxr
x, sz yq ` 2 Epxx, sz yqq
4˜
¸
ÿ
1
“
2 Ep}x}22 q ` Ep}sz }22 q ´ 2
xi xi q
Epr
4
i“1
˜
¸
ÿ
1
2
“
2nP ` nσ ´ 2
xi q Epxi q
E pr
4
i“1
˜
¸
ÿ
1
2
2
“
2nP ` nσ ´ 2 pEpxi qq
4
i“1

(X.4)
(X.5)

1
ď p2nP ` nσ 2 q,
4
r and x are i.i.d.. Then we have
where Equation X.4 and Equation X.5 follow since x
ˆ
ˆ
˙
1
2 ˙
?
1
1
2P ` σ 2
1
4 p2nP ` nσ q
1´
“
1´
.
Pe ě Pp}s}2 ď nN q ě
2
2
nN
2
4N
If ´2P ` σ 2¯ă 4N , say 4N “ p1 ` qp2P ` σ 2 q for some constant  ą 0, then Pe is bounded away from 0, i.e., Pe ě
1
1

σ2
N
2 1 ´ 1` “ 2p1`q . Thus no positive rate is achievable when P ă 4 P ´ 2.
Remark X.6. The argument above merges one way of proving the Plotkin bound (via the Cauchy–Schwarz inequality – see,
say, Li et al. [17]) with the additional randomness in sz .
XI. M YOPIC LIST- DECODING
A. Coding scheme
key q
Codebook construction. We use random spherical codes. Before the communication, Alice samples 2npR`R
` ? codewords
˘
n´1
nR
nRkey
u independently and uniformly at random from the sphere S
0, nP . Once
txpm, kq : 1 ď m ď 2 , 1 ď k ď 2
sampled, the codebook is?fixed and revealed to every party: Alice, Bob and James. Notice that all codewords satisfy Alice’s
power constraint }x}2 ď nP . We define C pkq – txpm, kq : 1 ď m ď 2nR u to be the kth codebook. We also distinguish the
message rate R from the codebook rate Rcode – R ` Rkey .
Encoder. Let k P r2nRkey s be the realization of the secret key shared by Alice and Bob. Alice sends xpm, kq if she wants to
transmit message m to Bob.
Decoder. Bob uses a minimum distance decoder. Receiving y, he outputs m
p such that the corresponding codeword xpmq
p is
the nearest (in Euclidean distance) one in C pkq to his observation, i.e.,

m
p “ argmin }xpmq
r ´ y}2 .
m
ĂPt0,1unR
8 Notice

that there may exist other pairs of codewords with the same average.

25

We now give an outline of the proof of myopic list-decoding. In order to have an improvement over the ominiscient listdecoding capacity,`James must
not be able to uniquely decode the transmitted codeword. Clearly, if the codebook rate Rcode
˘
P
is less than 12 log
1
`
2 , then James can recover the transmitted codeword with high probability. We will show that if
σ
˘
`
Rcode ą 21 log 1 ` σP2 , then there are exponentially many codewords
that confuse James. With high probability, all these
?
codewords lie on a thin strip at a distance approximately equal to nσ 2 from z. To simplify analysis, we assume that James
has access to an oracle, who reveals a list of 2n potential codewords (including the one transmitted) from the strip. If we
can show that the list-size is small in this case where James has more information, then the result will continue to hold even
when James does not have access to the oracle. The transmitted codeword is close to being uniformly distributed over the set
revealed by the oracle. Since James is still confused about which of the 2n codewords were transmitted, his attack is limited
in some sense. We will show that typical intersection of the noise/jamming ball (due to James’ attack) with the codebook is
at most polynomial in n, which gives us the result we want.
For the rest of this section, we fix two quantities:  is a small positive constant independent of n, and δ is a constant that
grows as Θpplog nq{nq.
B. The strip and the oracle-given set (OGS)
Fix an  ą 0 and L “ 2n4 . To help with the proof, we prove the achievability part under a more powerful adversary who
has access to an oracle in addition to z. The oracle reveals a set of 2n codewords that contains the transmitted codeword and
others that are all at approximately the same distance to z. We call this the oracle-given set or Orclpz, xq. Conditioned on
James’ knowledge, the transmitted codeword is independent of all codewords outside the oracle-given set. We now describe
the rule that assigns a pair px, zq to an OGS. a
?
Choose any optimal covering Z of Shn p0, npP ` σ 2 qp1 ˘ qq such that minz1 PZ }z ´ z 1 }2 ď nδZ . It turns out that the
size of such a covering
˜
¸1`op1q ˜ a
a
?
? ¸np1`op1qq
VolpB n p0, npP ` σ 2 qp1 ` q ` nδZ qq
pP ` σ 2 qp1 ` q ` δZ
?
?
“
|Z| ď
— cn,δZ .
(XI.1)
VolpB n p0, nδZ qq
δZ
Given z, let zQ – arg minz1 PZ }z ´ z 1 }2 denote the closest point to z in Z. For each zQ P Z, and i P t´{δ ` 1, . . . , {δu,
define
a
a
?
Strn´1 pzQ , iq – S n´1 p0, nP q X Shn pzQ , nσ 2 p1 ` pi ´ 1qδq, nσ 2 p1 ` iδqq,
(XI.2)
a
a
2
´ 1qδq but at most nσ 2 p1 ` iq away
to be the set of all points on the coding sphere at a distance
? of at least nσ p1 2`nRpicode
Ť Ť
n´1
n´1
from zQ . We claim that zQ i Str
pzQ , iq “ S
p0, nP q. If C “ txpmqum“1 denotes the codebook, define
Mstr pzQ , iq – tm : xpmq P Strn´1 pzQ , iqu

(XI.3)

to be the set of indices of the codewords that lie in Strn´1 pzQ , iq. We partition this set of indices into blocks of size 2n each
(except perhaps the last block), in the lexicographic order induced by m. Let tOrclpjq pzQ , iqu`j“1 denote the partition, where
` – r|Mstr pzQ , iq|{2n s. Each of these blocks constitutes an oracle-given set. If m corresponding to the transmitted codeword
x lies in Orclpιq pzQ , iq, the the oracle reveals OrclpzQ , xq – Orclpιq pzQ , iq to James.
Remark XI.4. It is important to note that all sets defined above (strips, OGS, etc.) are designed a priori, before z instantiated.
C. Error events

?
?
Define Lpkq pxpmq, sq – B n pxpmq ` s, nN q X C pkq for s P B n p0, nN q. Recall that to prove the existence of a listdecodable code, we want to show that
´
¯
?
n
pkq
np´hp,τ,δS ,δZ q{2q
“ op1q.
P Ds P B p0, nN q, |tm P Orclpz, xq : |L pxpmq, sq| ą Lu| ą 2
To analyze this, we define a number of error
? events.
?
Choose any optimal covering S of B n p0, nN q such that mins1 PS }s´s1 }2 ď nδS . Given s, let sQ – arg mins1 PS }s´s1 }2
denote the closest point to s in S. By similar calculation to Equation XI.1, we have
˜?
? ¸np1`op1qq
N ` δS
?
|S| ď
— cnδS .
(XI.5)
δS
We say that list-decoding fails if any of these events occur, and ultimately show that the probability of failure is negligible.
The error events that we analyze are listed below:
Eatyp James’ observation z behaves atypically, equivalently, the noise to James sz behaves atypically.
a
Eatyp1 – t}sz }2 R nσ 2 p1 ˘ qu.
(XI.6)

26

Eatyp2 – t| cosp=x,sz q| ě u.
Eatyp3 –

t}z}22

2

R npP ` σ qp1 ˘ qu.

(XI.7)
(XI.8)

Hence the error event Eatyp is the union of the above three events.
Eatyp – Eatyp1 Y Eatyp2 Y Eatyp3 .
Estr One of the sets tStr

n´1

3n

pzQ , iqui contain fewer than 2

(XI.9)

codewords.

Estr piq – t|Mstr pzQ , iq| ă 23n u.
ď
Estr –
Estr piq.

(XI.10)
(XI.11)

i

Eorcl Another minor technical thing to worry about is: the last OGS may be substantially smaller than than the others, hence
could have a higher probability of error. But the probability that the transmitted codeword happens to fall in to the last
set is small. Call Eorcl the event that the message corresponding to the transmitted codeword belongs to the last block of
Mstr pzQ , iq.
Eerr Given that none of E1, E2, E3 occur, there exists an attack vector sQ P S that results in a list-size greater than L for
more than 2np´hp,τ,δS ,δZ q{2q codewords in the oracle-given set. For each zQ , i, j, sQ , define
ÿ
1t|Lpkq pxpmq,sQ q|ąLu
(XI.12)
χpzQ , i, j, sQ q –
mPOrclpjq pzQ ,iq

to be the number of codewords in the oracle-given set that result in a large list-size when perturbed by sQ . Then, we
define
Eerr pzQ , i, j, sQ q – tχpzQ , i, j, sQ q ą 2np´hp,τ,δS ,δZ q{2q u
to be the event that more than 2np´hp,τ,δS ,δZ q{2q codewords can be perturbed by sQ to give a large list-size. The error
event Eerr is defined as
ďďďď
Eerr –
Eerr pzQ , i, j, sQ q
(XI.13)
zQ i

j sQ

D. The probability of myopic list-decoding error – proof of Theorem IX.3
We now prove Theorem IX.3 by upper bounding the probability that an error occurs in myopic list-decoding. We can
decompose the failure probability in the following manner.
´
¯
?
n
pkq
np´hp,τ,δS ,δZ q{2q
P Ds P B p0, nN q, |tm P OrclpzQ , xq : |L pxpmq, sq| ą Lu| ą 2
´
¯
ď P DsQ P S, |tm P OrclpzQ , xq : |Lpkq pxpmq, sQ q| ą Lu| ą 2np´hp,τ,δS ,δZ q{2q
“ P pEatyp Y Estr Y Eorcl Y Eerr q
˛
¨
ďďďď
Eerr pzQ , i, j, sQ q‚
“ P ˝Eatyp Y Estr Y Eorcl Y
zQ i

j sQ

ď1 ´ p1 ´ PpEatyp qq
˜
¸
ÿ
c
¨ 1 ´ PpEstr piq|Eatyp q

(XI.14)

i
c
c
¨ p1 ´ PpEorcl |Eatyp
X Estr
qq
¨
˛
ÿÿÿÿ
c
c
c
¨ ˝1 ´
PpEerr pzQ , i, j, sQ q|Eatyp X Estr X Eorcl q‚,
zQ i

?

j sQ

?
where Lpkq pxpmq, sQ q – B n p0, nN ` nδS q X C pkq .
It is therefore sufficient to show that each of the error terms is vanishing in n.
The analysis of Eatyp , Estr and Eorcl follow from somewhat standard concentration inequalities which are formally justified in
Section XI-E, Section XI-F and Section XI-G, respectively. Notice that in the analysis of Estr , James is said to be sufficiently
myopic if, given his observation ´z, his uncertainty
set, i.e., any strip, contains at least exponentially many codewords. This is
¯
1
σ2
guaranteed if R ` Rkey ą 2 log 1 ` P .

27

Much of the complication of our work is dedicated to the analysis of Eerr pzQ , i, j, sQ q. We further factorize it into sub-events
and treat them separately. Define E – Eatyp Y Estr Y Eorcl . Fix zQ , i, j and sQ . We are going to show that
c
PpEerr pzQ , i, j, sQ q|E q

“ Pp|tm P Orclpjq pzQ , iq : |Lpkq pxpmq, sQ q| ą Lu| ą 2np´hp,τ,δS ,δZ q{2q |E c q
“ PpχpzQ , i, j, sQ q ą 2np´hp,τ,δS ,δZ q{2q |E c q
ˇ ˛
¨
ˇ
ÿ
ˇ
“P˝
1t|Lpkq pxpmq,sQ q|ąLu ą 2np´hp,τ,δS ,δZ q{2q ˇˇ E c ‚
ˇ
mPOrclpjq pzQ ,iq
ď2´2

Ωpnq

,

which allows us to take a union bound over exponentially many objects. At a high level, this follows from a Chernoff-type
argument. To be concrete, first, fix m P Orclpjq pzQ , iq and we will prove
pkq

Pp|L

pxpmq, sQ q| ą L|E c q

ď Ppt|Lpkq pxpmq, sQ q| ą Lu X Erc |E c q ` PpEr |E c q
ď Pp|Lpkq pxpmq, sQ q| ą L|E c X Erc q ` PpEr |E c q

(XI.15)

ď2´hp,τ,δS ,δZ qn ,
?
?
?
?
where Er is the error event that the radius nr of the list-decoding region B n pxpmq ` sQ , nN ` nδS q X S n´1 p0, nP q
(notice that it is a cap) for m P Orclpjq pzQ , iq behaves atypically. We will see in Section XI-H that first terms in Equation XI.15
is super-exponentially small and the second term is singly exponentially small. The probability in the second term is only over
sz and hence single-exponential concentration is good enough, whereas the first term basically follows from Lemma VI.5 if
we fix list-size L to be a polynomial, say Opn4 q. The value that r (see optimization XI.27) is concentrated around when James
adopts the most malicious strategy gives the threshold of rate for different configurations of NSRs.
Then the expected number of codewords in the OGS that could lead to a large list-size is given by
ˇ ˛
¨
ˇ
ÿ
ˇ
1t|Lpkq pxpmq,sQ q|ąLu ˇˇ E c ‚
E˝
ˇ
mPOrclpjq pzQ ,iq
ÿ
c
“
Ep1t|Lpkq pxpmq,sQ q|ąLu |E q
mPOrclpjq pzQ ,iq

ď2n Pp|Lpkq pxpmq, sQ q| ą L|E c q
ď2np´hp,τ,δS ,δZ qq .
As txpmq P C pkq : m P Orclpjq pzQ , iqu are independently distributed over the strip that the OGS corresponds to, by Chernoff
bound,
ˇ ˛
¨
ˇ
ÿ
ˇ
Ωpnq
1t|Lpkq pxpmq,sQ q|ąLu ą 2np´hp,τ,δS ,δZ q{2q ˇˇ E c ‚ ď 2´2
.
P˝
ˇ
mPOrclpjq pzQ ,iq
A union bound over zQ , i, j and sQ completes the analysis of the probability of failure of myopic list-decoding.
The whole bounding procedure (including myopic list-decoding in this section and unique decoding in Section XII) is
depicted in Figure 23.
E. Event Eatyp : Atypical behaviours of James’ observation
From Fact VI.3, we know the probability
that sz , x are not jointly typical vanishes as n Ñ 8. Specifically, the AWGN to
?
James has norm concentrating around nσ 2 and is appproximately orthogonal to x.
a
2
´f pqn
.
PpEatyp1 q “ Pp}sz }2 R nσ 2 p1 ˘ qq ď 2 expp´ n{8q — 2 1
PpEatyp2 q “ Pp| cosp=x,sz q| ě q
ˇ
ˆˇ
˙
ˇ xx, sz y ˇ
ˇ
ˇ
“P ˇ
ě
}x}2 }sz }2 ˇ

28

Myopic list-decoding

James’ observation behaves atypically

The -the strip contains <

codewords

Union bound
over strips
Any strip contains <

codewords

The transmitted codeword belongs to the last OGS

Too many codewords in OGS have large list-size

For fixsed

, too many codewords in OGS have large list-size

Conditioned on good events,
in an OGS has large list-size under

Decoding region of in
an OGS has atypical area

Bayes theorem
Bayes theorem

Linearity of expectation

Chernoff bound

Union bound over ’s, strips, OGSs, ’s

List-decodable with poly(n) list-size w.h.p.

Unique decoding
Type I error: confusing codewords are outside OGS

Type II error: confusing codewords come from OGS
Grid argument

Blob list-decoding

Blob list-decoding
Reverse list-decoding
Reverse list-decoding

Unique decoding w.h.p.

Fig. 23: A flow-chart describing the procedure of bounding error probability. Some notation is simplified for the ease of
drawing.

29

ˇ
ˆˇ
˙
ˇ xe1 , sz y ˇ
ˇě
“ P ˇˇ
}sz }2 ˇ
“ Pp|sz 1 | ě }sz }2 q
a
a
ď Pp|sz 1 | ě }sz }2 , }sz }2 P nσ 2 p1 ˘ qq ` Pp}sz }2 R nσ 2 p1 ˘ qq
a
a
ď Pp|sz 1 | ě  nσ 2 p1 ´ qq ` Pp}sz }2 R nσ 2 p1 ˘ qq
ď2 expp´2 p1 ´ qn{2q ` 2´f1 pqn
—2´f2 pqn .
Notice that
}z}22 “ }x ` sz }22 “ }x}22 ` }sz }22 ` 2xx, sz y.
? a
Choose the smallest 1 that satisfies npP ` σ 2 qp1 ˘ q Ă nP ` nσ 2 p1 ˘ 1 q ˘ 2 nP nσ 2 p1 ` 1 q1 . We can also concentrate
James’ observation
2
2
PpEatyp3 q “ Pp}z}2 R npP ` σ qp1 ˘ qq

?

a
nσ 2 p1 ` 1 q1 q
? a
ď Pp}s}22 R nσ 2 p1 ˘ 1 qq ` Pp|xx, sz y| ě nP nσ 2 p1 ` 1 q1 q
ď Pp}z}22 R nP ` nσ 2 p1 ˘ 1 q ˘

nP

ď2´f1 p1 qn ` 2´f2 p1 qn
—2´f3 pqn .
Therefore,
´f pqn
` 2´f2 pqn ` 2´f3 pqn — 2´nfE1 pq ,
PpEatyp q ď PpEatyp1 q ` PpEatyp2 q ` PpEatyp3 q ď 2 1

where fE1 pq is positive as long as  ą 0 and limÓ0 fE1 pq “ 0.
F. Event Estr : Number and distribution of codewords in strip: exponential behaviour and quasi-uniformity
a
?
Ť
The intersection of Shn pzQ , npσ 2 ˘ qq with S n´1 p0, nP q forms a strip Strn´1 pzQ q – i Strn´1 pzQ , iq, which we
study next. For the ease of incoming calculations, let’s first translate slacks in the length of sz , i.e.,  and δ as afore-defined,
to slacks in the radius rstr of strip, i.e, ρ and τ , respectively. Recall that the set of strips is defined as follows
a
a
?
Strn´1 pzQ , iq “ S n´1 p0, nP q X Shn pzQ , nσ 2 p1 ` pi ´ 1qδq, nσ 2 p1 ` iδqq, @i P t´{δ ` 1, ¨ ¨ ¨ , {δu.
(XI.16)
Now we write it in a slightly different form
a
a
?
?
Strn´1 pzQ , iq “ Capn´1 p¨, nrstr p1 ` iτ q, nP qzCapn´1 p¨, nrstr p1 ` pi ´ 1qτ q, nP q, @i P t´ρ{τ ` 1, ¨ ¨ ¨ , ρ{τ u.
(XI.17)
a
Define di “ nσ 2 p1 ` iδq and rstr,i “ rstr p1 ` iτ q, for any i P t´{δ ` 1, ¨ ¨ ¨ , {δu. Then by Heron’s formula,
b
?
1
}zQ }2 rstr,i “ sps ´ di qps ´ }zQ }2 qps ´ nP q,
2
i.e.,
b
?
2
sps ´ di qps ´ }zQ }2 qps ´ nP q.
rstr,i “
}zQ }2
It follows that ρ and τ only differ by a constant factor from  and δ, respectively.
As mentioned, codewords are almost uniformly distributed in the strip from James’ point of view. Given z, we now
characterize the quasi-uniformity in terms of τ . Define quasi-uniformity factor
∆pτ q “

?sup

zPShn p0,

max

npP `σ 2 qp1˘qq

i

sup
xp1q ,xp2q PStr n´1 pzQ ,iq

px|zQ pxp1q |zQ q
px|zQ pxp2q |zQ q

.

(XI.18)

c
Lemma XI.19 (Quasi-uniformity). For appropriate choices of ρ “ Op1q and τ “ Opplog nq{nq, conditioned on Eatyp
, we have

∆pτ q “ Oppolypnqq.

30

Fig. 24: For
? any James’ observation z, a thin strip containing the transmitted codeword x is constructed on the coding sphere
S n´1 p0, nP q. Typically, the geometry is shown in above figure. From James’ perspective, given z, codewords in the strip
are approximately equally likely to be transmitted by Alice. The quasi-uniformity is defined as the maximum deviation of
probability of codewords in the strip. Notice that any codeword at the same latitude has exactly the same probability. Codewords
on the upper (lower) boundary of the strip, say x´ (x` ), are most (least) likely in the strip to be transmitted. For small enough
(Opplog nq{nq) thickness of the strip, the quasi-uniformity factor is a polynomial in n.
Proof. As shown in Figure 24, obviously, for fixed z and i, the inner supremum is achieved by a point x´ on the upper boundary
(closer to z) of the strip and a point x` on the lower boundary (further from z) of the strip. Calculations in Appendix E show
that
¸
˜
px|z pxp1q |zq
2nrstr τ
}z}2
a
a
sup
.
“ exp
p2q |zq
σ2
npP ´ r´ q ` npP ´ r` q
xp1q ,xp2q PStr n´1 pz,iq px|z px
c
, the quasi-uniformity factor is upper bounded by
Then, conditioned on Eatyp
˜
¸
}zQ }2
2nrstr τ
a
a
∆pτ q ď
max exp
?sup
i
σ2
npP ´ r´ q ` npP ´ r` q
zPShn p0, npP `σ 2 qp1˘qq
˜
¸
?
2nrstr τ
npP ` σ 2 qp1 ` q ` nδZ
a
a
ď exp
.
σ2
npP ´ rstr p1 ´ τ qq ` npP ´ rstr p1 ` τ qq

We have ∆pτ q “ Oppolypnqq by taking τ “ Opplog nq{nq.
Next, we show that if the codebook rate is large enough, then with high probability the strip will contain exponentially
many codewords.
`
˘
Lemma XI.20 (Exponentially many codewords in strip). Let Rcode ą 12 log 1 ` σP2 . Then,
¯
´
Ωpnq
c
n´1
c
ď 2´2
.
pzQ , iq X C| ď 23n |Eatyp
PpEstr |Eatyp q “ P Di, |Str

Proof. In Appendix F, we show that, for fixed zQ and i,
ˇ
´
¯
ˇ c
n´1
pzQ , iq X C|ˇ Eatyp
ě 24n .
E |Str
Using Chernoff’s bound,
c
n´1
c
pzQ , iq X C| ď 23n |Eatyp
q ď 2´2
PpEstr piq|Eatyp q “ Pp|Str

for some positive constant c. There are at most 2Opn
by taking a union bound over all such pairs.

2

q

Ωpnq

.

many zQ ’s and Opn{ log nq many i’s. Lemma XI.20 is then obtained

31

G. Event Eorcl : Transmitted codeword is in the last block
Conditioned on z and the OGS, the transmitted codeword is quasi-uniformly distributed over the strip that the OGS
c
c
corresponds to. Given Eatyp
and Estr
, there are at least 23n many codewords in each strip with high probability. Also, notice
that each OGS (probably except the last one) is of size 2n . Therefore, the probability that Eorcl occurs is
c
c
PpEorcl |Eatyp X Eorcl q ď

1
1
1
∆pτ q “
∆pτ q ď 3n n ∆pτ q “ 2´2n ∆pτ q.
n
`
r|Mstr pzQ , iq|{2 s
2 {2

H. Event Eerr : Existence of a problematic attack vector
At first, we fix sQ P S. We will show that the probability that the list-size is greater than L is super-exponentially small in
n. We will finally use a quantization argument and take a union bound over s to show that P pEerr q “ op1q.
We will show the following:
Lemma XI.21. Fix zQ , i, j and sQ . For any m P Orclpjq pzQ , iq, we have
´
¯
pkq
c
´hp,τ,δS ,δZ qn
,
P |L pxpmq, sQ q| ą L|E ď 2
where, as afore-defined, E “ Eatyp Y Estr Y Eorcl .
Using a Chernoff-type argument we sketched in Section XI-D, this immediately gives the following lemma.
Lemma XI.22. Fix zQ , i, j and sQ . Then
´
¯
Ωpnq
c
pjq
pkq
np´hp,τ,δS ,δZ q{2q c
|E ď 2´2
.
PpEerr pzQ , i, j, sQ q|E q “ P |tm P Orcl pzQ , iq : |L pxpmq, sQ q| ą Lu| ą 2
2

A loose upper bound on the number of oracle-given sets in each strip is 2npR´q . Since there are at most 2Opn q strips, we
2
can say that the number of possible oracle-given sets does not exceed 2Opn q . The argument for P pEerr q “ op1q?follows by
taking a union bound over zQ , i, j and sQ . Note that we are required to quantize s using a finite cover of B n p0, nN q. The
steps mimic the proof of Lemma C.1, and we omit the details. All that remains is to prove Lemma XI.21.
I. Proof of Lemma XI.21
?
To prove this lemma, we will find the typical value of nr – the radius of the list-decoding region, and use this to obtain
an upper bound on the probability that the list-size is large. We write
pkq
Pp|L pxpmq, sQ q| ą Lq

ď Pp|Lpkq pxpmq, sQ q| ą L|Erc q ` PpEr q.
Our goal is to show that both quantities are bounded from above by 2´n{2
? . ?
?
For m P Orclpjq pzQ , iq, the list-decoding region is B n pxpmq ` sQ , nN ` nδS q X S n´1 p0, nP q. We will first bound
the area of the list-decoding region, and show that with high probability, this is not too large.
Fix sQ . Let x be quasi-uniformly distributed over the strip Strn´1 pzQ , iq. We decompose x and sQ into sums of vectors
orthogonal and parallel to zQ ,
a
a
?
?
αx e} ` nβ
β x eK , sQ “ ´ nαs e} ` nβs es K ,
x “ nα
where e} denotes the unit vectors along zQ and
?

αx “
nα

xx, zQ y a
?
β x eK “ x ´ nα
α x e} ,
, nβ
}zQ }2

xsQ , zQ y a
?
?
´ nαs “
, nβs es K “ sQ ` nαs e} .
}zQ }2
s, and thus sQ , should satisfy James’ power constraint, i.e, αs ` βs ď N . Sometimes, we also use x} or sQ } to denote the
first composition in the decomposition and use xK or sQ K to denote the second composition.
?
This decomposition will bring us analytic ease to compute the list-size which is equivalent to computing the radius nr of
the myopic list-decoding region by noticing that it is nothing but a cap
a
?
?
B n pyQ , nN ` nδS q X S n´1 p0, nP q

32

?
Fig. 25: In expectation, the noise to James sz is orthogonal to the codeword x and of length nσ 2 . Fix a legitimate attack
vector s and decompose x and s into sums of components orthogonal and parallel to James’ observation z. Each component
in above figure can be concentrated and is robust to quantization errors.
a
?
?
“B n pxpmq ` sQ , nN ` nδS q X S n´1 p0, nP q
?
?
“Capn´1 p¨, nr, nP q,
where yQ – x ` sQ , and m P Orclpjq pzQ , iq.
Notice that, averaged over the codebook generation, eK is uniformly distributed9 over the unit ring S n´2 p0, 1q. We will
need Lemma VI.4 to bound the tail of inner product of xK with other vectors.
Heuristically, in expectation, without quantization, a glimpse at the geometry shown in Figure 25 immediately gives us,
?
?
αx
nα
nP
P2
?
“a
ùñ α x “
,
P ` σ2
nP
npP ` σ 2 q
and

?
nP
P σ2
a
.
ùñ β x “
“
P ` σ2
npP ` σ 2 q
nσ 2

a
?

βx
nβ

In fact, both components are concentrated.
ˆ
˙
P2
p1 ˘ q
P αx R
P ` σ2
¸
˜
c
xx, zQ y
P2
R n
p1 ˘ q
“P
}zQ }2
P ` σ2
˜
¸
c
P2
“ P xx, zQ y R n
p1 ˘ q}zQ }2
P ` σ2
˜
¸
c
a
P2
ď P xx, zQ y R n
p1 ˘ qp}z}2 ¯ nδZ q
P ` σ2
˜
¸
c
a
P2
“ P xx, zQ y R n
p1 ˘ qp}z}2 ¯ nδZ q, }z}22 P npP ` σ 2 qp1 ˘ q
P ` σ2
˜
¸
c
a
P2
2
2
` P xx, zQ y R n
p1 ˘ qp}z}2 ¯ nδZ q, }z}2 R npP ` σ qp1 ˘ q
P ` σ2
˜
¸
c
a
a
♥
P2
2
ď P xx, zQ y R n
p1 ˘ qp npP ` σ qp1 ¯ q ¯ nδZ q ` Pp}z}22 R npP ` σ 2 qp1 ˘ qq
P ` σ2
9 Technically speaking, it is the case only when we decompose x with respect z. It is not exactly, but still approximately true when we take the quantization
zQ . This error will be taken into account via Lemma XI.25.

33

ď Ppxx, zQ y R nP p1 ˘ f4 p, δZ qqq ` 2´f3 pqn
˙
ˆ
♦
P f 1 p, δZ q2
n ` 2´f3 pqn
ď2 exp ´ 4 2
2σ
—2´f5 p,δZ qn ,
where ♥ follows since the event
#

c

xx, zQ y R
implies the event

a
P2
n
p1 ˘ qp}z}2 ¯ nδZ q, }z}22 P npP ` σ 2 qp1 ˘ 1 q
2
P `σ

#

+

+
a
a
P2
p1 ˘ qp npP ` σ 2 qp1 ¯ 1 q ¯ nδZ q , 10
xx, zQ y R n
P ` σ2
?
?
and ♦ follows from standard Gaussian tail bound. Specifically, let 1 ˘ 2 “ 1 ˘  1 ` 1 and we have
c

Ppxx, zQ y R nP p1 ˘ f4 p, δZ qqq
“ Ppxx, z ` ze y R nP p1 ˘ f4 p, δZ qqq
“ Ppxx, zy ` xx, ze y R nP p1 ˘ f4 p, δZ qqq
♥

ď Ppxx, zy R nP p1 ˘ f4 p, δZ qq ¯ }x}2 }ze }2 q
a
ď Ppxx, zy R nP p1 ˘ f4 p, δZ qq ¯ n P δZ q
a
“ Ppxx ` sz , xy R nP p1 ˘ f4 p, δZ q ¯ P δZ qq
ď Ppxx, sz y ` }x}22 R nP p1 ˘ f41 p, δZ qqq
“ Pp|xx, sz y| ą nP f41 p, δZ qq
“ Pp|N p0, σ 2 }x}22 q| ą nP f41 p, δZ qq
ˆ 2 2 1
˙
n P f4 p, δZ q2
ď2 exp ´
2σ 2 nP
ˆ
˙
P f 1 p, δZ q2
“2 exp ´ 4 2
n ,
2σ
where ♥ follows from Cauchy–Schwarz inequality ´}a}2 }b}2 ď xa, by ď }a}2 }b}2 . It also follows that with probability at
least 1 ´ 2´f5 p,δZ qn ,
P2
P2
P2
βx P P ´
p1 ˘ q “
p1 ¯ {σ 2 q —
p1 ¯ 3 q,
2
2
P `σ
P `σ
P ` σ2
All the above concentration is over the randomness in the channel between Alice and James and codebook generation. Now
let’s take into account the quasi-uniformity of the codewords in the strip. By the definition of strip,
βx P

P σ2
P σ2
p1 ¯ 3 qp1 ¯ τ q —
p1 ˘ f6 p, τ qq,
2
P `σ
P ` σ2

and therefore
αx P P ´

P σ2
P2
p1 ¯ 3 qp1 ¯ τ q “
2
P `σ
P ` σ2

ˆ
1˘

σ2
σ2
σ2
3 ˘
τ´
3 τ
P
P
P

˙
—

P2
p1 ˘ f7 p, τ qq.
P ` σ2

Again, they are concentrated (over the codebook generation, the noise to James and the quasi-uniformity in the strip).
ˆ
˙
P2
p1 ˘ f7 p, τ qq ď 2´f5 p,δZ qn ∆pτ q,
P αx R
P ` σ2
ˆ
˙
P σ2
p1 ˘ f6 p, τ qq ď 2´f5 p,δZ qn ∆pτ q.
P βx R
P ` σ2
10 Similar

tricks will be frequently used in what follows and the corresponding explanation will be omitted.

34

(a) cap

(b) cap

Fig. 26: cap
?

nr of the list-decoding region, let’s first calculate
c
a
a
?
} ?
}
K
K
αx e , nαs e y ´ Epx nβ
β x e , nβs es yq “ nP
Epx´x, sQ yq “ x nα

To compute the radius

αs
,
P ` σ2

(XI.23)

a
?
β x eK , nβs es K yq “ 0 as eK is isotropically distributed.
since by decomposition, crossing terms vanish and E px nβ
?
?
Remark XI.24. Notice that we actually know exactly the distribution of x nβx eK , nβs es K y. Indeed, in Rn , given a real unit
2
`1
unit vector e isotropically distributed on the unit sphere
S n´1?p0, 1q, |xe,ey|
has Beta distribution
vector` e and a random
2
˘
?
n´1 n´1
K
K
Beta 2 , 2 . Plugging this into our calculation, indeed, we get that x nβx e , nβs es y has mean 0. But this result
does not bring us any analytic advantage. Rather, in the analysis, when caring about concentration, we use the approximation
of the tail of this distribution in Lemma VI.4.
Although given z, eK is perfectly isotropic on the unit ring S n´2 p0, 1q, it is not exactly the case when we are using zQ .
It is, however, approximately correct. Specifically, this issue is fixed by the following lemma. As shown in Figure 26a, recall
that we denote by x “ xQ } ` xQ K the decomposition with respect to zQ . Also, denote by x “ x} ` xK the decomposition
with respect to x. Define the error vectors as xe – xQ K ´ xK and se – sQ K ´ sK .
?
?
?
2
Lemma XI.25. Fix ζ ą 0. Let ζ 1 – ζ ´ P δS ´ }x}
δS δZ . Then
}z}2 N δZ ´
K
K
´
Pp|xxQ , sQ y| ě nζq ď 2

pn´2qζ 12
2N P

.

Proof. We write
K
K
Pp|xxQ , sQ y| ě nζq

“ Pp|xxK ` xe , sK ` se y| ě nζq
ď Pp|xxK , sK y| ` |xxK , se y| ` |xxe , sK y| ` |xxe , se y| ě nζq
ď Pp|xxK , sK y| ` }xK }2 }se }2 ` }xe }2 }sK }2 ` }xe }2 }se }2 ě nζq
a
a
?
ď Pp|xxK , sK y| ` n P δS ` nN }xe }2 ` n δS δZ ě nζq.
?
It suffices to upper bound }x
} . As the quantization error for z is at most nδZ , for maximum θ shown in Figure 26b,
?e 2
}ze }2
nδZ
we have sinpθq “ }z}
ď }z}
. Notice that =QAP “ =QBP “ =QOP {2 “ θ. Consider the triangle ∆QOP . We have
2
?2
?
}xe }2 {2
|QP |{2
nδZ
2
“ }x}2 {2 “ sinpθq ď }z}2 , i.e., }xe }2 ď }x}
}z}2 nδZ . Now Lemma VI.4 can be applied.
|QO|
K
K
Pp|xxQ , sQ y| ě nζq

35

ˆ
˙
a
a
}x}2 a
ď P |xxK , sK y| ě nζ ´ n P δS ´ n
N δZ ´ n δS δZ
}z}2
´

ď2

ď2´

pn´2qn2 ζ 12
2}xK }2 }sK }2
pn´2qζ 12
2N P

.

Now we give a concentrated version of Equation XI.23.
c
˙
ˆ
α
p1 ˘ q
P x´x, sQ y R nP
P ` σ2
c
ˆ
˙
a
a
?
αs
} ?
}
K
K
αx e , nαs e y ´ x nβ
β x e , nβs es y R nP
“ P x nα
p1 ˘ q
P ` σ2
c
˙
ˆ
a
a
?
P2
αs
} ?
}
K
K
αx e , nαs e y ´ x nβ
β x e , nβs es y R nP
ď P x nα
p1 ˘ q, α x P
p1 ˘ f7 p, τ q
P ` σ2
P ` σ2
c
˙
ˆ
a
a
?
?
P2
αs
αx e} , nαs e} y ´ x nβ
β x eK , nβs es K y R nP
p1
˘
q,
α
R
p1
˘
f
p,
τ
q
` P x nα
x
7
P ` σ2
P ` σ2
c
c
ˆ a
˙
a
αs
αs
β x eK , nβs es K y| ą nP
ď P |x nβ
p1 ` f7 p, τ qq ´ nP
p1 ´ q
P ` σ2
P ` σ2
ˆ
˙
P2
` P αx R
p1
˘
f
p,
τ
q
7
P ` σ2
b
¨
˛
s
nP P α
2 pf7 p, τ q ` q
a
a
`σ
‚` 2´f5 p,δZ qn ∆pτ q
β x eK , nβs es K y| ą a
ď P ˝|x nβ
?
1 ` f7 p, τ q ` 1 ´ 
a
a
β x eK , nβs es K y| ą nf8 p, τ qq ` 2´f5 p,δZ qn ∆pτ q
ď Pp|x nβ
ˆ a
˙
a
P σ2
β x eK , nβs es K y| ą nf8 p, τ q, β x P
“ P |x nβ
p1
˘
f
p,
τ
qq
6
P ` σ2
ˆ a
˙
2
a
Pσ
β x eK , nβs es K y| ą nf8 p, τ q, β x R
` P |x nβ
p1
˘
f
p,
τ
qq
` 2´f5 p,δZ qn ∆pτ q
6
P ` σ2
˜ˇCc
Gˇ
¸
ˇ
ˇ
a
P σ2
ˇ
ˇ
ďP ˇ
n
p1 ` f6 p, τ qqeK , nβs es K ˇ ą nf8 p, τ q
ˇ
ˇ
P ` σ2
˙
ˆ
P σ2
p1 ˘ f6 p, τ qq ` 2´f5 p,δZ qn ∆pτ q
` P βx R
P ` σ2
♥

ď2´

1 p,τ,δ ,δ q
pn´2qf8
S Z
2N P

` 2 ¨ 2´f5 p,δZ qn ∆pτ q

—2´f9 p,τ,δS ,δZ qn ,
where we use Lemma XI.25 to get ♥ and f81 p, τ, δS , δZ q – f8 p, τ q ´

?

b
P δS ´

N P δZ
pP `σ 2 qp1´q

´

´f9 p,τ,δS ,δZ qn

?

Thus the following inequality holds with probability at least 1 ´ 2
,
b
d
s
nP P α
x´x, sQ y
`σ 2 p1 ˘ q
P αs
cosp=´x,sQ q “
P? a
“
p1 ˘ q.
}x}2 }sQ }2
N pP ` σ 2 q
nP nN p1 ´ q
On the other hand, by law of cosines, we also have
cosp=´x,sQ q “

}x}22 ` }sQ }22 ´ }yQ }22
2}x}2 }sQ }2

It follows that

“
c

}yQ }22
with probability at least 1 ´ 2´f9 p,τ,δS ,δZ qn .

“ npP ` N q ´ 2nP

nP ` nN p1 ´ q ´ }yQ }22
? a
.
2 nP nN p1 ´ q
αs
p1 ˘ q,
P ` σ2

δS δZ .

36

Fig. 27: Fix a legitimate attack vector sQ . We compute the the expected radius of the list-decoding region, which is the cap
?
?
?
?
Capn´1 pyQ , nr, nP q “ Capn´1 px ` sQ , nr, nP q shown in above figure, over codewords in the strip.
?
?
?
?
Denote by nr the radius of the intersection B n pyQ , nN ` nδS q X S n´1 p0, nP q. Staring at the triangle ∆OAO1
shown in Figure 27, we know that, with probability at least 1 ´ 2´f9 p,τ,δS ,δZ qn ,
ˆ ? ˙2
nr
?
“ psinp=AOO1 qq2 “ 1 ´ pcosp=AOO1 qq2 ,
nP
i.e.,
?
˜
¸2
?
nP ` }yQ }22 ´ p nN ` nδS q2
r
?
“1 ´
P
2 nP }yQ }2
s
N ´ P Pα
`σ 2 p1 ˘ q ` f10 p, δS q
b
P,
s
P ` N ´ 2P P α
p1
˘
q
2
`σ
´
¯
b
?
2
?
s
where f10 p, δS q “ ´ pδS `24PN δS q ` 1 ´ 12 P α
`σ 2 p1 ˘ q pδS ` 2 N δS q. Thus we have
¨
˛
s
N ´ P Pα
`σ 2
b
P p1 ˘ f11 p, δS qq‚ ď 2´f9 p,τ,δS ,δZ qn .
P ˝r R
αs
P ` N ´ 2P P `σ2

ùñ r “

(XI.26)

From James’ perspective, he aims to maximize the above quantity to worst confuse Bob. He will take the jamming strategy
corresponding to the optimal solution of the following optimization problem.
minαs

N ´P

b

αs
P `σ 2
αs
P `σ 2

P `N ´2P

subject to 0 ď αs ď N
σ2
1
P ě 1´N {P ´ 1
2
P, N, σ ě 0

(XI.27)

Notice that the objective function of the above optimization problem
b XI.27 is essentially the same as that of the optimizaαs
tion VIII.6 in scale-and-babble converse by taking a map α ÞÑ
P `σ 2 . Solving this optimization problem, we get, if we
operate at a rate
$1
`P ˘
1
σ2
1
— CLD ,
& 2 log ˆN
1´N {P ´ 1 ď P ď N {P ´ 1
˙
?
!
),
2
Ră 1
(XI.28)
2
N pP `σ 2 q
1
1
% 2 log pP `σ qpP `NNq´2P
— RLD,myop , σP ě max 1´N
σ2
{P ´ 1, N {P ´ 1
no matter along which direction James is going to push, vast majority (exponentially close to one fraction) of codewords in
the strip have small list-size. Indeed, let ropt denote the optimal solution to the above optimization.

37

Consider two types of list-decoding errors.
1) Confusing codewords in the list-decoding region come from OGS. Then conditioned on bad events aforementioned not
happening, assuming codewords in OGS are uniformly distributed (which is actually not exactly the case), averaged over
the codebook generation, the channel noise to James and the quasi-uniformly distributed codewords in the strip, the
probability that a codeword falls into the list-decoding region is
a
?
n
Ppx P B pyQ , nN ` nδS q X OrclpzQ , xqq
?
a
AreapCapn´1 p¨, nropt p1 ` f11 p, δS qq, nP qq
“
AreapStrn´1 pzQ , iqq
d
´
¯
¯
´
ropt p1 ` f11 p, δS qq n ´ 21 log rPopt ` 12 logp rPstr q`f11 p,δS q
“
,
2
rstr
which is exponentially small. Then by similar calculations to Lemma VI.5, but with quasi-uniformity taken into account,
we have
a
?
n
4 c
´Ωpn5 q
.
(XI.29)
Pp|B pyQ , nN ` nδS q X OrclpzQ , xq| ą n |E q ď 2
2) Confusing codewords in the list-decoding region do not belong to OGS.
ˇ ¯
´
a
?
ˇ c
n
pkq
E |B pyQ , nN ` nδS q X pC zOrclpzQ , xqq|ˇ E
?
a
AreapCapn´1 p¨, nropt p1 ` f11 p, δS qq, nP qq nR
?
ď
2
AreapS n´1 p0, nP qq
d
´
´
¯
¯
P
n R´ 21 log rP `f11 p,δS q
opt
“
2
,
ropt p1 ` f11 p, δS qq
which is exponentially small if R is below the threshold. Then immediately by Lemma VI.5,
a
?
pkq
4 c
´Ωpn5 q
n
.
Pp|B pyQ , nN ` nδS q X pC zOrclpzQ , xqq| ą n |E q ď 2

(XI.30)

Taking into account two types of error in Equation XI.29 and Equation XI.30, respectively, we get
pkq
4 c
c
(XI.31)
Pp|L pxpmq, sQ q| ą 2n |E X Er q
a
a
?
?
ď Pp|B n pyQ , nN ` nδS q X C pkq | ą 2n4 , |B n pyQ , nN ` nδS q X pC pkq zOrclpzQ , xqq| ď n4 q
a
?
` Pp|B n pyQ , nN ` nδS q X pC pkq zOrclpzQ , xqq| ą n4 q
a
a
?
?
ď Pp|B n pyQ , nN ` nδS q X OrclpzQ , xq| ą n4 q ` Pp|B n pyQ , nN ` nδS q X pC pkq zOrclpzQ , xqq| ą n4 |E c q
5

ď2´Ωpn q .

(XI.32)

Combining Equation XI.26 and Equation XI.32, we get
5

pkq
4 c
´Ωpn q
` 2´f9 p,τ,δS ,δZ qn ď 2´hp,τ,δS ,δZ qn .
Pp|L pxpmq, sQ q| ą 2n |E q ď 2

which completes the proof of Lemma XI.21.
Finally, each term in Equation XI.14 is well bounded and we prove that list-decoding succeeds with high probability which
completes the proof of Theorem IX.3.
In the following section, we will argue that Bob will enjoy a vanishing probability of error below the threshold given by
optimization XI.27, which matches the converse in Section VIII-A in the corresponding region.
XII. ACHIEVABILITY IN THE SUFFICIENTLY MYOPIC REGIME – FROM MYOPIC LIST- DECODING TO UNIQUE DECODING
We first sketch the roadmap to proving that Bob can uniquely decode m with high probability. From James’ point of view,
x is quasi-uniformly distributed over the strip. The probability of error is small if
‚ the total number of messages (call them confusing messages) that can confuse any message in the OGS is small (say
polypnq) with probability super-exponentially close to one;
‚ any message can only confuse a small number (say polypnq) of messages in the OGS (call them confused messages) with
probability super-exponentially close to one.
The first statement follows from a blob list-decoding argument and second follows from a reverse list-decoding argument.
Technically, we will analyze them in two cases – the case where the confusing messages come from the OGS and the case
where they are outside of the OGS. Details are elaborated in Section XII-A and Section XII-B.

38

A. Type I error
For type I error, confusing messages come from C pkq zOrclpjq pzQ , iq. We will prove that there are at most polynomially
many codewords which are erroneously decoded due to confusion with another message in outside of the OGS.
Lemma XII.1. Let E 1 denote E Y Er . Then
PpDzQ , Di, Dj, DsQ ,
|tm P Orclpjq pzQ , iq : Dm1 P r2nR szOrclpjq pzQ , iq, }xpmq ` sQ ´ xpm1 q}2 ď

?

nN `

a
nδS u| ě Ωpn2 q|E c q

“ PpDzQ , Di, Dj, DsQ ,
a
?
|tm P Orclpjq pzQ , iq : Dm1 P r2nR szOrclpjq pzQ , iq, xpm1 q P B n pxpmq ` sQ , nN ` nδS qu| ě Ωpn2 q|E c q
3

ď2´Ωpn q .
Proof. We prove the lemma using a two-step list-decoding argument. Fix zQ , i, j and sQ . Notice that txpmq P C pkq : m P
r2nR szOrclpjq pzQ , iqu are independently and uniformly distributed.
`P ˘
r
´  are pP, N, Op1{qq-listIt is a folklore (Appendix C) in the literature that a spherical code C of rate 12 log N
decodable (with exponential concentration), thus are also pP, N, Opn2 qq-list-decodable (with super-exponential concentration
by Lemma VI.5).
1) Blob list-decoding: Define
ď
a
?
Blob “
B n pxpmq ` sQ , nN ` nδS q.
mPOrclpjq pzQ ,iq

The number of codewords in the blob is expected to be
ˇ ¯
´
ˇ 1c
pkq
pjq
E |Blob X pC zOrcl pzQ , iqq|ˇ E
?
a
AreapCapn´1 p¨, nropt p1 ` f11 p, δS qq, nP qq2n nR
?
ď
2
AreapS n´1 p0, nP qq
a
AreapS n´1 p¨, nropt p1 ` f11 p, δS qqqq2n nR
?
ď
2
AreapS n´1 p0, nP qq
a
n´1
nropt p1 ` f11 p, δS qq
“
2n 2nR
? n´1
nP
d
´
´
¯ ¯
P
n R´ 21 log r p1`fP p,δ qq `
opt
11
S
2
“
ropt p1 ` f11 p, δS qq
d
´
´
¯
¯
P
n R´ 21 log rP `f11 p,δS q`
opt
2
ď
,
ropt p1 ` f11 p, δS qq
which is exponentially small. Then by LemmaVI.5, the actual number of codewords exceeds Ωpn2 q with probability at most
3
2´Ωpn q .
2) Reverse list-decoding: The expected number of codewords corresponding to messages in OGS translated by sQ lying in
?
`
˘
?
the ball B n xpm1 q, nN ` nδS for any m1 P r2nR szOrclpjq pzQ , iq is
ˇ ¯
´
a
?
ˇ 1c
n
1
E |B pxpm q, nN ` nδS q X ptxpmqumPOrclpjq pzQ ,iq ` sQ q|ˇ E
ˇ ¯
´
a
?
ˇ
“ E |B n pxpm1 q ´ sQ , nN ` nδS q X txpmqumPOrclpjq pzQ ,iq |ˇ E 1c
?
?
AreapS n´1 p¨, nN ` nδS qq
n
ď
1 , O 1 , ?nr , ?nr qq 2
AreapStrn´1 pO´
´
`
`
?
?
AreapS n´1 p¨, nN ` nδS qq
?
?
“
2n
1 , ?nr , nP qq ´ AreapCapn´1 pO 1 , ?nr , nP qq
AreapCapn´1 pO`
`
´
´
?
?
AreapS n´1 p¨, nN ` nδS qq
n
ď
1 , ?nr qq ´ AreapS n´1 pO 1 , ?nr qq 2
VolpB n´1 pO`
`
´
´
ˆ
˙
ˆ
˙
c
1
P?
1
P
n
´
log
`
log
`
p
q
N
1
2
2
rstr
N `δS `2 N δS
ď
2
1
1
rstr
2pn´1q 2 logp1`τ q´Θplog nq ´ 2pn´1q 2 logp1´τ q

39

c
“
c
♥

ď

ˆ

N n
2
rstr
N
2
rstr

ˆ
P
´ 21 logp N
q´ 12 log 1´

ˆ
P
n ´ 21 logp N
q` 12 logp rP

str

?

δS `2 N δS
?
N `δS `2 N δS

˙

˙
` 12 logp rP

str

?
Nδ
? S

δS `2

q`2 N `δS `2

N δS

1

q`

1
2pn´1q 2 logp1`τ q´Θplog nq

˙
`

1

´ 2pn´1q 2 logp1´τ q

1
1
2pn´1q 2 logp1`τ q´Θplog nq

1

´ 2pn´1q 2 logp1´τ q

,

where we use logp1 ´ xq ě ´2x for small enough x ą 0. The above quantity is exponentially small according to the sufficient
3
myopicity assumption. Thus the actual number is less than Ωpn2 q with probability at least 1 ´ 2´Ωpn q .
3) Union bound: By Section XII-A1 and Section XII-A2, for any zQ , i, j and sQ , there are at most Opn4 q messages
3
from Orclpjq pzQ , iq satisfying the condition in the lemma with probability at most 2´Ωpn q . Finally, a union bound over all
assumptions we have made completes the proof.
B. Type II error
For type II error, confusing messages come from Orclpjq pzQ , iq. We will prove that there are at most polynomially many
codewords which are erroneously decoded due to confusion with another message in the same OGS.
Lemma XII.2.
ˆ
P DzQ , Di, Dj, DsQ ,
|tm P Orclpjq pzQ , iq : Dm1 P Orclpjq pzQ , iq, m1 ‰ m, }xpmq ` sQ ´ xpm1 q}2 ď

?

nN `

ˇ ˙
a
polypnq ˇ
nδS u| ě n{2 ˇˇE c
2

ď2´Ωpnq .
?
Proof. Notice that for different m P Orclpjq pzQ , iq, the events tDm1 P r2nR szOrclpjq pzQ , iq, xpm1 q P B n pxpmq ` sQ , nN `
?
nδS qu are not independent. This issue is resolved by arranging messages in OGS into a 2n{2 ˆ 2n{2 square matrix M
lexicographically and applying blob list-decoding and reverse list-decoding to any row or column, denoted R, of M. Again,
using Lemma VI.5, it suffices to bound the expected blob list-size and reverse list-size from above by some exponentially
small quantity.
1) Blob list-decoding: The expected number of codewords in the intersection of the blob and the codewords corresponding
to the OGS is
ˇ ¯
´
ˇ 1c
pjq
E |Blob X pOrcl pzQ , iqzRq|ˇ E
?
a
AreapCapn´1 p¨, nropt p1 ` f11 p, δS qq, nP qq2n n{2
ď
2
∆pτ q
1 , O 1 , ?nr , ?nr qq
AreapStrn´1 pO´
´
`
`
d
¯
´
´
¯
ropt p1 ` f11 p, δS qq n ´ 21 log ropt p1`fP p,δ qq ` 21 logp rPstr q`3{2
∆pτ q
11
S
ď
2
1
pn´1q
logp1`τ
q´Θplog
nq ´ 2pn´1q 21 logp1´τ q
rstr
2
2
d
´
¯
´
¯
ropt p1 ` f11 p, δS qq n ´ 21 log rPopt ` 12 logp rPstr q`f11 p,δS q`3{2
∆pτ q
ď
2
.
1
pn´1q
logp1`τ
q´Θplog
nq ´ 2pn´1q 12 logp1´τ q
rstr
2
2
2) Reverse list-decoding: The expected number of messages in the row (column) which can be confused by a single message
is
ˇ ¯
´
a
?
ˇ 1c
1
n
E |B pxpm q, nN ` nδS q X ptxpmqumPR ` sQ q|ˇ E
ˇ ¯
´
a
?
ˇ
“ E |B n pxpm1 q ´ sQ , nN ` nδS q X txpmqumPR |ˇ E 1c
?
?
AreapS n´1 p¨, nN ` nδS qq
n{2
ď
∆pτ q
1 , O 1 , ?nr , ?nr qq 2
AreapStrn´1 pO´
´
`
`
ˆ
˙
?
c
δS `2 N δS
P
?
`{2
q` 12 logp rPstr q`2 N `δ
N n ´ 21 logp N
∆pτ q
S `2 N δS
ď
2
.
1
pn´1q
logp1`τ
q´Θplog
nq ´ 2pn´1q 21 logp1´τ q
rstr
2
2
3) Grid argument: By Section XII-B1 and Section XII-B2, for any zQ , i, j, sQ and R, there are at most Opn2 q ¨ Opn2 q “
Opn4 q messages satisfying the condition in the lemma. Thus there are at most 2 ¨ 2n{2 Opn4 q such “bad” messages in M, i.e.,
the OGS. A union bound over zQ , i, j and sQ completes the proof.

40

XIII. C ONCLUDING REMARKS / FUTURE DIRECTIONS
In this work, we studied the capacity of a myopic adversarial channel with quadratic constraints. We did so for different
amounts of common randomness, and were able to find a complete characterization for certain regimes of the noise-to-signal
ratios of Bob and James.
1) For different regimes of the NSRs (Figs. 7, 6, 4, and 5), we were able to characterize the capacity in the red, blue and
grey regions. We only have nonmatching upper and lower bounds on the capacity in the green and white regions.
2) We also derived a myopic list-decoding result in the general case when Alice and Bob share a linear amount of common
randomness. We believe that this is a useful technique that is worth exploring for general channels.
3) When Alice uses a deterministic encoder, we believe that an improved converse using linear programming-type bounds
might be obtained in the green and white regions.
4) The z-aware symmetrization argument could also be extended to obtain Plotkin-type upper bounds on the rate in the green
and white regions.
5) We also believe that superposition codes could be used to obtain improved achievability results in the green and white
regions for the case when there is no common randomness. In particular, we feel that rates exceeding RGV should be
achievable using superposition codes in the green and white regions.
6) A natural problem is to find the minimum amount of common randomness required to achieve the capacity in Fig. 2. We
know for certain values of the NSRs, this is achievable with no common randomness (blue and red regions in Fig. 7).
Even Θplog nq bits is sufficient to achieve RLD in the entire red region in Fig. 2, while the blue region can be expanded
with increasing amounts (Ωpnq bits) of shared secret key. A lower bound on nkey needed to achieve capacity along the
lines of [18] would be of interest.
7) In this article, we studied the impact of an adversary who has noncausal access to a noisy version of the transmitted
signal. However, in reality, James can only choose his attack vector based on a causal observation of the transmission.
Li et al. [17] have some recent results for the quadratically constrained adversarial channel where the jammer can choose
the ith symbol of his transmission based on the first i symbols of the transmitted codeword. An interesting direction is
to look at the impact of myopicity in this setup.
8) Our work was inspired by the study of the discrete myopic adversarial channel [13]. A part of their work involved studying
the capacity of a binary channel with a bit-flipping adversary who can flip at most np bits of the transmitted codeword
(for some 0 ă p ă 1{2). The adversary can choose his attack vector based on a noncausal observation of the output of a
binary symmetric channel with crossover probability q. Dey et al. [13] observed that if q ą p (sufficiently myopic), then
the adversary is essentially “blind,” i.e., the capacity is equal to 1 ´ Hppq. This is what one would obtain when James
were oblivious to the transmitted codeword. In other words, as long as the channel from Alice to Bob has capacity greater
than that of the channel seen by James, the damage that James can do is minimal. What we observe in the quadratically
constained case is slightly different. A sufficient condition for our results to go through is that the list-decoding capacity
for Bob be greater than the Shannon capacity for the channel seen by James. Even then, we can never hope to achieve
P
q for any finite σ. What we can achieve is the myopic list-decoding capacity. In the
the oblivious capacity 21 logp1 ` N
bit-flipping adversarial case, the list-decoding capacity is equal to the capacity of the channel with an oblivious adversary.
No amount of myopicity can let us obtain a higher list-decoding capacity. However, the two capacities are different in
the quadratically constrained scenario.
9) The difference between oblivious and list-decoding capacities might explain the gap between the upper and lower bounds
for general discrete myopic adversarial channels [13]. Our technique of using myopic list-decoding could potentially be
used to close this gap in certain regimes.
10) While the use of list-decoding as a technique for obtaining capacity of general AVCs is not new [15], we believe that
myopic list-decoding and reverse list-decoding can be generalized to arbitrary AVCs to obtain results even in the case
where the encoder-decoder pair do not share common randomness.
A PPENDIX A
TABLE OF NOTATION
Symbol
C
C

Description
Capacity
Codebook

CAWGN
C pkq

Capacity of AWGN channels
Codebook shared by Alice and Bob specified by
common randomness k
Shorthand notation for the union of several error
events

E

Value/Range
lim supnÑ8 Rpnq
txpm,?
kq : m P r2nR s, k P r2nkey su Ď
n
B p0,` nP q ˘
1
P
2 log 1 ` N
nR
C pkq “ txpm, kqu2m“1
E “ Eatyp Y Estr Y Eorcl

41

E1

P

Shorthand notation for the union of several error
events
The error event that James’ observation behaves
atypically
The error event that the any list-size is too large
The error event that the transmitted codewords
falls into the last OGS in a strip
The error event that the radius of the listdecoding region of messages in OGS behaves
atypically
The error event that there are not enough codewords in a strip
Gaussian part of scale-and-babble attack
Common randomness shared by Alice and Bob
Number of OGSs in a strip
List of xpmq ` s
List of xpmq ` sQ
Message held by Alice
Bob’s reconstruction
Set of codewords in Strn´1 pzQ , iq
?
James’ power constraint, i.e., }s}2 ď nN
Blocklength/number of channel uses
Amount of common randomness
Oracle-given set
The oracle-given set containing the transmitted
x
?
Alice’s power constraint, i.e., }x}2 ď nP

R
Rcode

Rate
Codebook rate

Eatyp
Eerr
Eorcl
Er

Estr
g
k
`
Lpkq pxpmq, sq
Lpkq pxpmq, sQ q
m
p
m
Mstr pzQ , iq
N
n
nkey
Orclpjq pzQ , iq
OrclpzQ , xq

RGV

Rkey
RLD
RLP

Gilbert–Varshamov bound, a lower bound on
capacity of quadratically constrained omniscient
adversarial channels
Key rate
List-decoding capacity of quadratically constrained omniscient adversarial channels
Linear programming bound, an upper bound
on capacity of quadratically constrained
omniscient adversarial channels

RLD,myop

N/A

RRankin

Rankin bound, an upper bound on capacity of
quadratically constrained omniscient adversarial
channels
n´1
Radius
region
? Cap ?pxpmq `
? of list-decoding
n
sQ , nrq “ B pxpmq ` sQ , nN ` nδS q for
m P OrclpzQ , xq
Optimal solution to optimization XI.27
?
Radius nrstr of a strip
?
An optimal covering of?B n p0, nP q with quantization error at most nδS
Strip
James’ attack vector
Quantization of s

r

ropt
rstr
S
Strn´1 pzQ , iq
s
sQ

E 1 “ E Y Er
See Equation XI.9
See Equation XI.13
See Item XI-C
See Equation XI.15

See Equation XI.11
g „ N p0, γ 2 In q
k P t0, 1unkey
` “ r|Mstr pzQ , iq|{2n s
?
B n pxpmq ` s, ?
nN q X C pkq
?
n
B pxpmq ` sQ , nN ` nδS q X C pkq
m „ U pr2nR sq
p P t0, 1unR
m
zQ P Z, i P t´{δ ` 1, ¨ ¨ ¨ , {δu
N P Rą0
n P Zą0
nkey “ nRkey
zQ P Z, i P t´{δ ` 1, ¨ ¨ ¨ , {δu, j P r`s
OrclpzQ , xq “ Orclpιq pzQ , iq
P P Rą0
log |C pkq |
n

P Rě0
Rcode´“ R ` Rkey
¯ “
1
2

log

2

P
4N pP ´N q

log |C|
n

1tP ě2N u

Rkey `“ n˘key {n
1
P
2 log N
pα log α ´ β log?
βq1tP ě2N u ,

?
P `2 N pP ´N q
P ´2 N pP ´N q
where α “ ?
,β “ ?
4 N pP ´N q
4 N pP ´N q
ˆ
˙
?
pP `σ 2 qpP `N q´2P N pP `σ 2 q
1
log
2
N σ2
`P ˘
1
2 log 2N 1tP ě2N u
See Equation XI.26

See Equation XI.28
σ2
rstr R PP`σ
2 p1 ˘ q w.h.p.
|S|

S “ tsQ piq ui“1
zQ P Z, i P t´{δ ` 1, ¨ ¨ ¨ , {δu
?
s P B n p0, nN q
sQ P S

42

sz „ N p0, σ 2 In q
xPC
?
?
y “ x ` s P B n p0, nP ` nN q
|Z|
Z “ tzQ piq ui“1

z
zQ

AWGN to James
Alice’s transmitted codeword
Bob’s observation
An
covering
of
a optimal
Shn p0, npP?` σ 2 qp1 ˘ qq with quantization
error at most nδZ
James’ noisy observation of x
Quantization of z

∆pτ q

Quasi-uniformity factor

maxz maxi
´
¯
O logn n

sz
x
y
Z

z “ x ` sz P Rn
zQ P Z
maxxPStrn´1 pz
minxPStrn´1 pz

δ

Thickness of a strip (See Equation XI.16)

δS

Op1q


ρ
σ

Quantization
? error parameter for1 s, i.e., for any
s P B n p0, ?
nN q, there exists s P S, such that
}s ´ s1 }2 ď nδS
Quantization a
error parameter for s, i.e., for any
z P Shn p0, npP ` σ 2 qp1 ˘?qq, there exists
z 1 P Z, such that }z ´ z 1 }2 ď nδZ
N/A
N/A
Standard deviation of channel noise to James

τ

Thickness of a strip (See Equation XI.17)

O

χpzQ , i, j, sQ q

Number of codewords in an OGS with large listsize

See Equation XI.12

δZ

Q ,iq

Q

px|zQ px|zQ q

,iq px|zQ px|zQ q

Op1q

Op1q
Op1q
a
Varpsz¯q
´
log n
n

TABLE II: Table of notation.

A PPENDIX B
S TOCHASTIC VS . DETERMINISTIC ENCODING AGAINST AN OMNISCIENT ADVERSARY
pnq

pnq

pnq

pnq

Suppose we are given a sequence of pn, Rstoch , P, N q stochastic codes Cstoch “ txpm, kq : m P r2nRstoch s, k P r2nRkey su of
pnq
blocklength n, rate Rstoch , satisfying maximum power constraint P for Alice and maximum power constraint N for James,
nÑ8
pnq
pnq
pnq
pnq
with average probability of error Pe,stoch Ñ 0. Fix any n, we turn Cstoch into a pn, Rdet , P, N q deterministic code Cdet .
pnq
pnq
The decoder associated with Cstoch partitions Rn (the space that James’ observation y lives in) into 2nRstoch cells tY pnq pmq Ă
?
?
pnq
Rn : m P r2nRstoch su, where Y pnq pmq “ ty P B n p0, nP ` nN q : Decpyq “ mu. Collect all “good” messages into
pnq
p ‰ m|m “ mq ă 1u. For any good message m P Mpnq , there must exist at least one “good”
Mpnq “ tm P r2nRstoch s : P pm
codeword xpm, kq such that
?
px|m pxpm, kq|mq ą 0, @s P B n p0, nN q, xpm, kq ` s P Y pnq pmq.
?
The second condition is equivalent to B n pxpm, kq, nN q Ď Y pnq pmq, i.e., James does not have enough power to push
xpm, kq outside of Y pnq pmq. For any good message, take any one of good codewords and we get a deterministic codebook
pnq
pnq
pnq
Cdet “ txpm, ¨q P Cstoch : xpm, ¨q is good, m P r2nRstoch su. We then argue that this deterministic code with the same decoding
region partition restricted to the messages in Mpnq enjoys a vanishing probability of error and asymptotically the same rate
pnq
pnq
Rdet “ limnÑn Rstoch as Cstoch .
pnq

pnq
Pe,stoch

“
ě

1
pnq

2nRstoch
1
pnq
nRstoch

2
“

2nR
ÿstoch

1
pnq

2nRstoch

p ‰ m|m “ mq
Ppm

m“1
pnq

p ‰ m|m “ mq “ 1u|
|tm P r2nRstoch s : Ppm
|pMpnq qc |

“ Ppm R Mpnq q Ñ 0.

43

Define e “ 1tmPMpnq u . We have
pnq

nRstoch “Hpmq
“Hpeq ` Hpm|eq
“Hpeq ` Ppe “ 1qHpm|e “ 1q ` Ppe “ 0qHpm|e “ 0q
“Hpeq ` Ppm P Mpnq qHpm|m P Mpnq q ` Ppm R Mpnq qHpm|m R Mpnq q.
It follows that
1
pnq
Rdet “ Hpm|m P Mpnq q
n
1
pnq
“
pnRstoch ´ Hpeq ´ Ppm R Mpnq qHpm|m R Mpnq qq
n P pm P Mpnq q
1
pnq
pnq
pnq
pnRstoch ´ 1 ´ Pe,stoch nRstoch q
ě
pnq
n P pm P M q
ˆ
˙
1
1
pnq
pnq
“
p1 ´ Pe,stoch qRstoch ´
n
1 ´ P pm R Mpnq q
pnq

Ñ lim Rstoch .
nÑ8

A PPENDIX C
Q UADRATICALLY CONSTRAINED LIST- DECODING CAPACITY
A. Achievability.
nR

2
We use a random spherical code, i.e., the 2nR codewords
? C “ txpmqum“1 are chosen independently? and uniformly at
random from the Euclidean sphere centered at 0 of radius nP
? . Since
? James has a power constraint of nN , the received
vector y “ x ` s is guaranteed to lie within the shell Shn p0, nP ˘ nN q. We will prove the following stronger result:

Lemma C.1. There exists a constant c ą 0 independent of n and , but possibly on P, N , and R, such that
ˆ
˙
?
?
?
1
1
n
n
ě 1 ´ 2´Ωpnq .
P @y P Sh p0, nP ˘ nN q, |B py, nN q X C| ă c log


Proof. Let L be the desired list-size. At first, we increase the list radius by a small amount. As we will see later, this will be
helpful when we take a union bound over possible y’s. Define δ – N 2 {8. We
? that for any fixed y, the probability
? first show
nN
`
nδ from y is sufficiently small.
(over the codebook) that
there
are
more
than
L
codewords
within
a
distance
?
?
?
?
?
Observe that |B n py, nN ` nδq X C| “ |Capn´1 py, nN ` nδ, nP q X C|. We claim that for any fixed y,
´
¯
?
?
n
1 ´npL`1q{2
.
(C.2)
P |B py, nN ` nδq X C| ą L ď c 2
for some constant c1 independent of n and .?
?
?
The maximal intersection of a ball B n py, nN ` nδq and the Euclidean sphere S n´1 p0, nP q is shown in Figure 28.
The probability of a codeword falling into the cap can be upper bounded by
´
¯
?
?
?
p – P x P Capn´1 py, nN ` nδ, nP q
?
?
?
AreapCapn´1 py, nN ` nδ, nP qq
?
“
AreapS n´1 p0, nP qq
?
?
AreapS n´1 py, nN ` nδqq
?
ď
AreapS n´1 p0, nP qq
c ¸n´1
ˆ ˙pn´1q{2 ˜
N
δ
“
1`
P
N
´
´ ? ¯¯
P
δ
´ n´1
logp N
`2 log 1` N
q
2
“2
´
?δ¯
P
´n 12 logp N
`2 N
q
ďc1 2
1
P

“c 2´np 2 logp N q` 2 q ,
1

44

?
Fig. 28: Maximal intersection of the decoding ball with the sphere S n´1 p0, nP q.
b
where c1 –

P
N.

In the last step, we have used the fact that δ “ N 2 {8. Now consider the left-hand side of (C.2).
´
¯
?
?
?
n´1
py, nN ` nδ, nP q X C| ą L
P |Cap
nR
2ÿ

˙
nR
2nR i
“
p p1 ´ pq2 ´i
i
i“L`1
ˆ nR ˙
2
ď2nR
pL`1
L`1
ˆ nR ˙L`1 ´
¯L`1
1
P
n
2 e
nR
c2´n 2 logp N q` 2
ď2
L`1
P
nR`npL`1qpR´ 12 logp N
q` 2 q
“c 2
ˆ

(C.3)

2

“c2 2´npL`1q{2`nR ,
´
where c2 –

ec1
L`1

(C.4)

¯L`1

. Since we are interested in constant list-sizes, c2 does not depend on n.
?
?
?
Define Y to be?an optimal
covering of Shn p0, nP ˘ nN?
q by balls of radius nδ.
?
? In other
? words, Y is a finite set of
points in Shn p0, nP ˘ nN q such that miny1 PY }y ´ y 1 } ă nδ for all y P Shn p0, nP ˘ nN q. In addition, Y is the
smallest (in cardinality) over all possible coverings. One can achieve (for e.g., using lattice codes [22, Chapter 2])
¸1`op1q ˜ ?
˜
?
? ¸np1`op1qq
?
?
?
´ c ¯n
P` N` δ
VolpB n p0, nP ` nN ` nδqq
3
?
?
“
—
|Y| ď
.
(C.5)

VolpB n p0, nδqq
δ

We now have everything to prove Lemma C.1.
´
¯
?
?
?
?
n
n´1
py, nN , nP q X C| ą L
P Dy P Sh p0, nP ˘ nN q, |Cap
´
¯
?
?
?
ď P DyQ P Y, |Capn´1 pz, nN ` nδ, nP q X C| ą L
¯
ÿ ´
?
?
?
n´1
ď
pz, nN ` nδ, nP q X C| ą L
P |Cap
yQ PY

Now using (C.5) and (C.4), we have
´
¯
?
?
?
?
n
n´1
py, nN , nP q X C| ą L
P Dy P Sh p0, nP ˘ nN q, |Cap

45

ďc2 2´npL`1q{2`nR

´ c ¯n
3



“2´Ωpnq
as long as
pL ` 1q{2 ´ R ´ log
or equivalently, L ą c 1 log

1


´c ¯
3



ą0

for a suitable constant c. This completes the proof of Lemma C.1.

B. Converse.
`P ˘
`  with 2nR codewords (not necessarily randomly) chosen from
We will
show that for any code C of rate R “ 12 log N
?
n´1
S
p0, nP q, there must some y with list-size exceeding Op1{q. First notice that p can be lower bounded by
?
VolpB n´1 p0, nN qq
?
pě
AreapS n´1 p0, nP qq
ˆ?
˙ ˆ ˙pn´1q{2
1
2
N
´3{2
? ` Opn
“ ?
q
2 π
n
P
ˆ ˙n{2
N
“cn
P
P
´n 12 logp N
q,
“cn 2
¯b
´?
P
where cn – 2?1 π ?n2 ` Opn´3{2 q
N . The expected number of codewords in the intersection is
?
?
1
P
n´1
py, nN , nP q X C|q “ p2nR ě cn 2npR´ 2 logp N qq “ cn 2n .
Ep|Cap
a
?
As x’s are not necessarily uniformly distributed on S n´1 p0, nP q, there must exist some y in S n´1 p0, npP ´ N qq such
that
?
?
?
?
|Capn´1 py, nN , nP q X C| ě
p|Capn´1 py, nN , nP q X C|q ě cn 2n .
E ?
x„U pS n´1 p0, nP qq

By the black-box reduction from ball codes to spherical codes in Proposition 2.1 in Cohn–Zhao’s paper [5], this converse holds
for any code satisfying Alice’s power constraint.
A PPENDIX D
P ROOF OF C LAIM VIII.4
We want to prove that the scale-and-babble attack instantiates a channel whose capacity is equal to that of an equivalent
AWGN channel.
We begin with the following observation, which follows from a simple application of the chain rule of mutual information.
Lemma D.1. Consider any joint distribution px,y on px, yq such that x has differential entropy which grows as 2opnq . Let ξ
be a t0, 1u-valued random variable (possibly depending on x, y) that takes value 0 with probability 2´cn for some constant
c ą 0. Then, Ipx; yq P Ipx; y|ξξ “ 1qp1 ´ 2´cn q ` 2´cnp1´op1qq ˘ 1.
r – p1 ´ αqz ` g. The channel from x to y
r is a standard AWGN channel with capacity (VIII.5). Let ξ be the indicator
Let y
random variable which is equal to 1 if β “ 1 (i.e., if James’ power constraint is satisfied), and zero otherwise. Clearly,
r |ξξ “ 1q “ Ipx; y|ξξ “ 1q.
Ipx; y
Lemma D.2.
´Ωpnq
.
Ppξξ ‰ 1q “ 2

Proof. Recall that
g ´ αsz „ N p0, pγ 2 ` α2 σ 2 qIn q “ N p0, pN ´ α2 P ´ pN ´ α2 pP ` σ 2 qqqIn q — N p0, pN ´ α2 P ´ 1 qIn q.
Now we can bound the probability
?
Ppξξ ‰ 1q “ Pp} ´ αz ` g}2 ą nN q
“ Ppα2 }x}22 ` }g ´ αsz }22 ´ 2xαx, g ´ αsz y ą nN q

46

ď Pp}g ´ αsz }22 ´ 2xαx, g ´ αsz y ą npN ´ α2 P qq
“ Pp}g ´ αsz }22 ´ 2xαx, g ´ αsz y ą npN ´ α2 P q, 2|xαx, g ´ αsz y| ą n1 {2q
` Pp}g ´ αsz }22 ´ 2xαx, g ´ αsz y ą npN ´ α2 P q, 2|xαx, g ´ αsz y| ď n1 {2q
ˇ
`
˘
ď Pp2|xαx, g ´ αsz y| ą n1 {2q ` P }g ´ αsz }22 ´ 2xαx, g ´ αsz y ą npN ´ α2 P qˇ 2|xαx, g ´ αsz y| ď n1 {2
ď Pp|xαx, g ´ αsz y| ą n1 {4q ` Pp}g ´ αsz }22 ą npN ´ α2 P ´ 1 {2qq .
P1

P2

We bound P1 and P2 separately.
P1 “ Pp|N p0, α2 }x}22 pN ´ α2 P ´ 1 qq| ą n1 {4q
˙
ˆ
pn1 {4q2
ď2 exp ´ 2 2
2α }x}2 pN ´ α2 P ´ 1 q
ˆ
˙
12
ď2 exp ´
n
32α2 P pN ´ α2 P ´ 1 q
1

—2´g1 p qn ,
and
P2 “ Pp}N p0, pN ´ α2 P ´ 1 qIn q}22 ą npN ´ α2 P ´ 1 {2qq
ˆ
˙* ˙
ˆ"
1 {2
n
1 {2
` ln 1 `
ď exp
´
2
1
2
1
N ´α P ´
N ´α P ´
2
˜
ˆ
˙2 ¸
1
n
1
 {2
ď exp ´
4 N ´ α 2 P ´ 1
2
˙
ˆ
12

n
“ exp ´
32pN ´ α2 P ´ 1 q2
1

—2´g2 p qn .

r qp1 ` op1qq. Here we have used the fact that x is power
Using Lemmas D.1 and D.2, we have that Ipx; yq ď Ipx; y
constrained, and hence has differential entropy Θpnq.
The rest of the proof follows along the same lines as the standard converse for the AWGN channel [23, Sec. 9.2]. Let us
briefly outline the steps involved.
As a first step, note that Fano’s inequality still holds even in the presence of common randomness. Let k denote the shared
p and Pe , respectively, denote the message chosen, Bob’s estimate of the message, and the
secret key. Specifically, if m, m,
probability of error, then
p kq ď Hpm|mq
p ď HpPe q ` nRPe ,
Hpm|m,
where the first step follows because conditioning reduces entropy, and the second follows from (standard) Fano’s inequality.
Now, if we demand that the probability of error be vanishingly small in n, then
p
p kq
nR “ Hpmq “ Hpm|kq “ Ipm; m|kq
` Hpm|m,
p
ď Ipm; m|kq
` opnq
ď Ipx; y|kq ` opnq
r |kqp1 ` op1qq ` opnq
ď Ipx; y
ˆ
˙
1
p1 ´ αq2 P
ď log 1 ` 2 2
.
2
α σ ` γ2

(D.3)

We have skipped a number of arguments in obtaining the last step, but these follow from the standard converse proof for the
AWGN channel. The only property of the codebook used there is that it satisfies an average power constraint (which is indeed
satisfied as we have a more restrictive max power constraint). This completes the proof of Claim VIII.4.

47

A PPENDIX E
Q UASI - UNIFORMITY – P ROOF OF L EMMAS XI.20
First, we argue that rstr behaves typically with high probability. By the geometric alignment of Alice’s transmission and
James’ observation, we have the following formula
nrstr “

}x}22 }sz }22
p1 ´ pcosp=x,sz qq2 q.
}z}22

As the codewords lies on the sphere and the channel noise is Gaussian, the value of rstr is concentrated.
˙
ˆ
P σ2
p1 ˘ q
P rstr R
P ` σ2
ˆ
˙
}x}22 }sz }22
nP σ 2
2
“P
p1 ´ pcosp=x,sz qq q R
p1 ˘ q
}z}22
P ` σ2
˜
¸
}sz }22
σ2
1˘
R
, | cosp=x,sz q| ă  ` Pp| cosp=x,sz q| ě q
ďP
}z}22
P ` σ 2 1 ´ pcosp=x,sz qq2
˙
ˆ
}sz }22
σ2
1˘
R
“P
` 2´f2 pqn
}z}22
P ` σ 2 1 ˘ 2
ˆ
˙
σ2
2
2 1˘
2
2
ď P }sz }2 R
}z}2
, }z}2 P npP ` σ qp1 ˘ q ` Pp}z}22 R npP ` σ 2 qp1 ˘ qq ` 2´f2 pqn
P ` σ2
1 ˘ 2
ˆ
˙
σ2
2 1˘
npP
`
σ
q
p1
¯
q
` 2´f3 pqn ` 2´f2 pqn
ď P }sz }22 R
P ` σ2
1 ˘ 2
ˆ
˙
p1 ˘ qp1 ¯ q
“ P }sz }22 R nσ 2
` 2´f3 pqn ` 2´f2 pqn
1 ˘ 2
— Pp}sz }22 R nσ 2 p1 ˘ 4 qq ` 2´f3 pqn ` 2´f2 pqn
ď2´f1 p4 qn ` 2´f3 pqn ` 2´f2 pqn
—2´f12 pqn .
?
Define |xO1 | – nrstr . By the construction of the strip,
a
1 | – ?nr –
|x´ O´
nrstr p1 ´ τ q,
´

1 |–
|x` O`

?

nr` –

a
nrstr p1 ` τ q.

Then the quasi-uniformity factor can be computed as follows
˜
¸N˜
sup ?
px|zpx|zq
?

¸

px|zpx|zq
inf
1 ,O 1 ,?nr ,?nr q
xPStr n´1 pO´
´
`
`

1 ,O 1 , nr , nr q
xPStr n´1 pO´
´
`
`

px|z px´ |zq
px|z px` |zq
px,z px´ , zq
“
px,z px` , zq
ˆ
˙
}z ´ x` }22 ´ }z ´ x´ }22
“ exp
2σ 2
˜
¸
a
a
}z}2 p npP ´ r´ q ´ npP ´ r` qq
♥
“ exp
σ2
˜
¸
}z}2
2nrstr τ
a
a
“ exp
,
σ2
npP ´ r´ q ` npP ´ r` q
“

where ♥ holds since
}z ´ x˘ }22 “ nr˘ ` p}z}2 ´

a

nP ´ nr˘ q2 “ }z}22 ` nP ´ 2}z}2

a

nP ´ nr˘ .

A PPENDIX F
E XPONENTIALLY MANY CODEWORDS IN THE STRIP – PROOF OF L EMMA XI.20
We compute the expected number of codewords in the strip
?
n´1
1
1 ?
pO´
, O`
, nr´ , nr` q X C|q
Ep|Str

48

?
?
1 ?
1 ?
AreapCapn´1 pO`
, nr` , nP qq ´ AreapCapn´1 pO´
, nr´ , nP qq nRcode
?
ě
2
∆pτ q´1
AreapS n´1 p0, nP qq
1 ?
1 ?
VolpB n´1 pO`
, nr` qq ´ AreapS n´1 pO´
, nr´ qq nRcode
?
ě
2
∆pτ q´1
n´1
AreapS
p0, nP qq
˛
¨
?
?
n´1
π pn´1q{2
n´1
nr
`
nr´
Γppn´1q{2`1q
´ ? n´1 ‚2nRcode ∆pτ q´1
“˝
? n´1
2π n{2
nP
Γpn{2q nP
"
ˆ?
*
˙´ ¯
1
2
r` pn´1q{2 ´ r´ ¯pn´1q{2 nRcode
♥
´3{2
? ` Opn
“ ?
´
2
q
∆pτ q´1
2 π
n
P
P
"
¯pn´1q{2 ´ r
¯pn´1q{2 *
´r
str
str
´1{2
p1 ` τ q
´
p1 ´ τ q
2nRcode ∆pτ q´1
“ Θpn
q
P
P
´
¯
rstr
rstr
1
1
1
1
“ 2pn´1qp 2 logp P q` 2 logp1`τ qq´Θplog nq ´ 2pn´1qp 2 logp P q` 2 logp1´τ qq 2nRcode ∆pτ q´1
c
¯
1
P ´n 21 logp rP q ´ pn´1q 1 logp1`τ q´Θplog nq
2
str
2
“
2
´ 2pn´1q 2 logp1´τ q 2nRcode ∆pτ q´1 ,
rstr
Γpn{2q
where ♥ follows from Taylor expansion of Γppn´1q{2`1q
. The factor in the parentheses is a polynomial in n when τ “
Opplog nq{nq. By operating at a rate slightly above the threshold with a tiny but enough slack, we have at least 24n codewords
in every strip.

R EFERENCES
[1] D. Blackwell, L. Breiman, and A. J. Thomasian, “The capacity of a class of channels under random coding,” Ann. of Mathematical Statistics, vol. 31,
no. 3, pp. 558–567, 1960.
[2] N. Blachman, “On the capacity of bandlimited channel perturbed by statistically dependent interference,” IRE Transactions on Information Theory, vol. 8,
pp. 48–55, 1962.
[3] R. Rankin, “The closest packing of spherical caps in n dimensions,” Proc. Glasgow Math. Assoc., vol. 2, pp. 139–144, 1955.
[4] G. A. Kabatiansky and V. I. Levenshtein, “On bounds for packings on a sphere and in space,” Problemy Peredachi Informatsii, vol. 14, no. 1, pp. 3–25,
1978.
[5] H. Cohn and Y. Zhao, “Sphere packing bounds via spherical codes,” Duke Mathematical Journal, vol. 163, no. 10, pp. 1965–2002, 2014.
[6] B. Hughes and P. Narayan, “Gaussian arbitrarily varying channels,” IEEE Trans. Inf. Theory, vol. 33, pp. 267–284, 1987.
[7] I. Csiszár and P. Narayan, “Capacity of the Gaussian arbitrarily varying channel,” IEEE Trans. Inf. Theory, vol. 37, pp. 18–26, 1991.
[8] A. Sarwate, “An AVC perspective on correlated jamming,” in Proc. IEEE Int. Conf. Signal Proc. and Comm., Bangalore, India, 2012.
[9] F. Haddadpour, M. Siavoshani, M. Bakshi, and S. Jaggi, “On AVCs with quadratic constraints,” IEEE International Symposium on Information Theory,
2013.
[10] M. Médard, “Capacity of correlated jamming channels,” in Proc. Allerton Annual Conf. on Comm., Control and Computing, Allerton, USA, 1997.
[11] S. Shafiee and S. Ulukus, “Mutual information games in multi-user channels with correlated jamming,” IEEE Trans. Inf. Theory, vol. 55, pp. 4598–4607,
2009.
[12] C. Baker and I.-F. Chao, “Information capacity of channels with partially unknown noise. i. finite-dimensional channels,” SIAM Journal on Applied
Mathematics, vol. 56, pp. 946–963, 1996.
[13] B. K. Dey, S. Jaggi, and M. Langberg, “Sufficiently myopic adversaries are blind,” in Information Theory (ISIT), 2015 IEEE International Symposium
on, 2015, pp. 1164–1168. [Online]. Available: https://arxiv.org/abs/1610.01287
[14] B. K. Dey, S. Jaggi, M. Langberg, and A. D. Sarwate, “The benefit of a 1-bit jump-start, and the necessity of stochastic encoding, in jamming
channels,” ArXiV, Tech. Rep. arXiv:1602.02384 [cs.IT], February 2016. [Online]. Available: http://arxiv.org/abs/1602.02384
[15] A. Sarwate, “Robust and adaptive communication under uncertain interference,” Ph.D. dissertation, University of California, Berkeley, 2008.
[16] I. Csiszár and P. Narayan, “The capacity of the arbitrarily varying channel revisited : Positivity, constraints,” IEEE Trans. Inf. Theory, vol. 34, pp.
181–193, 1988.
[17] S. J. M. L. Tongxin Li, Bikash Kumar Dey and A. D. S. Rutgers, “Quadratically constrained channels with causal adversaries,” submitted, ISIT, 2018.
[18] M. Langberg, “Private codes or succinct random codes that are (almost) perfect,” in Proc. IEEE Symp. Found. Comp. Sci., Rome, Italy, 2004.
[19] K. Ball, “An elementary introduction to modern convex geometry,” in Flavors of geometry, vol. 31, 1997, pp. 1–58.
[20] G. L. Stéphane Boucheron and P. Massart, Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013.
[21] M. Langberg, “Oblivious channels,” in Proc. IEEE Int. Symp. Information Theory, 2006.
[22] J. H. Conway and N. J. A. Sloane, Sphere packings, lattices and groups. Springer Science & Business Media, 2013, vol. 290.
[23] T. Cover and J. Thomas, Elements of Information Theory. Wiley, New York, 1991.

