# Low-bandwidth recovery of linear functions of Reed-Solomon-encoded data

Noah Shutty and Mary Wootters Stanford University. Email<EMAIL_ADDRESS>N.S. was supported in part by NSF DGE-1656518.Stanford University. Email:
<EMAIL_ADDRESS>Research partially supported by NSF Grants CCF-1844628
and CCF-BSF-1814629, and by a Sloan Research Fellowship.

###### Abstract

We study the problem of efficiently computing on encoded data. More
specifically, we study the question of low-bandwidth computation of functions
$F:{\mathbb{F}}^{k}\to{\mathbb{F}}$ of some data
$\mathbf{x}\in{\mathbb{F}}^{k}$, given access to an encoding
$\mathbf{c}\in{\mathbb{F}}^{n}$ of $\mathbf{x}$ under an error correcting
code. In our model—relevant in distributed storage, distributed computation
and secret sharing—each symbol of $\mathbf{c}$ is held by a different party,
and we aim to minimize the total amount of information downloaded from each
party in order to compute $F(\mathbf{x})$. Special cases of this problem have
arisen in several domains, and we believe that it is fruitful to study this
problem in generality.

Our main result is a low-bandwidth scheme to compute linear functions for
Reed-Solomon codes, even in the presence of erasures. More precisely, let
$\varepsilon>0$ and let $\mathcal{C}:{\mathbb{F}}^{k}\to{\mathbb{F}}^{n}$ be a
full-length Reed-Solomon code of rate $1-\varepsilon$ over a field
${\mathbb{F}}$ with constant characteristic. For any
$\gamma\in[0,\varepsilon)$, our scheme can compute any linear function
$F(\mathbf{x})$ given access to any $(1-\gamma)$-fraction of the symbols of
$\mathcal{C}(\mathbf{x})$, with download bandwidth $O(n/(\varepsilon-\gamma))$
bits. In contrast, the naive scheme that involves reconstructing the data
$\mathbf{x}$ and then computing $F(\mathbf{x})$ uses $\Theta(n\log n)$ bits.
Our scheme has applications in distributed storage, coded computation, and
homomorphic secret sharing.

##  1 Introduction

Suppose that we would like to store some data $\mathbf{x}\in{\mathbb{F}}^{k}$
on a distributed storage system consisting of $n$ nodes, where $n\geq k$.
(Here and for the rest of the paper, ${\mathbb{F}}$ denotes some finite
field). Since node failure is a possibility, we may protect the data with an
_error correcting code_ $\mathcal{C}:{\mathbb{F}}^{k}\to{\mathbb{F}}^{n}$ as
follows. We encode $\mathbf{x}$ as a _codeword_
$\mathbf{c}=\mathcal{C}(\mathbf{x})\in{\mathbb{F}}^{n}$, and for
$i=1,\ldots,n$, we send the symbol $c_{i}$ to the $i$’th storage node. If
$\mathcal{C}$ is a _Maximum Distance Separable_ (MDS) code—meaning that any
$k$ symbols of the codeword $\mathbf{c}$ are sufficient to recover the
original data $\mathbf{x}$—then the system can tolerate $n-k$ node failures
without losing any of the original data. Encoding with an MDS code (such as a
Reed-Solomon code, see Definition 2 below) is common in distributed storage:
for example, Reed-Solomon codes are built into HDFS [HDFS] and Ceph [CEPH].

Given data $\mathbf{x}\in{\mathbb{F}}^{k}$ encoded and stored with an MDS code
as described above, suppose that we would like to compute a function
$F(\mathbf{x})$ of the data, where $F:{\mathbb{F}}^{k}\to{\mathbb{F}}$. One
scheme (which we will refer to as the naive scheme) is to contact any $k$ of
the nodes, download their data, recover $\mathbf{x}$, and compute
$F(\mathbf{x})$. This requires downloading $k$ field symbols, or
$k\log|{\mathbb{F}}|$ bits. We call the amount of downloaded information the
bandwidth of the scheme. Given that $F(\mathbf{x})$ is only one field symbol,
or $\log|{\mathbb{F}}|$ bits, the naive scheme seems wasteful in terms of
bandwidth.

Our motivating question is whether we can compute $F(\mathbf{x})$ with less
bandwidth. That is, _when is it possible to do communication-efficient
computation on top of encoded data?_

In this paper, we introduce a new notion, _low-bandwidth function evaluation_
, in order to make this question precise. Our main result is a low-bandwidth
function evaluation scheme for the ubiquitous family of _Reed-Solomon Codes_ ,
and for the useful family of _linear functions_
$F:{\mathbb{F}}^{k}\to{\mathbb{F}}.$

###  1.1 Low-Bandwidth Function Evaluation

A low-bandwidth evaluation scheme for a code $\mathcal{C}$ and a collection of
functions $\mathcal{F}$ allows us to compute functions in $\mathcal{F}$ in a
communication-efficient way on data encoded with $\mathcal{C}$, even when a
set $\mathcal{I}\subset[n]$ of symbols are unavailable (e.g., the
corresponding nodes have failed). More precisely, we have the following
definition. Below, and throughout the paper, we use bold letters like
$\mathbf{c}$ to denote vectors, and we use $c_{i}$ to denote the $i$’th entry
of $\mathbf{c}$.

######  Definition 1 (Low-Bandwidth Function Evaluation).

Let $\mathcal{C}:{\mathbb{F}}^{k}\to{\mathbb{F}}^{n}$ be a code. Let
$\mathcal{F}$ be a class of functions $F:{\mathbb{F}}^{k}\to{\mathbb{F}}$. Let
$b\geq 0$. We say that there is an _evaluation scheme for $\mathcal{F}$ and
$\mathcal{C}$ with bandwidth $b$_ if for any $F\in\mathcal{F}$, there are:

  * •

positive integers $b_{1},\ldots,b_{n}\in{\mathbb{Z}}^{\geq 0}$ so that
$\sum_{j}b_{j}\leq b$;

  * •

functions $g_{1},\ldots,g_{n}$ so that
$g_{j}:{\mathbb{F}}\to\\{0,1\\}^{b_{j}}$;

  * •

and a function $G:\\{0,1\\}^{\sum_{j}b_{j}}\to{\mathbb{F}}$

so that for all $\mathbf{x}\in{\mathbb{F}}^{k}$, if
$\mathbf{c}=\mathcal{C}(\mathbf{x})$, then

$G(g_{1}(c_{1}),g_{2}(c_{2}),\ldots,g_{n}(c_{n}))=F(\mathbf{x}).$

We denote the scheme by $\Phi:F\mapsto(g_{1},g_{2},\ldots,g_{n},G)$ that maps
$F\in\mathcal{F}$ to the maps $g_{j}$ and $G$.

If there is a set $\mathcal{I}\subset[n]$ so that $b_{j}=0$ for all
$F\in\mathcal{F}$ and for all $j\in\mathcal{I}$, we say that $\Phi$ _tolerates
failures in $\mathcal{I}$_.

######  Remark 1 (More general alphabets).

More generally, one could define an evaluation scheme for codes
$\mathcal{C}:\Sigma_{0}^{k}\to\Sigma_{1}^{n}$ for arbitrary input/output
alphabets. In this paper, we focus on linear functions and MDS codes, so we
state Definition 1 with $\Sigma_{0}=\Sigma_{1}={\mathbb{F}}$ being some finite
field.

######  Remark 2 (Knowledge of $\mathcal{I}$).

We note that in Definition 1, the set of failed nodes $\mathcal{I}$ tolerated
by a scheme is a property of that particular scheme; a stronger definition
might demand that the same scheme tolerates _any_ set of failed nodes of a
particular size. In the distributed storage example above, this weaker
definition means that the nodes may need to know which nodes have failed in
order to decide which scheme to use. This mirrors the set-up in regenerating
codes, discussed below, where the identity of the (single) failed node is
assumed to be known.

Notions related to Definition 1 have been studied before, for particular
families of functions and/or particular codes. We mention a few of these
below, and discuss them more in Section 1.3 (Applications of our results) and
Section 1.4 (Related work).

  * •

Regenerating codes. In the model of distributed storage described above, there
has been a great deal of work on regenerating codes, which aim to repair one
node failure with low download bandwidth (see, e.g., [DRWS11]). This is a
special case of Definition 1 when $\mathcal{F}$ is the family of functions
$f_{i}(\mathbf{x})=\mathcal{C}(\mathbf{x})_{i}$, for $i=1,\ldots,n$, and where
$\mathcal{I}=\\{i\\}$. We note that if the code is systematic, this allows us
to recover the dictator functions $f_{i}(\mathbf{x})=x_{i}$.

  * •

Gradient Coding. The goal of gradient coding is to speed up distributed
gradient descent in the presence of stragglers, that is, compute nodes that
may be slow or unresponsive [TLDK17]. In this model, the data is
$\mathbf{X}=(\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(k)})$ where each
$\mathbf{x}^{(i)}\in{\mathbb{R}}^{d}$ for some $d$. The data $\mathbf{X}$ is
distributed using a code among $n$ workers, so that worker $i$ receives
$\mathbf{c}^{(i)}\in{\mathbb{R}}^{d^{\prime}}$, for a codeword
$\mathbf{C}=(\mathbf{c}^{(1)},\ldots,\mathbf{c}^{(n)})$. At each timestep the
parameter server (PS) has an iterate $\bm{\theta}\in{\mathbb{R}}^{d}$, which
it broadcasts to the workers. Each worker $i$ that has not failed computes a
local function $g_{i}(\mathbf{c}^{(i)})$ and returns it to the PS. The PS then
uses these messages to recover the gradient of some loss function,
$\nabla\mathcal{L}(\mathbf{X};\bm{\theta})$. One goal of gradient coding is to
tolerate stragglers in any set $\mathcal{I}$ of some fixed size, while
minimizing the communication bandwidth from the workers to the PS (e.g.,
[YA18]). This can be cast as a special case of a strengthing of Definition 1
(with different input/output alphabets as per Remark 1 and which can tolerate
any small set $\mathcal{I}$ of failed nodes as per Remark 2), where
$\mathcal{F}$ is the family of functions given by possible gradients:
$\mathcal{F}=\left\\{F_{\bm{\theta}}\,:\,\bm{\theta}\in{\mathbb{R}}^{d}\right\\}$,
where $F_{\bm{\theta}}(\mathbf{X})=\nabla\mathcal{L}(\mathbf{X};\bm{\theta})$.

  * •

Homomorphic Secret Sharing. In _secret sharing_ , a secret $s$ is shared among
$n$ parties, so that some coalitions of parties can recover the secret while
others learn nothing about it. A classic example is Shamir’s scheme, which is
essentially a Reed-Solomon (RS) code: let $\mathcal{C}$ be a RS code of
dimension $k$ and length $n+1$. To share a secret $s\in{\mathbb{F}}$, we pick
a random codeword $\mathbf{c}\in\mathcal{C}$ such that $c_{0}=s$, and we send
$c_{i}$ to party $i$. Any $k$ parties can recover $\mathbf{c}$ and hence $s$,
but any $k-1$ parties learn nothing about $s$. In single-client _Homomorphic
Secret Sharing_ (HSS) [BGI16, BCG+17, BGI+18], one additionally asks that the
parties be able to locally compute messages $g_{i}(c_{i})$ so that a referee
can compute a function $f(s)$ of the secret from these messages.111Typically,
$f(s)$ should be a sum of the messages, in which case the HSS scheme is called
additive. The HSS property has applications in Private Information Retrieval
and Secure Multiparty Computation (see, e.g., [BCG+17]). In some applications,
it is desirable that the messages $g_{i}(c_{i})$ be short, in which case the
HSS scheme is said to be compact. Low-bandwidth function evaluation is related
to (information-theoretic, not-necessarily-additive) compact HSS, in the sense
that a low-bandwidth function evaluation scheme for a Reed-Solomon code
$\mathcal{C}$ and with $\mathcal{F}=\\{F:\mathbf{x}\mapsto
f(\mathcal{C}(\mathbf{x})_{0})\\}$ gives a single-client HSS protocol for
Shamir’s scheme; the bandwidth of the scheme corresponds to the compactness of
the messages $g_{i}(c_{i})$. More generally, if $\mathcal{C}$ represents a
secret sharing scheme, then a low-bandwidth function evaluation scheme for
$\mathcal{C}$ yields a compact single-client HSS protocol for that scheme.

Given the numerous places that notions related to Definition 1 have appeared,
we believe it will be fruitful to study Definition 1 in generality. In this
paper we begin this general study by considering what is arguably most natural
class of functions (after the indicator functions
$f(\mathbf{x})=\mathcal{C}(\mathbf{x})_{i}$ studied in regenerating codes):
the class of linear functions. Our main results, described next in Section
1.2, are low-bandwidth evaluation schemes for Reed-Solomon codes, for classes
of linear functions. In Section 1.3, we mention several applications of our
results.

###  1.2 Our Results

Our main results hold for Reed-Solomon codes, defined below.

######  Definition 2 (Reed-Solomon Code).

Let $\mathbb{F}$ be a finite field and suppose $n\leq|{\mathbb{F}}|$. Let
$\alpha_{1},\alpha_{2},\ldots,\alpha_{n}\in\mathbb{F}$ be distinct evaluation
points. The Reed-Solomon Code (RS) of dimension $k$ and length $n$ with
evaluation points $\alpha_{1},\ldots,\alpha_{n}$ is the map
$\mathcal{C}:{\mathbb{F}}^{k}\to{\mathbb{F}}^{n}$ given by

$\mathcal{C}(\mathbf{f})=(f(\alpha_{1}),\ldots,f(\alpha_{n})),$

where for $\mathbf{f}\in{\mathbb{F}}^{k}$, we define
$f(X)=\sum_{i=0}^{k-1}f_{i}X^{i}$.

Our contributions are as follows.

  1. 1.

A framework for computing linear functions on RS-encoded data. We provide a
framework for developing low-bandwidth evaluation schemes for RS codes and for
families $\mathcal{F}$ of linear functions over extension fields. This begins
with a general linear-algebraic charactization (similar to the
characterization of [GW17] for regenerating codes) that applies to any linear
code. However, we go beyond that, building on it to develop a framework for RS
codes in particular. The linear-algebraic characterization for any linear code
is given in Section 3, and the framework for RS codes is given in Section 4.

  2. 2.

Low-bandwidth schemes for computing any linear function on RS-encoded data, up
to the Singleton bound. Our main theorem, Theorem 13, can be
summarized/simplified as follows:

######  Theorem 3 (Simplified; see Theorem 13).

Let $\varepsilon>\gamma>0$. There is some
$q_{0}=\Theta\left(\frac{1}{\varepsilon-\gamma}\right)$ so that the following
holds for sufficiently large $n$ and for any prime power $q\geq q_{0}$.

Let $Q=q^{t}$ for any $t\geq 2$. Let $n=Q$ and let $k=(1-\varepsilon)n$. Let
$\mathcal{C}$ be the RS code over ${\mathbb{F}}={\mathbb{F}}_{Q}$ of dimension
$k$ and length $n$, with evaluation points all of ${\mathbb{F}}$. Let
$\mathcal{F}$ be the set of all linear functions
$F:{\mathbb{F}}^{k}\to{\mathbb{F}}$. Let $\mathcal{I}\subseteq[n]$ be any set
with $|\mathcal{I}|<\gamma n$. Then there is an evaluation scheme for
$\mathcal{C}$ and $\mathcal{F}$ that tolerates failures in $\mathcal{I}$, with
bandwidth (measured in bits) of

$b=O\left(\frac{n\log(q)}{\varepsilon-\gamma}\right).$

We make a few remarks about Theorem 3:

     * •

The naive scheme (downloading enough information to recover $\mathbf{x}$, and
then computing $F(\mathbf{x})$) requires

$k\log(Q)=\frac{n\log n}{1-\varepsilon}$

bits of bandwidth. Thus, when $\varepsilon,\gamma,q$ are constant, our scheme
gives an asymptotic improvement of a factor of $\log n$ over the naive scheme.
(Notice that $|\mathbb{F}|=Q=q^{t}$, so we may choose $q$ to be constant and
allow $n=Q$ to grow by growing $t$).

     * •

Our scheme can tolerate a $\gamma$ fraction of failures, where $\gamma$ can be
arbitrarily close to $\varepsilon$. Since the rate of the code is
$1-\varepsilon$, by the Singleton bound the relative distance can be at most
$\varepsilon$, and so this is optimal.

     * •

One may wonder about lower bounds on the bandwidth. In Appendix A (Observation
18), we show that $b\geq n\log_{q}\left(\frac{n}{n-k+1}\right)\approx
n\log_{q}(1/\varepsilon)$ is necessary for Reed-Solomon codes, and that a
similar result (Corollary 20) holds for any MDS code. This shows that the
linear dependence on $n$ in Theorem 3 is optimal for constant $\varepsilon$
and $q$, although we leave it as an open question to pin down the correct
dependence on $\varepsilon$ and $\gamma$.

We also give a simpler version of Theorem 13, Theorem 12, which does not
tolerate any failures and which only works up the rate $1/2$. Our main reason
for presenting Theorem 12 is for exposition, as the proof is simpler, but we
are also able to get more precise constants. In particular, we show that RS
codes of rate approaching $1/2$ (for sufficiently large $q$, where $Q=q^{t}$
is the size of ${\mathbb{F}}$) can compute any linear function with bandwidth
at most $n\lceil\log q\rceil$. When $q=2$, we get an RS code of rate $1/4$
with bandwidth $n$ bits, or _only one bit_ from each node.

  3. 3.

Applications in distributed storage, coded computation, and homomorphic secret
sharing. Our results have applications in several domains. We elaborate on
these next in Section 1.3.

###  1.3 Applications

As noted above, low-bandwidth function evaluation shows up in several
settings, and our work has natural applications in these areas. We briefly
mention a few potential applications of Theorem 3 to further motivate our
results. First, we make two remarks about the generality of our scheme.

######  Remark 3 (Non-linear functions).

Our framework can also be used to efficiently compute certain non-linear
functions, for example $\mathbf{x}\mapsto\sum_{i=1}^{k}x_{i}^{2}$. To see
this, we first suppose without loss of generality that the Reed-Solomon code
has a systematic encoding, so that $\mathbf{x}$ is encoded as
$(f(\alpha_{1}),\ldots,f(\alpha_{n}))$ where $f\in{\mathbb{F}}[X]$ is the
unique polynomial of degree at most $k-1$ so that $f(\alpha_{i})=x_{i}$ for
$i=1,\ldots,k$. Then define $g(X)=f(X)^{2}$ and observe that each node
$i=1,\ldots,n$ can locally compute $g(\alpha_{i})$. Thus, we can apply our
scheme to the Reed-Solomon code of dimension $2k-1$ to recover the linear
combination $\sum_{i=1}^{k}g(\alpha_{i})=\sum_{i=1}^{k}x_{i}^{2}$.

######  Remark 4 (Prime fields).

Our approach requires that ${\mathbb{F}}$ be an extension field over a base
field ${\mathbb{B}}$. However, in many applications (including those discussed
below), it is desirable to work over a prime field. The reason is that often
we actually want to work over the reals or the integers, and these can be
nicely embedded in $\mathbb{F}_{p}$ for a large enough prime $p$. Fortunately,
for certain linear functions $F$, our approach can still be used to save
bandwidth when we wish to amortize several computations over prime fields.

In more detail, suppose that ${\mathbb{B}}={\mathbb{F}}_{p}$ for a large prime
$p$, and let ${\mathbb{F}}={\mathbb{F}}_{p^{t}}$. Let
$\zeta_{1},\ldots,\zeta_{t}$ be a basis for ${\mathbb{F}}$ over
${\mathbb{B}}$. Suppose that the linear function we want to compute is
$F(\mathbf{x})=\mathbf{b}^{T}\mathbf{x}$, where
$\mathbf{b}\in{\mathbb{B}}^{k}$ has coefficients in the base field
${\mathbb{B}}$. This is the case, for example, in Remark 3 when we want to
compute the $\ell_{2}$ norm: all of the coefficients are $1$. It is also the
case when the data $\mathbf{x}$ represents a histogram and we’d like to take
the sum of certain buckets: all of the coefficients are $0$ or $1$. If
$\mathbf{b}\in{\mathbb{B}}^{k}$, then we can proceed as follows. View the data
$\mathbf{x}\in{\mathbb{F}}^{k}$ as $t$ data points in ${\mathbb{B}}^{k}$. That
is, we write $x_{j}=\sum_{i=1}^{t}y_{i,j}\zeta_{i}$, and interpret
$\mathbf{x}$ as $t$ vectors
$\mathbf{y}^{(i)}=(y_{i,1},y_{i,2},\ldots,y_{i,k})$. If we use our scheme to
compute $F(\mathbf{x})$, then we have computed

$F(\mathbf{x})=\sum_{j=1}^{k}b_{j}x_{j}=\sum_{j=1}^{k}b_{j}\left(\sum_{i=1}^{t}\zeta_{i}y_{i,j}\right)=\sum_{i=1}^{t}\zeta_{i}\mathbf{b}^{T}\mathbf{y}^{(i)}=\sum_{i=1}^{t}\zeta_{i}F(\mathbf{y}^{(i)}).$

Since $F(\mathbf{y}^{(i)})\in{\mathbb{B}}$, and since the $\zeta_{i}$ form a
basis for ${\mathbb{F}}$ over ${\mathbb{B}}$, we can now read off the values
$F(\mathbf{y}^{(i)})$. This allows us to compute $t$ evaluations of $F$ on
vectors $\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(t)}\in{\mathbb{B}}^{k}$, using
bandwidth $O(n\log p)$ (assuming that the rate $1-\varepsilon$ of the code and
fraction $\gamma<\varepsilon$ of failed nodes are constants). In contrast, the
naive computation would require $O(tn\log p)$ bits. So for such linear
functions $F$, our scheme can do $t=\log_{p}n$ computations for the bandwidth
cost of a single computation in the naive scheme.

#### Distributed Storage.

The application to distributed storage was described in Section 1. In this
context, Theorem 3 gives a method to compute any linear function of data
stored on a distributed storage system with non-trivial download bandwidth.
The reader may be wondering about the upload bandwidth: don’t we need to
communicate the function $F$ to each node? The reason that we focus on the
download bandwidth (as is also the case for regenerating codes) is because of
the way that files are stored in a typical distributed storage system. In more
detail, a large file $\mathbf{x}$ will be broken up into blocks
$\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(M)}\in{\mathbb{F}}^{k}$, where $M$ is
very large, and each $\mathbf{x}^{(i)}$ will be encoded as $\mathbf{c}^{(i)}$,
so that the $j$’th node stores $\\{c^{(i)}_{j}\,:\,j\in[M]\\}$. With this set-
up, the evaluation scheme of Theorem 3 would be run independently on each of
the blocks, so that the upload cost is just the cost of broadcasting $F$,
while the download cost is $M$ times the bandwidth guaranteed in the theorem.
Since $M$ is large, the download cost dominates the upload cost, and Theorem 3
yields real bandwidth savings over the naive scheme.

#### Coded Computation and Low-Bandwidth Matrix-Vector Multiplication.

Suppose we would like to distribute some data $\mathbf{X}$ among $n$ worker
nodes and perform a computation $f(\mathbf{X})$ in a distributed way. A body
of work [LLP+17, DCG19, YLR+19] on coded computation has proposed introducing
redundancy in the data assignment, with the goal of tolerating stragglers
(worker nodes that may be slow or non-responsive): that is, we would like
responses from any $\tilde{k}$ out of $n$ workers to determine
$f(\mathbf{X})$. There are two lines of work in coded computation. One line of
work adds redundancy by replicating and appropriately distributing data (for
example the work on gradient coding mentioned above [YA18], or a line of work
aimed at general MapReduce computations [LMAYA17]), and aims to minimize
download bandwidth. Unfortunately, because the coding is done by replication,
the rate of the resulting code is necessarily small. A second line of work
adds redundancy through true “coding” (eg, taking nontrivial linear
combinations). This allows for high-rate codes without much overhead in terms
of the total computational load, but instead of focusing on bandwidth, this
line of work has focused on minimizing the number $\tilde{k}$ of nodes that
need to respond. Several works in this second line have focused on linear
functions, like matrix-vector multiplication [LLP+17, DCG19] or Fourier
transforms [YMAA17a]; to the best of our knowledge, none of these have focused
on download bandwidth beyond minimizing the number $\tilde{k}$ of workers that
need to respond.

Our work provides a way to interpolate between these two lines of work. That
is, our work gives coded computation schemes for linear functions that both
can have low download bandwidth and that can use non-replication-based coding
to achieve a high rate. In particular, Theorem 3 shows that we can use a rate
$1-\varepsilon$ RS code, with bandwidth that scales like $n/\varepsilon$,
saving an $O(\log n)$ factor when $\varepsilon$ is constant. As per Remarks 3
and 4 above, this approach can be used effectively to compute, say, $\ell_{p}$
norms over the reals, even though our Theorem 3 is stated for linear functions
over extension fields.

We note that this is not directly comparable to prior work for coded
computation of linear functions (eg, [LLP+17, DCG19, YMAA17b]) for two
reasons. First, those works have focused on computations with a larger output
(eg, matrix-vector multiplication, where the output is a vector rather than a
scalar), while our approach is most effective when the desired output is a
scalar. Second, in much of the work on coded computation, the identities of
the stragglers are not known to the other worker nodes. In our approach, since
the scheme may depend on the set $\mathcal{I}$ of failed nodes, the parameter
server would have to broadcast this information, which may not be practical.
However, we note that the problem is still interesting even if there are no
stragglers, simply to reduce download bandwidth (as in [LMAYA17]); or when the
“stragglers” can be planned (for example to do load balancing between multiple
tasks).

#### Homomorphic Secret Sharing.

We have described the basic set-up for Homomorphic Secret Sharing (HSS) above.
Our scheme immediately gives a compact single-client HSS scheme for linear
functions, by sharing a secret $\mathbf{x}\in{\mathbb{F}}^{k}$ using a
generalization of Shamir’s scheme (as in [FY92]) as follows. Let
$\mathbf{x}\in{\mathbb{F}}^{k}$ be a secret. Let $\tilde{k}>k$, so that
$\tilde{k}+k<n$. We encode $\mathbf{x}$ with a systematic Reed-Solomon code,
so that $x_{i}=f(\beta_{i})$ for $i=1,\ldots,k$, where $f$ is a random
polynomial of degree at most $\tilde{k}-1$ so that this is true, and where
$\beta_{1},\ldots,\beta_{k}\in{\mathbb{F}}$ are fixed evaluation points. Then
we distribute shares $f(\alpha_{1}),\ldots,f(\alpha_{n})$ to the $n$ parties,
where $\alpha_{i}\in{\mathbb{F}}\setminus\\{\beta_{1},\ldots,\beta_{k}\\}$.
Now, any $\tilde{k}$ parties can recover the secret, while any $\tilde{k}-k$
learn nothing about it. Theorem 3 (treating the evaluation points
$\beta_{1},\ldots,\beta_{k}$ as the unavailable nodes in $\mathcal{I}$)
ensures that as long as $\varepsilon=1-\tilde{k}/n$ and $\gamma=k/n$ are
constants with $\gamma<\varepsilon$, then each party can compute a small local
share $g_{i}(f(\alpha_{i}))$, which can then be combined to recover a linear
function $F(\mathbf{x})$.

As noted in Remarks 3 and 4 above, this approach can also be used for
amortizing the computation of certain (possibly nonlinear) functions over
prime fields.

###  1.4 Related Work

First, we mention two works that are similar in flavor to ours in that the aim
is to compute functions on data encoded with an error correcting code,
although the models are quite different. The first of these is [CGdW13], which
studies the notion of _error-correcting data structures_. In that work, a
vector $\mathbf{x}$, thought of as a database, is encoded as a data structure
$\mathcal{C}(\mathbf{x})$; as in our work, the goal is to efficiently compute
some function (e.g., perform a membership query) on $\mathbf{x}$ given access
to $\mathcal{C}(\mathbf{x})$, possibly in the presence of noise. However, that
work differs from ours because (a) they consider query complexity (rather than
bandwidth) as the notion of efficiency; and (b) the noise they consider is
errors (rather than erasures). Thus, in some sense, the work [CGdW13]
generalizes locally decodable codes in the same direction that we generalize
regenerating codes. The second work that is similar in flavor is the recent
work [LBWZY21] on _function correcting codes_. In that work, a sender Alice
sends a message $\mathbf{x}$ over a noisy channel to a receiver Bob who is
only interested in some function $f(\mathbf{x})$. The main focus of that work
is on the trade-off between the amount of noise in the channel and the rate of
the code, given that Bob can recover $f(\mathbf{x})$. This differentiates
their problem from ours because they do not study any notion of efficiency
(like bandwidth or query complexity) on Bob’s end.

As mentioned above, notions related to Definition 1 arise in a variety of
contexts, including in regenerating codes, coded computation, and homomorphic
secret sharing. We survey related work in these areas below.

#### Regenerating codes.

The body of work most related to ours is that of regenerating codes.
Regenerating codes were introduced in [DGW+10] and have seen a huge amount of
work since then. The work most related to ours is the study of scalar222In the
regenerating codes literature, a scalar MDS code is one that is linear over
its alphabet, as opposed to a vector MDS code, which is linear over a smaller
field. MDS codes, including RS codes. This was initiated by [SPDC14], and
further developed in a line of work including [GW17, TYB18]. These works give
repair schemes for RS codes, which can be seen as evaluation schemes for RS
codes and for the class of functions
$\mathcal{F}=\left\\{F_{i}:\mathbf{x}\mapsto\mathcal{C}(x)_{i}\,:\,i\in[n]\right\\}$.
The work [GW17] gives a characterization of repair schemes for MDS codes. This
characterization inspires our Definition 4 and Proposition 5, which gives a
similar formulation for evaluation schemes for linear codes and classes of
linear functions. However, our framework for RS codes developed in Section 4
is quite different than the approach in [GW17]. In more detail, in [GW17], the
goal is to choose dual codewords $\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(t)}$,
so that they give rise to low-dimensional ${\mathbb{B}}$-subpsaces. In
contrast, our approach is to go the other way around: we first pick the low-
dimensional ${\mathbb{B}}$-subspaces, and show how they give rise to
appropriate dual codewords.

#### Coded computation.

As mentioned above, there are two main lines of work in coded computation. We
refer the reader to [LA20] for a survey. One line of work has focused on
coding for stragglers and has used “true” coding (in the sense that linear
combinations of the original data are stored, rather than repeated blocks). In
our framework, stragglers correspond to the set $\mathcal{I}$ of failures, the
code maps some data $\mathbf{x}$ to a codeword $\mathbf{c}$ that is
distributed to workers, and the goal is to compute some function
$F(\mathbf{x})$ from computations $g_{i}(c_{i})$ performed by the worker $i$
on their part of the encoded data $c_{i}$. (We note that typically in these
settings the symbols $x_{j}$ and $c_{i}$ are actually vector or matrix-valued,
and the code is applied to each coordinate in parallel). This line of work has
considered linear functions like matrix-vector multiplication [LLP+17, DCG19]
or Fourier transformations [YMAA17a], as well as non-linear functions like
matrix-matrix multiplication [YMAA17b] and computation of low-degree
polynomials [YLR+19]. The main focus has been on minimizing the number of
workers required to complete their task before the desired function can be
computed, as well as on analyzing when and how much this can speed up
computation given stochastic models of stragglers. However, to the best of our
knowledge, this line of work has not considered the network bandwidth, which
is what we consider here.

A second line of work has also focused on coding for stragglers, but has used
replication-based coding. That is, the data $\mathbf{x}$ is separated into
blocks, and these blocks are distributed to workers with repetition. For
example, worker $i$ might receive blocks 1 and 2, and worker $j$ might receive
blocks 2 and 3. This approach is especially common in the area of gradient
coding [TLDK17, HASH18, RTTD20], where the goal is to compute the function
$F_{\bm{\theta}}(\mathbf{x})=\nabla L(\mathbf{x};\bm{\theta})$ which is the
gradient of a loss function at a current iterate $\bm{\theta}$. In this set-
up, again the main goal is to minimize the number of nodes that need to
respond before the function can be computed, but some works like [YA18] have
also considered the download bandwidth. Thus, the goal of [YA18] is similar to
ours, but the approach differs because (a) they are using a replication-based
code, and in particular the rate must be low; but (b) their scheme does not
depend on the identity of the stragglers, which ours does. We note that there
are several relaxations of the gradient coding problem, for example when the
stragglers are random and/or the gradient only needs to be approximately
computed [CPE17, RTTD20, LKAS18]. Again, those works differ from ours because
of the replication-based coding and the different model of stragglers.

A final line of work, starting with [LMAYA17], has focused on minimizing
communication bandwidth, as we do here, but in a different setting. That work
considers computation in a general MapReduce framework. In that work, the data
is distributed before the Map phase, introducing redundancy via replication.
Then the data is shuffled before the Reduce phase; the goal is to reduce the
amount of communication in the shuffle. Finally, the Reduce phase occurs, and
each node needs to compute the function that they are responsible for. This
can be viewed as a decentralized version of our setting where each node wants
to compute a (different) function. Key differences between that work and ours
are that (a) the coding comes via replication, and (b) the goal is to be able
to support generic computation in the MapReduce framework, rather than
focusing on specific functions.

#### Homomorphic Secret Sharing.

Homomorphic Secret Sharing was introduced in [BGI16] and has been further
explored in [BGI+18] and the references therein. As noted above, a single-
client compact HSS scheme is related to our definition of low-bandwidth
function evaluation, where the code is given by the secret-sharing scheme. The
work [BGI16] gave a two-party HSS scheme for any deterministic branching
program that is cryptographically secure; this scheme has been optimized in
[BCG+17], and other works [BKS19, OSY21, RS21] have achieved similar results
under different cryptographic assumptions. The work [BGI+18] has studied the
problem more generally, including under information-theoretic security, and
provided lower bounds. While the setup of HSS is quite related to our work,
most existing work on HSS is in a very different parameter regime. For
example, the two-party case studied in [BGI16] corresponds to a code of length
$n=2$. Additionally, since an MDS code provides an information-theoretically
secure secret-sharing scheme, HSS is most related to our work under
information-theoretic security. However, most constructions that we are aware
of for HSS have focused on cryptographic security. One exception is the recent
work [FIKW21], which focuses on the download bandwidth of information-
theoretic HSS. However, that work focuses on _multi_ -client HSS, where the
$k$ secrets in $\mathbf{x}\in{\mathbb{F}}^{k}$ must be secret-shared
independently of each other; in contrast, the application of our work sketched
above is for _single_ -client HSS, where the $k$ secrets in $\mathbf{x}$ may
be shared jointly.

###  1.5 Organization

In Section 2 we set notation and give a brief overview of our approach. In
Section 3 we introduce our framework for linear functions and linear codes. In
Section 4 we introduce our framework for RS codes in particular. In Section 5,
we instantiate our framework to prove Theorem 13, the more detailed version of
Theorem 3 above. Section 6 concludes with some open questions.

##  2 Notation and Technical Overview

In this section we set some notation and give a quick technical overview of
the main ideas in our work.

###  2.1 Notation

Throughout, we use $[n]$ to denote the set $\\{1,2,\ldots,n\\}$. We use bold
lowercase letters like $\mathbf{x}$ to denote vectors, and bold uppercase
letters like $\mathbf{G}$ to denote matrices. For a vector $\mathbf{x}$, we
use $x_{i}$ to denote the $i$’th coordinate of $x$. We use
$\mathbf{x}|_{[i,j]}$ to denote the vector $(x_{i},x_{i+1},\ldots,x_{j})$. For
a polynomial $f(X)=\sum_{i}f_{i}X^{i}$, we define the degree set of $f$ to be

$\mathrm{degSet}(f(X))=\left\\{i\,:\,f_{i}\neq 0\right\\}.$

We always work over a field ${\mathbb{F}}={\mathbb{F}}_{Q}$, where $Q=q^{t}$
and we will let ${\mathbb{B}}={\mathbb{F}}_{q}$ be the subfield of
${\mathbb{F}}$ of size $q$. With $Q=q^{t}$ as above, we will make use of the
field trace of ${\mathbb{F}}_{Q}$ over ${\mathbb{F}}_{q}$, defined by

$\mathrm{tr}(X)=\sum_{i=0}^{t-1}X^{q^{i}}.$

We note the following two facts about the field trace:

  * •

The field trace is ${\mathbb{F}}_{q}$-linear and its image is contained in
${\mathbb{F}}_{q}$.

  * •

The field ${\mathbb{F}}={\mathbb{F}}_{Q}$ is a vector space over the subfield
${\mathbb{B}}={\mathbb{F}}_{q}$. Given a basis $\zeta_{1},\ldots,\zeta_{t}$
for ${\mathbb{F}}$ over ${\mathbb{B}}$, the traces
$\mathrm{tr}(\zeta_{1}\alpha),\ldots,\mathrm{tr}(\zeta_{t}\alpha)$ uniquely
specify $\alpha\in{\mathbb{F}}$.

We consider linear codes $\mathcal{C}:{\mathbb{F}}^{k}\to{\mathbb{F}}^{n}$.
Such a code can be represented by a full-rank generator matrix
$\mathbf{G}\in{\mathbb{F}}^{n\times k}$, so that
$\mathcal{C}(\mathbf{x})=\mathbf{G}\mathbf{x}$ for
$\mathbf{x}\in{\mathbb{F}}^{k}$.

We consider both ${\mathbb{F}}$-subspaces of ${\mathbb{F}}^{n}$ and
${\mathbb{B}}$-subspaces of ${\mathbb{F}}$ or ${\mathbb{F}}^{n}$. To that end,
we use $\operatorname{span}$, $\dim$, and $\cdot^{\perp}$ (with no decoration)
to refer to the span, dimension, and orthogonal complement over
${\mathbb{F}}$. We use $\operatorname{span}_{{\mathbb{B}}}$,
$\dim_{\mathbb{B}}$ and $\cdot^{\perp_{\mathbb{B}}}$ (decorated with a
“${\mathbb{B}}$”) to denote the span, dimension, and orthogonal complement
over ${\mathbb{B}}$. We define the orthogonal complement over ${\mathbb{B}}$
as follows. For a ${\mathbb{B}}$-vector space $V\subseteq{\mathbb{F}}$, we
define
$V^{\perp_{\mathbb{B}}}:=\left\\{x\in{\mathbb{F}}\,:\,\mathrm{tr}(xv)=0\forall
v\in V\right\\}$. For a ${\mathbb{B}}$-vector space
$\mathcal{V}\subset{\mathbb{F}}^{n}$, we define

$\mathcal{V}^{\perp_{\mathbb{B}}}:=\left\\{\mathbf{x}\in{\mathbb{F}}^{n}\,:\,\mathrm{tr}(\mathbf{x}^{T}\mathbf{v})=0\forall\mathbf{v}\in
V\right\\}.$

###  2.2 Technical Overview

Our approach begins with a general linear-algebraic framework, similar to that
from [GW17] for renegerating codes. Let ${\mathbb{B}}$ be a subfield of
${\mathbb{F}}$, and let $\zeta_{1},\ldots,\zeta_{t}$ be a basis for
${\mathbb{F}}$ over ${\mathbb{B}}$. For a code
$\mathcal{C}:{\mathbb{F}}^{k}\to{\mathbb{F}}^{n}$, let
$C=\mathcal{C}({\mathbb{F}}^{k})$, so $C$ is a subspace of dimension $k$ in
${\mathbb{F}}^{n}$ that consists of all codewords. We can associate an
evaluation scheme with a sequence of ${\mathbb{B}}$-subspaces
$V_{1},\ldots,V_{n}\subset{\mathbb{F}}$, by demanding that node $j$ return
enough information to evaluate $\mathrm{tr}(c_{j}\nu)$ for all $\nu\in V_{j}$.
Since $V_{j}$ is ${\mathbb{B}}$-linear, it suffices to send $b_{j}$ symbols
from ${\mathbb{B}}$, where $b_{j}=\dim_{\mathbb{B}}(V_{j})$. When is this
enough information to recover a linear function
$F_{\mathbf{p}}(\mathbf{x})=\mathbf{p}^{T}\mathbf{x}$?

In Definition 4, we define a linear evaluation scheme as a sequence of
${\mathbb{B}}$-subspaces $V_{1},\ldots,V_{n}\subset{\mathbb{F}}$ that has a
nice relationship to $\mathcal{C}$, and then we show that this nice
relationship allows us to recover linear functions
$F_{\mathbf{p}}(\mathbf{x})$. More precisely, let

$\mathcal{W}=V_{1}^{\perp_{\mathbb{B}}}\times\ldots,\times
V_{n}^{\perp_{\mathbb{B}}}.$

We show in Section 3 that if
$\operatorname{span}_{\mathbb{F}}\left(C\cap\mathcal{W}\right)$ has low
dimension over ${\mathbb{F}}$, then there are many linear functions
$F_{\mathbf{p}}$ that can be recovered by the scheme derived from the
subspaces $V_{1},\ldots,V_{n}$. Thus, the goal becomes to find
${\mathbb{B}}$-subspaces $V_{1},\ldots,V_{n}\subset{\mathbb{F}}$ so that
$\operatorname{span}_{\mathbb{F}}\left(C\cap\mathcal{W}\right)$ is low-
dimensional over ${\mathbb{F}}$. (Additionally, we need to keep track of which
linear functions we can recover, but we will gloss over that in this
overview). Notice that $\mathcal{W}$ is a ${\mathbb{B}}$-vector space, but not
an ${\mathbb{F}}$-vector space. Thus, it is not obvious how to get a handle on
the dimension of this span.

In order to control the dimension of
$\operatorname{span}_{\mathbb{F}}\left(C\cap\mathcal{W}\right)$, we specialize
to Reed-Solomon codes (rather than any linear code); this is where our
analysis departs in similarity from [GW17]. We do this in Sections 4 and 5.
Suppose that we choose
$V_{i}=\operatorname{span}_{\mathbb{B}}\left(v(\alpha_{i})\right)$, where
$v(X)\in{\mathbb{F}}[X]$ is some polynomial. Then our goal becomes to show
that

$\left\\{g\in{\mathbb{F}}[X]\,:\,\deg(g)<k,\mathrm{tr}(g(\alpha_{j})v(\alpha_{j}))=0\
\ \forall j\in[n]\right\\}$ (1)

lies in a low-dimensional ${\mathbb{F}}$-vector space. Again, this is tricky
because “$\mathrm{tr}(g(\alpha_{j})v(\alpha_{j}))=0$” is a
${\mathbb{B}}$-linear constraint, and we want ${\mathbb{F}}$-linear
constraints. We turn these ${\mathbb{B}}$-linear constraints into
${\mathbb{F}}$-linear constraints as follows. Consider the unique polynomial
$R(X)$ of degree at most $n-1$ so that

$R(X)\equiv\mathrm{tr}(g(X)v(X))\mod p_{A}(X),$

where $p_{A}(X)=\prod_{j=1}^{n}(X-\alpha_{j})$. Now, if
$\mathrm{tr}(g(\alpha_{j})v(\alpha_{j}))=0$ for all $j$, then $R$ vanishes
everywhere and is thus identically zero. The polynomial $R$ is a bit tricky to
write down, but if the evaluation points are all of ${\mathbb{F}}$, then
$p_{A}(X)=X^{Q}-X$, and in fact taking the residue of $R(X)$ modulo $p_{A}(X)$
is tractable. Thus, our strategy is to expand out $R(X)$ and choose the
coefficients of $v$ carefully so that the coefficient on some term $X^{d}$ is
of the form $\sum_{\ell}v_{d-\ell}g_{\ell}$. Since that coefficient must be
zero—because $R(X)$ is identically zero—this gives us an ${\mathbb{F}}$-linear
constraint on the polynomial $g$. If we get enough linearly independent
${\mathbb{F}}$-linear constraints this way, we can show that the space (1)
lies in a low-dimension ${\mathbb{F}}$-vector space, which in turn will show
that there are many $F_{\mathbf{p}}$ that can be recovered by the scheme
associated with $V_{i}=\operatorname{span}_{\mathbb{B}}(v(\alpha_{i}))$.
(Again, in this overview we gloss over the fact that we actually want to know
_which_ functions $F_{\mathbf{p}}$ can be recovered this way: by keeping track
of exactly which linear constraints we get, we are able to design the
polynomial $v(X)$ so that we can control this.)

The approach above is sufficient to design a scheme for codes of rate up to
$1/2$, that doesn’t tolerate any failures $\mathcal{I}$. As a warm-up, we
present this result as Theorem 12. In order to extend our result to get
Theorem 13, the more detailed version of Theorem 3 above, we must choose
several polynomials $v^{(1)},\ldots,v^{(s)}$, increasing the bandwidth by a
factor of $s$. There are two main ideas here. First, in order to make the rate
larger than $1/2$ in the scheme from Theorem 12, we must restrict not only the
coefficients of $v$ but also the coefficients of $g$. This results in a scheme
for a subset $\mathcal{F}^{\prime}$ of linear functions. By repeating this
several times, we are able to recover all of the linear functions. Second, in
order to handle failures in an arbitrary set $\mathcal{I}$, we choose the
polynomials $v^{(r)}(X)$ to additionally vanish on the set $\mathcal{I}$.
Indeed, since the subspace $V_{j}$ given by a polynomial $v(X)$ is
$V_{j}=\operatorname{span}_{\mathbb{B}}(v(\alpha_{j}))$, if $v$ vanishes on
$\mathcal{I}$ then $V_{j}=\\{0\\}$ for all $j\in\mathcal{I}$. Thus, the
dimension is zero, and the $j$’th node does not need to return any
information.

We give the framework for general linear codes, and explain why
$\operatorname{span}_{\mathbb{F}}\left(C\cap\mathcal{W}\right)$ is important,
in Section 3. We develop our “pick nice polynomials $v(X)$” framework in
Section 4. Finally, we instantiate our framework for a full-length RS code and
analyze it in Section 5.

##  3 Framework for linear functions and any linear code

For the rest of the paper, we focus on the special case where $\mathcal{C}$ is
a linear code, and where $\mathcal{F}$ is a set of linear functions. In this
case, evaluation schemes for $\mathcal{F}$ and $\mathcal{C}$ can arise from a
simple linear-algebraic condition, defined next.

######  Definition 4 (Linear Evaluation Schemes).

Let ${\mathbb{B}}$ be a subfield of ${\mathbb{F}}$, and let
$\zeta_{1},\ldots,\zeta_{t}\in{\mathbb{F}}$ be a basis for ${\mathbb{F}}$ over
${\mathbb{B}}$. Let $\mathcal{C}:{\mathbb{F}}^{k}\to{\mathbb{F}}^{n}$ be a
linear code, and let $\mathbf{G}\in{\mathbb{F}}^{n\times k}$ be a generator
matrix for $\mathcal{C}$. Let $\mathbf{p}\in{\mathbb{F}}^{k}$ and let
$\mathbf{w}\in{\mathbb{F}}^{n}$ be any vector so that
$\mathbf{p}=\mathbf{G}^{T}\mathbf{w}$. (Note that such a vector exists since
$\mathbf{G}$ has full column-rank).

Suppose that $V_{1},\ldots,V_{n}\subset{\mathbb{F}}$ are
${\mathbb{B}}$-subspaces, so that $\dim_{{\mathbb{B}}}(V_{j})=b_{j}$. Let
$\mathcal{V}=V_{1}\times\cdots\times V_{n}\subset{\mathbb{F}}^{n}$. We say
that $(V_{1},\ldots,V_{n})$ provide a _linear evaluation scheme for
$\mathbf{p}$ and $\mathcal{C}$_ (with respect to
$\\{\zeta_{1},\ldots,\zeta_{t}\\}$) if for all $i\in[t]$,

$\zeta_{i}\mathbf{w}\in\mathcal{C}({\mathbb{F}}^{k})^{\perp}+\mathcal{V}$

The _bandwidth_ of the scheme is
$\left(\sum_{j=1}^{n}b_{j}\right)\lceil\log|{\mathbb{B}}|\rceil$. Further, we
say that $(V_{1},\ldots,V_{n})$ _tolerates failures in $\mathcal{I}$_ where
$\mathcal{I}:=\left\\{j\in[n]\,:\,V_{j}=\\{0\\}\right\\}$.

For $\mathcal{P}\subseteq{\mathbb{F}}^{k}$, we say that a map
$\varphi:\mathcal{P}\to(2^{\mathbb{F}})^{n}$ provides a linear evaluation
scheme for $\mathcal{P}$ and $\mathcal{C}$ if
$\varphi(\mathbf{p})=(V_{1},\ldots,V_{n})$ provides a linear evaluation scheme
for $\mathbf{p}$ and $\mathcal{C}$ for all $\mathbf{p}\in\mathcal{P}$. For a
set $\mathcal{I}\subset[n]$, we say that $\varphi$ tolerates failures in
$\mathcal{I}$ if, for all $\mathbf{p}\in\mathcal{P}$, $\varphi(\mathbf{p})$
tolerates failures in $\mathcal{I}$.

The following proposition explains why a linear evaluation scheme $\varphi$
indeed gives us an evaluation scheme for a set of linear functions.

######  Proposition 5.

Suppose that $\varphi$ provides a linear evaluation scheme for $\mathcal{P}$
and $\mathcal{C}$, with bandwidth $b$. Then there is an evaluation scheme for
the class of functions

$\mathcal{F}=\\{F_{\mathbf{p}}:\mathbf{x}\mapsto\mathbf{x}^{T}\mathbf{p}\,:\,\mathbf{p}\in\mathcal{P}\\}$

and $\mathcal{C}$ with bandwidth $b$. Moreover, for $\mathcal{I}\subset[n]$,
this evaluation scheme tolerates failures in $\mathcal{I}$ if $\varphi$ does.

###### Proof.

Suppose that $\varphi$ forms a linear evaluation scheme for $\mathcal{P}$ and
$\mathcal{C}$. Let $\mathbf{p}\in\mathcal{P}$, and let
$\mathbf{w}\in{\mathbb{F}}^{n}$ be as in the theorem statement. Let
$(V_{1},\ldots,V_{n})=\varphi(\mathbf{p})$ be the linear evaluation scheme for
$\mathbf{p}$. For each $j\in[n]$, let
$\beta^{(j)}_{1},\ldots,\beta^{(j)}_{b_{j}}\in V_{j}$ be a basis for $V_{j}$
over ${\mathbb{B}}$. We will construct functions $g_{1},\ldots,g_{n}$ and $G$
as in Definition 1 that will allow us to reconstruct
$F(\mathbf{x})=\mathbf{p}^{T}\mathbf{x}$.

Fix $\mathbf{x}\in{\mathbb{F}}^{k}$ and let
$\mathbf{c}=\mathbf{G}\mathbf{x}\in\mathcal{C}({\mathbb{F}}^{k})$ be the
corresponding codeword. First, we observe that

$\mathbf{c}^{T}\mathbf{w}=\mathbf{x}^{T}\mathbf{G}^{T}\mathbf{w}=\mathbf{x}^{T}\mathbf{p}=F(\mathbf{x}).$

Thus, we focus on recovering $\mathbf{c}^{T}\mathbf{w}$.

We define the functions $g_{j}:{\mathbb{F}}\to{\mathbb{B}}^{b_{j}}$ by

$g_{j}(x):=(\mathrm{tr}(c_{j}\beta_{1}^{(j)}),\mathrm{tr}(c_{j},\beta_{2}^{(j)}),\ldots,\mathrm{tr}(c_{j},\beta^{(j)}_{b_{j}})).$

Now by the definition of a linear evaluation scheme, for all $i$,
$\zeta_{i}\mathbf{w}\in\mathcal{C}({\mathbb{F}}^{k})^{\perp}+\mathcal{V}$.
This implies that there are dual codewords
$\mathbf{z}^{(1)},\ldots,\mathbf{z}^{(t)}\in\mathcal{C}({\mathbb{F}}^{k})^{\perp}$
so that for all $j\in[n]$ and all $i\in[t]$,

$\zeta_{i}w_{j}-z_{j}^{(i)}\in V_{j}.$

In order to define the repair function $G$, we observe that for all $i\in[t]$,
we have

$\zeta_{i}\sum_{j}w_{j}c_{j}=\sum_{j}c_{j}(\zeta_{i}w_{j}-z_{j}^{(i)}).$

This is because $\sum_{j}c_{j}z_{j}^{(i)}=0$, since
$\mathbf{z}^{(i)}\in\mathcal{C}({\mathbb{F}}^{k})^{\perp}$ and
$\mathbf{c}\in\mathcal{C}({\mathbb{F}}^{k})$. In particular, this implies that
for all $i\in[t]$,

$\mathrm{tr}\left(\zeta_{i}\sum_{j}w_{j}c_{j}\right)=\sum_{j}\mathrm{tr}(c_{j}(\zeta_{i}w_{j}-z_{j}^{(i)})).$
(2)

Since $\zeta_{i}w_{j}-z_{j}^{(i)}\in V_{j}$ for all $j\in[n],i\in[t]$, we can
write

$\zeta_{i}w_{j}-z_{j}^{(i)}=\sum_{\ell=1}^{b_{j}}a^{(i,j)}_{\ell}\beta^{(i)}_{\ell}$

for some coefficients $a^{(i,j)}_{\ell}\in{\mathbb{B}}$. Thus,

$\mathrm{tr}(c_{j}(\zeta_{i}w_{j}-z_{j}^{(i)}))=\sum_{\ell=1}^{b_{j}}a^{(i,j)}_{\ell}\mathrm{tr}(c_{j}\beta^{(i)}_{\ell}),$
(3)

where above we have used the linearity of the trace. Now, we can define the
function $G$ to be the output of the following algorithm:

  * •

Input:
$g_{j}(c_{j})=(\mathrm{tr}(c_{j}\beta_{1}^{(j)}),\mathrm{tr}(c_{j},\beta_{2}^{(j)}),\ldots,\mathrm{tr}(c_{j},\beta^{(j)}_{b_{j}}))$
for all $j$.

  * •

For each $i\in[t],j\in[n]$, use (3) to recover
$\mathrm{tr}(c_{j}(\zeta_{i}w_{j}-z_{j}^{(i)}))$ from the input.

  * •

Use (2) to recover $\mathrm{tr}\left(\zeta_{i}\sum_{j}w_{j}c_{j}\right)$ for
all $i\in[t]$.

  * •

Since $\zeta_{1},\ldots,\zeta_{t}$ form a basis for ${\mathbb{F}}$ over
${\mathbb{B}}$, this is sufficient to recover
$\sum_{j}w_{j}c_{j}=F(\mathbf{x})$. Return $F(\mathbf{x})$.

Thus, we have a function evaluation protocol for $\mathcal{C}$. To finish the
proof, we observe that the amount of information sent is $\sum_{j=1}^{n}b_{j}$
symbols from ${\mathbb{B}}$, so the total bandwidth is
$\left(\sum_{j=1}^{n}b_{j}\right)\lceil\log|{\mathbb{B}}|\rceil$ bits.

Finally, observe that if $V_{j}=\\{0\\}$, then $b_{j}=0$ and the scheme above
does not need to contact symbol $i$, so this scheme tolerates failures in
$\mathcal{I}$. ∎

In the next lemma, we reformulate the condition in Definition 4 in a way that
will be helpful going forward.

######  Lemma 6.

Let $\mathcal{V}=V_{1}\times V_{2}\times\cdots\times
V_{n}\subset{\mathbb{F}}^{n}$, where each $V_{i}$ is a ${\mathbb{B}}$-subspace
of ${\mathbb{F}}$. Let $\mathcal{W}=W_{1}\times W_{2}\times\cdots\times
W_{n}\subset{\mathbb{F}}^{n}$, where $W_{i}=V_{i}^{\perp_{{\mathbb{B}}}}$. Let
$\mathcal{C}:{\mathbb{F}}^{k}\to{\mathbb{F}}^{n}$ be a linear code. Let
$\zeta_{1},\ldots,\zeta_{t}$ be a basis for ${\mathbb{F}}$ over
${\mathbb{B}}$. Then for any $\mathbf{w}\in{\mathbb{F}}^{n}$,

$\zeta_{i}\mathbf{w}\in\mathcal{C}({\mathbb{F}}^{k})^{\perp}+\mathcal{V}\ \ \
\forall i\in[t]$

if and only if

$\mathbf{w}\in\left(\operatorname{span}_{{\mathbb{F}}}(\mathcal{C}({\mathbb{F}}^{k})\cap\mathcal{W})\right)^{\perp}.$

###### Proof.

Let $C=\mathcal{C}({\mathbb{F}}^{k})\subset{\mathbb{F}}^{n}$. We have

$\displaystyle\mathbf{w}\in\left(\operatorname{span}_{{\mathbb{F}}}(C\cap\mathcal{W})\right)^{\perp}$
$\displaystyle\Leftrightarrow\forall\mathbf{y}\in
C\cap\mathcal{W},\mathbf{w}^{T}\mathbf{y}=0$
$\displaystyle\Leftrightarrow\forall\mathbf{y}\in C\cap\mathcal{W},\forall
i\in[t],\mathrm{tr}((\zeta_{i}\mathbf{w})^{T}\mathbf{y})=0$
$\displaystyle\Leftrightarrow\forall
i\in[t],\zeta_{i}\mathbf{w}\in(C\cap\mathcal{W})^{\perp_{\mathbb{B}}}$
$\displaystyle\Leftrightarrow\forall i\in[t],\zeta_{i}\mathbf{w}\in
C^{\perp_{\mathbb{B}}}+\mathcal{W}^{\perp_{\mathbb{B}}},$ (4)

using the fact that for any vector spaces $A,B$, we have $(A\cap
B)^{\perp}=A^{\perp}+B^{\perp}$. Now, we observe that
$C^{\perp_{\mathbb{B}}}=C^{\perp}$. Indeed,

$\displaystyle C^{\perp_{\mathbb{B}}}$
$\displaystyle=\left\\{\mathbf{x}\,:\,\mathrm{tr}(\mathbf{c}^{T}\mathbf{x})=0\forall\mathbf{c}\in
C\right\\}$
$\displaystyle=\left\\{\mathbf{x}\,:\,\mathrm{tr}(\zeta_{i}\mathbf{c}^{T}\mathbf{x})=0\forall\mathbf{c}\in
C,\forall i\in[t]\right\\}$
$\displaystyle=\left\\{\mathbf{x}\,:\,\mathbf{c}^{T}\mathbf{x}=0\forall\mathbf{c}\in
C\right\\}=C^{\perp}.$

Above, we used the fact that since $\mathcal{C}$ is linear, $C=\zeta_{i}C$ for
all $i$. Further, we observe that
$\mathcal{W}^{\perp_{\mathbb{B}}}=\mathcal{V}$ by defintion. Thus, from (4),
we conclude that

$\mathbf{w}\in\left(\operatorname{span}_{{\mathbb{F}}}(C\cap\mathcal{W})\right)^{\perp}\Leftrightarrow\forall
i\in[t],\zeta_{i}\mathbf{w}\in C^{\perp}+\mathcal{V},$

which is what we wanted to show. ∎

##  4 Framework for linear functions and RS codes

The framework in Section 3 was valid for any linear code $\mathcal{C}$. Now,
we specialize to Reed-Solomon codes in order to leverage this
characterization. We begin with a few definitions that will be useful for our
framework.

######  Definition 7.

Let $A=(\alpha_{1},\ldots,\alpha_{n})$, so that $\alpha_{i}\in{\mathbb{F}}$
are distinct. Define

$p_{A}(X)=\prod_{j=1}^{n}(X-\alpha_{j}).$

For a non-negative integer $j$ and for $i\in\\{0,1,\ldots,t-1\\}$, define
$\sigma_{i}(j)\subset\mathbb{Z}$ to be

$\sigma_{i}(j)=\mathrm{degSet}\left(\overline{X^{jq^{i}}}\right),$

where $\overline{X^{jq^{i}}}$ is the unique polynomial of degree at most $n-1$
so that

$\overline{X^{jq^{i}}}\equiv X^{jq^{i}}\mod p_{A}(X).$

We note that $\sigma_{i}$ depends on the choice of $A$, but we suppress this
dependence in the notation for readability.

######  Remark 5.

For any $j<n$, we have
$\sigma_{0}(j)=\mathrm{degSet}\left(\overline{X^{j}}\right)=\mathrm{degSet}\left(X^{j}\right)=\left\\{j\right\\}$.

######  Remark 6.

While for general $A$, $\sigma_{i}$ may be quite complicated, for some sets
$A$ it is relatively simple. For example, if $A={\mathbb{F}}$, then
$p_{A}(X)=X^{Q}-X$, and

$\sigma_{i}(j)=\\{jq^{i}\ \ \mathrm{mod}^{*}\ Q-1\\},$

where

$x\ \ \mathrm{mod}^{*}\ Q-1:=\begin{cases}y\in\\{1,\ldots,Q-1\\}\text{ so that
}y\equiv x\mod Q-1&\text{ if }x\neq 0\\\ 0&\text{ if }x=0\end{cases}.$

In particular, if we write $x\in\\{0,1,\ldots,Q-1\\}$ in base-$q$ as

$x=\sum_{b=0}^{t-1}x_{b}q^{b}$

for $x_{b}\in\\{0,\ldots,q-1\\}$, then

$\sigma_{i}(x)=\left\\{\sum_{b=0}^{t-1}x_{b}q^{b+i\mod t-1}\right\\}$

is a circular shift of this expansion.

######  Definition 8.

Let $0<k\leq n$ and consider the Reed-Solomon code $\mathcal{C}$ of dimension
$k$ with evaluation points $A=(\alpha_{1},\ldots,\alpha_{n})$ over
${\mathbb{F}}$. Let ${j_{\min}},{j_{\max}},d$ be positive integers so that
${j_{\min}}\leq{j_{\max}}$ and ${j_{\min}}<d$. We say that
$({j_{\min}},{j_{\max}},d)$ is _good_ for $\mathcal{C}$ if all of the
following hold:

  1. 1.

$d<n$ and ${j_{\max}}+k-1<n$;

  2. 2.

for all $i\in\\{1,\ldots,t-1\\}$,
$d\not\in\bigcup_{j={j_{\min}}}^{{j_{\max}}+k-1}\sigma_{i}(j)$; and

  3. 3.

$d\in\bigcup_{j={j_{\min}}}^{{j_{\max}}+k-1}\sigma_{0}(j)$,

where above $\sigma_{i}$ is defined as in Definition 7 with respect to $A$.
Given some $d,{j_{\min}},{j_{\max}}$, we define $\ell_{\min}$ and
$\ell_{\max}$ by

$\ell_{\min}=\max\\{0,d-{j_{\max}}\\}\qquad\text{and}\qquad\ell_{\max}=\min\\{k-1,d-{j_{\min}}\\}.$
(5)

######  Definition 9.

Fix $(d,{j_{\min}},{j_{\max}})$, and let $\ell_{\min},\ell_{\max}$ be as in
(5). Let $\mathbf{p}\in{\mathbb{F}}^{k}$, so that
$\mathrm{Supp}(\mathbf{p})\subseteq[\ell_{\min},\ell_{\max}]$. We say that a
polynomial

$v(X)=\sum_{j={j_{\min}}}^{{j_{\max}}}v_{j}X^{j}$

is _consistent_ with $\mathbf{p}$ (with respect to
$(d,{j_{\min}},{j_{\max}})$), if $v_{j}=p_{d-j}$ whenever $d-j\in[0,k-1]$.

Notice that, for any $\mathbf{p}$ as in Definition 9, there is some polynomial
$v(X)$ consistent with $\mathbf{p}$, given by
$v(X)=\sum_{j=\max\\{d-k+1,{j_{\min}}\\}}^{\min\\{d,{j_{\max}}\\}}p_{d-j}X^{j}.$

With these definitions, we have the following lemma.

######  Lemma 10.

Let $0<k\leq n$ and consider the Reed-Solomon code $\mathcal{C}$ of dimension
$k$ with evaluation points $A=(\alpha_{1},\ldots,\alpha_{n})$ over
${\mathbb{F}}$. Suppose that $({j_{\min}},{j_{\max}},d)$ is good for
$\mathcal{C}$, and let $\ell_{\min},\ell_{\max}$ be as in Definition 8. Then
for all $\mathbf{p}\in{\mathbb{F}}^{k}$ so that
$\mathrm{Supp}(\mathbf{p})\subseteq[\ell_{\min},\ell_{\max}]$, and for all
$v(X)$ consistent with $\mathbf{p}$, there exist ${\mathbb{B}}$-subspaces
$V_{1},\ldots,V_{n}\subset{\mathbb{F}}$ with $\dim_{{\mathbb{B}}}(V_{j})\leq
1$ for all $j$, so that the following holds:

Let $\mathbf{g}\in{\mathbb{F}}^{k}$ and let
$g(X)=\sum_{\ell=0}^{k-1}g_{\ell}X^{\ell}$. Suppose that $g(\alpha_{j})\in
V_{j}^{\perp_{\mathbb{B}}}$ for all $j\in[n]$. Then
$\mathbf{g}^{T}\mathbf{p}=0$.

Further, $V_{j}=\\{0\\}$ for all $j\in\mathcal{I}$, where
$\mathcal{I}=\left\\{j\in[n]\,:\,v(\alpha_{j})=0\right\\}$. (Notice that
$\mathcal{I}$ depends on both $\mathbf{p}$ and the choice of $v(X)$).

Before we prove Lemma 10, we show how to use it to obtain a linear evaluation
scheme for $\mathcal{C}$. The following Theorem is our main framework theorem
for RS codes.

######  Theorem 11 (Main Framework Theorem).

Let $\mathcal{C}$ be a Reed-Solomon code. Suppose that
$({j_{\min}},{j_{\max}},d)$ is good for $\mathcal{C}$. Let
$\ell_{\min},\ell_{\max}$ be as in (5), and let

$\mathcal{P}\subseteq\left\\{\mathbf{p}\in{\mathbb{F}}^{k}\,:\,\mathrm{Supp}(\mathbf{p})\subseteq[\ell_{\min},\ell_{\max}]\right\\}.$

Then there is a linear evaluation scheme $\varphi$ for $\mathcal{P}$ and
$\mathcal{C}$ with bandwidth at most $n\lceil\log|{\mathbb{B}}|\rceil$.

Further, for any collection

$\left\\{v_{\mathbf{p}}(X)\,:\,\mathbf{p}\in\mathcal{P}\right\\}$

so that for each $\mathbf{p}\in\mathcal{P}$, $v_{\mathbf{p}}(X)$ is consistent
with $\mathbf{p}$, there exists a scheme $\varphi$ that tolerates failures in

$\mathcal{I}:=\left\\{j\in[n]\,:\,v_{\mathbf{p}}(\alpha_{j})=0\ \
\forall\mathbf{p}\in\mathcal{P}\right\\},$

with bandwidth is at most

$(n-|\mathcal{I}|)\lceil\log|{\mathbb{B}}|\rceil.$

###### Proof of Theorem 11, assuming Lemma 10.

We prove the “Further” statement, since it implies that first statement.
(Indeed, we may take $v_{\mathbf{p}}(X)$ to be any polynomial consistent with
$\mathbf{p}$).

Suppose that $({j_{\min}},{j_{\max}},d)$ is good for $\mathcal{C}$. Let
$\mathbf{p}\in\mathcal{P}$, and suppose that $v_{\mathbf{p}}(X)$ is consistent
with $\mathbf{p}$. Let $\mathbf{G}\in{\mathbb{F}}^{n\times k}$ be a generator
matrix for $\mathcal{C}$ and let $\mathbf{w}$ be such that
$\mathbf{p}=\mathbf{G}^{T}\mathbf{w}$, as in Definition 4. Let
$V_{1},\ldots,V_{n}$ be the ${\mathbb{B}}$-subspaces guaranteed for
$\mathbf{p}$ and $v_{\mathbf{p}}(X)$ by Lemma 10, and define
$W_{j}=V_{j}^{\perp_{\mathbb{B}}}$ for $j=1,\ldots,n$. Let
$\mathcal{W}=W_{1}\times\cdots\times W_{n}$ and let
$\mathcal{V}=V_{1}\times\cdots\times V_{n}$.

The guarantee of Lemma 10 implies that $\mathbf{c}^{T}\mathbf{w}=0$ for all
$\mathbf{c}\in\mathcal{C}({\mathbb{F}}^{k})\cap\mathcal{W}$, so
$\mathbf{w}\in(\mathcal{C}({\mathbb{F}}^{k})\cap\mathcal{W})^{\perp}$. By
Lemma 6, this implies that

$\zeta_{i}\mathbf{w}\in\mathcal{C}({\mathbb{F}}^{k})^{\perp}+\mathcal{V}\qquad\forall
i\in[t],$

where $\zeta_{1},\ldots,\zeta_{t}$ is a basis for ${\mathbb{F}}$ over
${\mathbb{B}}$. Therefore from Definition 4, $(V_{1},\ldots,V_{n})$ is a
linear scheme for $\mathbf{p}$ and $\mathcal{C}$, and the map $\varphi$ that
maps $\mathbf{p}$ to $(V_{1},\ldots,V_{n})$ as above is a linear scheme for
$\mathcal{P}$ and $\mathcal{C}$.

Further, Lemma 10 implies that for all $\mathbf{p}\in\mathcal{P}$, if
$\varphi(\mathbf{p})=(V_{1},\ldots,V_{n})$ then $V_{j}=\\{0\\}$ for all
$j\in\mathcal{I}$. Thus, $\varphi$ tolerates failures in $\mathcal{I}$.

Finally, we observe that the bandwidth of the scheme is $\log|{\mathbb{B}}|$
times the number of $V_{j}$ so that $V_{j}\neq\\{0\\}$, which is at most
$(n-|\mathcal{I}|)\log|{\mathbb{B}}|$. ∎

Finally, we prove Lemma 10.

###### Proof of Lemma 10.

Suppose that $\mathcal{C}$ is an RS code as in the statement of the lemma, so
we have evaluation points $A=(\alpha_{1},\ldots,\alpha_{n})$. Suppose that
$({j_{\min}},{j_{\max}},d)$ is good for $\mathcal{C}$. Choose
$\mathbf{p}\in{\mathbb{F}}^{k}$ such that
$\mathrm{Supp}(\mathbf{p})\in[\ell_{\min},\ell_{\max}]$, and suppose that
$v(X)=\sum_{j={j_{\min}}}^{{j_{\max}}}v_{j}X^{j}$ is consistent with
$\mathbf{p}$. Define
$V_{j}:=\operatorname{span}_{{\mathbb{B}}}(v(\alpha_{j}))$ for $j\in[n]$.
Notice that $\dim_{\mathbb{B}}(V_{j})\leq 1$, as desired, and further that
$V_{j}=\\{0\\}$ if $v(\alpha_{j})=0$. Now suppose that
$\mathbf{g}\in{\mathbb{F}}^{k}$ so that
$g(X)=\sum_{\ell=0}^{k-1}g_{\ell}X^{\ell}$ has $g(\alpha_{j})\in
V_{j}^{\perp_{\mathbb{B}}}$. We wish to show that
$\mathbf{g}^{T}\mathbf{p}=0$.

From the definition of $V_{j}$ and the assumption that $g(\alpha_{j})\in
V_{j}^{\perp_{\mathbb{B}}}$ for all $j\in[n]$, we have

$\mathrm{tr}(v(\alpha_{j})g(\alpha_{j}))=0$

for all $j$. Consider the unique polynomial $R(X)$ of degree at most $n-1$ so
that

$R(X)\equiv\mathrm{tr}(v(X)g(X))\mod p_{A}(X),$

where $p_{A}(X)$ is as in Definition 7. Thus, $R(\alpha_{i})=0$ for all
$i\in[n]$. Since $\deg(R)\leq n-1$, this implies that $R(X)\equiv 0$ is
identically zero. Consider the coefficient of $X^{d}$ in $R(X)$. On the one
hand, this is zero. On the other hand, we can compute

$\displaystyle R(X)$
$\displaystyle=\sum_{i=0}^{t-1}\left(\sum_{j={j_{\min}}}^{{j_{\max}}}v_{j}X^{j}\right)^{q^{i}}\left(\sum_{\ell=0}^{k-1}g_{\ell}X^{\ell}\right)^{q^{i}}$
$\displaystyle=\sum_{i=0}^{t-1}\sum_{j,\ell}v_{j}^{q^{i}}g_{\ell}^{q^{i}}X^{q^{i}(\ell+j)}$

Thus, we have

$\displaystyle 0=\text{(coefficient of $X^{d}$ in $R(X)$)}$
$\displaystyle=\sum_{i=0}^{t-1}\sum_{j,\ell:d\in\sigma_{i}(\ell+j)}c_{\ell+j,d,i}v_{j}^{q^{i}}g_{\ell}^{q^{i}},$
(6)

where $c_{r,d,i}\in{\mathbb{F}}$ are the coefficients that arise when we write

$\overline{X^{rq^{i}}}=\sum_{d\in\sigma_{i}(r)}c_{r,d,i}X^{d}.$

(Above, as in Definition 7, $\overline{X^{rq^{i}}}$ refers to the residue
modulo $p_{A}(X)$). Since $(d,{j_{\min}},{j_{\max}})$ is good, Item 2 of
Definition 8 says that for all $i\neq 0$, and for all
$r\in[{j_{\min}},{j_{\max}}+k-1]$, $d\not\in\sigma_{i}(r)$. Since
$\ell+j\in[{j_{\min}},{j_{\max}}+k-1]$, this implies that the inner sum on the
right hand side of (6) is empty if $i\neq 0$. Therefore, we have

$\displaystyle 0$ $\displaystyle=\text{(coefficient of $X^{d}$ in $R(X)$)}$
$\displaystyle=\sum_{j,\ell:d\in\sigma_{0}(\ell+j)}c_{\ell+j,d,0}v_{j}g_{\ell}$
$\displaystyle=\sum_{j={j_{\min}}}^{{j_{\max}}}\sum_{\ell=0}^{k-1}\mathbf{1}_{\ell+j=d}v_{j}g_{\ell}$
(7)
$\displaystyle=\sum_{j=\max\\{d-k+1,{j_{\min}}\\}}^{\min\\{d,{j_{\max}}\\}}\sum_{\ell=0}^{k-1}\mathbf{1}_{\ell+j=d}v_{j}g_{\ell}$
(8) $\displaystyle=\sum_{\ell=\ell_{\min}}^{\ell_{\max}}p_{\ell}g_{\ell}$ (9)
$\displaystyle=\sum_{\ell=0}^{k-1}p_{\ell}g_{\ell}.$ (10)

Above, we have used in (7) the fact that $\sigma_{0}(\ell+j)=\\{\ell+j\\}$ (as
per Remark 5, using the assumption that $\ell+j\leq k-1+j_{\max}<n$ as per
Definition 8); and the fact that $c_{d,d,0}=1$ since we have
$\overline{X^{d}}=X^{d}$ (using the assumption that $d<n$). In (8), we have
used the fact that for $j\in[{j_{\min}},d-k]\cup[d+1,{j_{\max}}]$,
$\mathbf{1}_{\ell+j=d}=0$. In (9), we have used the definition (5) of
$\ell_{\min}$ and $\ell_{\max}$. And in (10), we have used the fact that
$\mathrm{Supp}(\mathbf{p})\subseteq[\ell_{\min},\ell_{\max}]$.

This shows that $\mathbf{p}^{T}\mathbf{g}=0$, which completes the proof. ∎

##  5 Proof of main theorem

We begin with a warm-up that already gives good schemes for RS codes of rates
approaching $1/2$.

######  Theorem 12.

Let $Q=q^{t}$, for some $t\geq 2$ and some prime power $q$. Suppose that
$k\leq
Q\left(\frac{1}{q}\left\lfloor\frac{q}{2}\right\rfloor\left(1-\frac{1}{q}\right)\right)$.
Let $\mathcal{C}$ be the Reed-Solomon code of dimension $k$ and length $n=Q$
over ${\mathbb{F}}={\mathbb{F}}_{Q}$. Let $\mathcal{F}$ be the class of all
linear functions from ${\mathbb{F}}^{k}$ to ${\mathbb{F}}$:

$\mathcal{F}=\left\\{\left(F_{\mathbf{y}}:\mathbf{x}\mapsto\mathbf{x}^{T}\mathbf{y}\right)\,:\,\mathbf{y}\in{\mathbb{F}}^{k}\right\\}.$

Then there is an evaluation scheme for $\mathcal{F}$ and $\mathcal{C}$ with
bandwidth $n\lceil\log_{2}q\rceil.$

Notice that the rate of the RS code $\mathcal{C}$ in Theorem 12 can be as
large as

$\frac{k}{n}=\frac{1}{q}\left\lfloor\frac{q}{2}\right\rfloor(1-1/q)\geq\frac{1}{2}-\frac{3}{2q},$

which approaches $1/2$ as $q$ grows. We note that for $q=2$, the rate of
$\mathcal{C}$ is $1/4$.

###### Proof of Theorem 12.

We will use Theorem 11 to show that there is a linear scheme for
$\mathcal{P}={\mathbb{F}}^{k}$. Then Proposition 5 will imply the theorem.

Choose

$\displaystyle d$ $\displaystyle=\left\lfloor\frac{q}{2}\right\rfloor q^{t-1}$
$\displaystyle{j_{\min}}$ $\displaystyle=\left\lfloor\frac{q}{2}\right\rfloor
q^{t-2}+1$ $\displaystyle{j_{\max}}$ $\displaystyle=Q-k.$

We claim that $(d,{j_{\min}},{j_{\max}})$ is good for $\mathcal{C}$. We check
the three items in Definition 8:

  1. 1.

Since $n=Q=q^{t}$, and using the choice of $d$ above, we have $d<n$. We also
have ${j_{\max}}+k-1=Q-1<n$.

  2. 2.

As per Remark 6, for this full-length RS code we have
$\sigma_{i}(j)=\\{jq^{i}\ \ \mathrm{mod}^{*}\ Q-1\\}$. Thus, the second item
in Definition 8 is equivalent333Note here that for all $i\geq 0$, $q^{i}$ is a
unit of $\mathbb{Z}/(Q-1)\mathbb{Z}$, and in particular $q^{t}\ \
\mathrm{mod}^{*}\ Q-1=Q\ \ \mathrm{mod}^{*}\ Q-1=1$. to showing that for all
$i=1,\ldots,t-1$,

$\displaystyle d$ $\displaystyle\neq q^{i}j\ \ \mathrm{mod}^{*}\
Q-1\qquad\forall j\in[{j_{\min}},{j_{\max}}+k-1]$ $\displaystyle dq^{t}\ \
\mathrm{mod}^{*}\ Q-1$ $\displaystyle\neq q^{i}j\ \ \mathrm{mod}^{*}\
Q-1\qquad\forall j\in[{j_{\min}},{j_{\max}}+k-1]$ $\displaystyle dq^{t-i}\ \
\mathrm{mod}^{*}\ Q-1$ $\displaystyle\neq j\ \ \mathrm{mod}^{*}\
Q-1\qquad\forall j\in[{j_{\min}},{j_{\max}}+k-1]$ $\displaystyle dq^{t-i}\ \
\mathrm{mod}^{*}\ Q-1$ $\displaystyle\not\in[{j_{\min}},{j_{\max}}+k-1].$

Plugging in the definitions of $d$, ${j_{\min}}$ and ${j_{\max}}$, this is the
same as showing that for all $i=1,\ldots,t-1$,

$\left\lfloor\frac{q}{2}\right\rfloor
q^{t-i-1}\not\in\left[\left\lfloor\frac{q}{2}\right\rfloor
q^{t-2}+1,Q-1\right].$

This is true, because for all $i=1,\ldots,t-1$, we have

$0<\left\lfloor\frac{q}{2}\right\rfloor
q^{t-i-1}<\left\lfloor\frac{q}{2}\right\rfloor q^{t-2}+1.$

  3. 3.

Finally, using the fact that $\sigma_{0}(j)=\\{j\\}$ for all
$j\in[{j_{\min}},{j_{\max}}+k-1]$, the third item is equivalent to showing
that $d\in[{j_{\min}},{j_{\max}}+k-1]$, or that

$\left\lfloor\frac{q}{2}\right\rfloor
q^{t-1}\in\left[\left\lfloor\frac{q}{2}\right\rfloor q^{t-2}+1,Q-1\right],$

which is true.

Thus, $(d,{j_{\min}},{j_{\max}})$ is good for $\mathcal{C}$. Now we compute
$\ell_{\min},\ell_{\max}$ as in Theorem 11. We have

$\displaystyle\ell_{\min}$ $\displaystyle=\max\\{0,d-{j_{\max}}\\}$
$\displaystyle=\max\left\\{0,\left\lfloor\frac{q}{2}\right\rfloor
q^{t-1}-q^{t}+k\right\\}$ $\displaystyle=0,$

using the fact that $Q=q^{t}$ and

$k\leq
Q\left(\frac{1}{q}\left\lfloor\frac{q}{2}\right\rfloor(1-1/q)\right)\leq
Q\frac{1}{q}\left\lfloor\frac{q}{2}\right\rfloor\leq
Q\left(1-\frac{1}{q}\left\lfloor\frac{q}{2}\right\rfloor\right).$

We also have

$\displaystyle\ell_{\max}$ $\displaystyle=\min\\{k-1,d-{j_{\min}}\\}$
$\displaystyle=\min\left\\{k-1,\left\lfloor\frac{q}{2}\right\rfloor
q^{t-1}-\left\lfloor\frac{q}{2}\right\rfloor q^{t-2}-1\right\\}$
$\displaystyle=k-1,$

using the fact that $k\leq
Q\left(\frac{1}{q}\left\lfloor\frac{q}{2}\right\rfloor(1-1/q)\right)$.
Therefore we have

$\left\\{\mathbf{p}\in{\mathbb{F}}^{k}\,:\,\mathrm{Supp}(\mathbf{p})\subseteq[\ell_{\min},\ell_{\max}]\right\\}={\mathbb{F}}^{k}.$

By Theorem 11 and the fact that $(d,{j_{\min}},{j_{\max}})$ is good for
$\mathcal{C}$, we conclude that there is a linear evaluation scheme $\varphi$
for $\mathcal{P}={\mathbb{F}}^{k}$, and $\mathcal{C}$, with bandwidth
$n\left\lfloor\log q\right\rfloor$, which is what we wanted to show. ∎

The reason that Theorem 12 has rate limited by $1/2$ is that if we were to
take $k$ to be larger, the interval $[\ell_{\min},\ell_{\max}]$ would not be
all of $[0,k-1]$. In the next theorem, we modify the construction in Theorem
12 to give a constant number of schemes like the one in Theorem 12, each of
which covers a small interval, but which together cover all of $[0,k-1]$.
Thus, we can increase the rate of the code to approach $1$, at the cost of
increasing the bandwidth by a constant factor. While we are at it, we give
ourselves enough freedom in order to choose the schemes so that they can
tolerate failures in any set $\mathcal{I}$ that is not too large.

######  Theorem 13.

Let $Q=q^{t}$, for some $t\geq 2$ and prime power $q$. Let
$\varepsilon,\gamma>0$. Let

$\delta\geq\gamma+\frac{1}{q},$

and suppose that $\varepsilon>\delta$ and that $(\varepsilon-\delta)q$ is an
integer. Suppose that $k\leq Q(1-\varepsilon)$, and let $\mathcal{C}$ be the
Reed-Solomon code of dimension $k$ and length $n=Q$ over
${\mathbb{F}}={\mathbb{F}}_{Q}$. Let $\mathcal{F}$ be the class of all linear
functions from ${\mathbb{F}}^{k}$ to ${\mathbb{F}}$:

$\mathcal{F}=\left\\{\left(f:\mathbf{x}\mapsto\mathbf{x}^{T}\mathbf{y}\right)\,:\,\mathbf{y}\in{\mathbb{F}}^{k}\right\\}.$

Let $\mathcal{I}\subset[n]$ be any set of size $|\mathcal{I}|<\gamma n$.

Then there is an evaluation scheme $\Phi$ for $\mathcal{F}$ and $\mathcal{C}$
that tolerates failures in $\mathcal{I}$, and that has bandwidth at most

$(n-|\mathcal{I}|)\cdot\left(\frac{1}{\varepsilon-\delta}\right)\cdot\lceil\log_{2}q\rceil.$

######  Remark 7.

For constant $\gamma$, the requirements on $\varepsilon,\gamma,\delta$ may be
satisfied with a choice of $\varepsilon=\gamma+\Theta(1/q)$. Thus, as $q$
grows, $\varepsilon$ may approach $\gamma$. This means that the trade-off
between the rate of the code ($1-\varepsilon$) and the fraction of failures
tolerated ($\gamma$) approaches the Singleton bound, which is optimal
(regardless of bandwidth).

######  Remark 8.

We have chosen to present Theorem 13 as it applies to the full-length Reed-
Solomon code of length $n=Q$. However, the scheme can also be used for shorter
codes with $n<Q$, as long as $Q-n\leq\gamma Q$. This is because the scheme
tolerates failures of up to $\gamma Q$ nodes, and we may instead imagine these
nodes never existed in the first place. In total, the number of failed or
nonexistent nodes can be at most $\gamma Q$.

###### Proof of Theorem 13.

Define $s$ to be the largest integer so that

$s<\frac{1}{\varepsilon-\delta}.$

where $\delta$ is as in the theorem statement. Before we proceed, we record
the following useful claim:

######  Claim 14.

With $\delta,\varepsilon$ as in the theorem statement, we have

$\delta\geq\frac{1-\varepsilon}{q-1}+\frac{\gamma}{1-1/q}.$

###### Proof.

We have

$\displaystyle\gamma+\frac{1}{q}$ $\displaystyle=\frac{1-1/q}{q-1}+\gamma$
$\displaystyle=\frac{1-1/q-\gamma}{q-1}+\frac{q\gamma}{q-1}$
$\displaystyle\geq\frac{1-\varepsilon}{q-1}+\frac{\gamma}{1-1/q},$

in the last line using the assumptions that

$\varepsilon\geq\delta\geq\gamma+\frac{1}{q}.$

∎

For $r=1,\ldots,s$, we will define a evaluation scheme $\Phi^{(r)}$ that
tolerates failures in $\mathcal{I}$. Each of these evaluation schemes will
only be able to recover linear functions with support in some window, but
together the $\Phi^{(r)}$ will form an evaluation scheme for all of
$\mathcal{F}$. We begin with the following claim.

######  Claim 15.

For $r=1,\ldots,s$, there is a choice of
$(d^{(r)},j_{\min}^{(r)},j_{\max}^{(r)})$ so that:

  1. 1.

$(d^{(r)},j_{\min}^{(r)},j_{\max}^{(r)})$ is good for $\mathcal{C}$ for all
$1\leq r\leq s$;

  2. 2.

$d^{(1)}-{j_{\max}}^{(1)}\leq 0$;

  3. 3.

$d^{(s)}-{j_{\min}}^{(s)}\geq k-1+Q\gamma$;

  4. 4.

for all $1\leq r<s$,

$\left(d^{(r)}-j_{\min}^{(r)}\right)-\left(d^{(r+1)}-{j_{\max}}^{(r+1)}\right)\geq
Q\gamma-1.$

###### Proof.

For $r=1,\ldots,s$, define

$y^{(r)}=(\varepsilon-\delta)qr.$

Note that since $r\leq s<\frac{1}{\varepsilon-\delta}$, we have
$(\varepsilon-\delta)r<1$, and so $y^{(s)}<q$. Further, by our assumption that
$(\varepsilon-\delta)q\in\mathbb{Z}$, $y^{(r)}$ is an integer. Define

$\displaystyle d^{(r)}$ $\displaystyle=y^{(r)}q^{t-1}$ $\displaystyle
j_{\min}^{(r)}$ $\displaystyle=y^{(r)}q^{t-2}+1$ $\displaystyle
j_{\max}^{(r)}$ $\displaystyle=Q-k.$

(Notice that these choices are reminiscent of the choices in the proof of
Theorem 12). First, we establish that each
$(d^{(r)},j_{\min}^{(r)},j_{\max}^{(r)})$ is good for $\mathcal{C}$. We check
the three conditions in Definition 8:

  1. 1.

For all $q\leq r\leq s$, we have $d^{(r)}=y^{(r)}q^{t-1}$. As noted above,
$y^{(s)}<q$, and so we have $d^{(r)}<q^{t}=Q=n$. Similarly we have
$j_{\max}^{(r)}+k-1=Q-1<n$.

  2. 2.

As in the proof of Theorem 12, it suffices to show that

$q^{t-i}d^{(r)}\ \ \mathrm{mod}^{*}\
Q-1\not\in[j_{\min}^{(r)},j_{\max}^{(r)}+k-1]$

for all $i=1,\ldots,t-1$. This is true since for all such $i$, we have

$0<q^{t-i}d^{(r)}\ \ \mathrm{mod}^{*}\ Q-1\leq y^{(r)}q^{t-2}<j_{\min}^{(r)}$

using the definition of $j_{\min}^{(r)}$.

  3. 3.

It suffices to show that $d^{(r)}\in[j_{\min}^{(r)},j_{\max}^{(r)}+k-1]$,which
is equivalent to $y^{(r)}q^{t-1}\in[y^{(r)}q^{t-2}+1,Q-1]$, which is true.

This establishes the first point of the claim.

For the second point, we observe that

$\displaystyle d^{(1)}-{j_{\max}}^{(1)}$
$\displaystyle=y^{(1)}q^{t-1}-q^{t}+k$
$\displaystyle=(\varepsilon-\delta)Q-Q+Q(1-\varepsilon)$
$\displaystyle=-\delta Q\leq 0.$

For the third point, we observe that

$\displaystyle d^{(s)}-{j_{\min}}^{(s)}$
$\displaystyle=y^{(s)}(q^{t-1}-q^{t-2})-1$
$\displaystyle=(\varepsilon-\delta)sQ(1-1/q)-1$
$\displaystyle\geq(\varepsilon-\delta)\left(\frac{1}{\varepsilon-\delta}-1\right)Q(1-1/q)-1$
$\displaystyle=(1-\varepsilon+\delta)Q(1-1/q)-1,$

using the fact that $s\geq\frac{1}{\varepsilon-\delta}-1$. In order for this
to be at least $k-1+Q\gamma=Q(1-\varepsilon+\gamma)-1$, we need

$\displaystyle(1-\varepsilon+\delta)(1-1/q)$ $\displaystyle\geq
1-\varepsilon+\gamma$ $\displaystyle\delta(1-1/q)-\frac{1-\varepsilon}{q}$
$\displaystyle\geq\gamma$ $\displaystyle\delta$
$\displaystyle\geq\frac{1-\varepsilon}{q-1}+\frac{\gamma}{1-1/q},$

which is indeed satisfied by our choice of $\delta$, by Claim 14. This
establishes the third point.

Finally, for the fourth point, we compute

$\displaystyle\left(d^{(r)}-j_{\min}^{(r)}\right)-\left(d^{(r+1)}-{j_{\max}}^{(r+1)}\right)$
$\displaystyle=y^{(r)}(q^{t-1}-q^{t-2})-1-y^{(r+1)}q^{t-1}+q^{t}-k$
$\displaystyle=Qr(\varepsilon-\delta)(1-1/q)-1-Q(r+1)(\varepsilon-\delta)+\varepsilon
Q$ $\displaystyle=Q(\delta-r(\varepsilon-\delta)/q)-1$ $\displaystyle\geq
Q(\delta-s(\varepsilon-\delta)/q)-1$ $\displaystyle\geq
Q\left(\delta-\left(\frac{1}{\varepsilon-\delta}\right)\left(\frac{\varepsilon-\delta}{q}\right)\right)-1$
$\displaystyle=Q(\delta-1/q)-1$ $\displaystyle\geq Q\gamma-1$

using the fact that $s\leq\frac{1}{\varepsilon-\delta}$ in the third-to-last
line, and using our assumption that $\delta\geq\gamma+1/q$ in the final line.
This establishes the last point, and proves the claim.

∎

######  Claim 16.

Let $(d^{(r)},j_{\min}^{(r)},j_{\max}^{(r)})$ be as in Claim 15, and let
$\ell_{\min}^{(r)}=\max\\{0,d^{(r)}-j_{\max}^{(r)}\\}$ and
$\ell_{\max}^{(r)}=\min\\{k-1,d^{(r)}-j_{\min}^{(r)}\\}$. For any
$\mathbf{p}\in{\mathbb{F}}^{k}$, there is a sequence
$\mathbf{p}^{(1)},\mathbf{p}^{(2)},\ldots,\mathbf{p}^{(s)}\in{\mathbb{F}}^{k}$
so that:

  1. 1.

For each $1\leq r\leq s$, we have

$\mathrm{Supp}(\mathbf{p}^{(r)})\subseteq[\ell_{\min}^{(r)},\ell_{\max}^{(r)}].$

  2. 2.

For each $1\leq r\leq s$, there exists a polynomial $v^{(r)}(X)$ that is
consistent with $\mathbf{p}^{(r)}$, such that $v^{(r)}(\alpha_{i})=0$ for all
$i\in\mathcal{I}$.

  3. 3.

We have $\sum_{r=1}^{s}\mathbf{p}^{(r)}=\mathbf{p}.$

###### Proof.

We prove the claim by induction. Suppose inductively that we have
$\mathbf{p}^{(1)},\ldots,\mathbf{p}^{(r-1)}$ and consistent polynomials
$v^{(1)}(X),\ldots,v^{(r-1)}(X)$, so that $v^{(1)},\ldots,v^{(r-1)}$ all
vanish on $\mathcal{I}$ and so that

$\left.\left(\sum_{j=1}^{r-1}\mathbf{p}^{(j)}\right)\right|_{[0,\ell_{\min}^{(r)}-1]}=\mathbf{p}|_{[0,\ell_{\min}^{(r)}-1]}.$
(11)

(For the base case, we define $\mathbf{p}^{(0)}=\mathbf{0}$, using Claim 15,
Item 2, to establish that that $d^{(1)}-{j_{\max}}^{(1)}\leq 0$ and hence
$\ell_{\min}^{(1)}=0$, and taking the convention that $[0,-1]=\emptyset$.)

Now, given $\mathbf{p}^{(1)},\ldots,\mathbf{p}^{(r-1)}$, we define
$\mathbf{p}^{(r)}$ for $r<s$ as follows. First, we define

$\left.\mathbf{p}^{(r)}\right|_{[\ell_{\min}^{(r)},\ell_{\min}^{(r+1)}-1]}=\left.\mathbf{p}\right|_{[\ell_{\min}^{(r)},\ell_{\min}^{(r+1)}-1]}-\sum_{j=1}^{r-1}\left.\mathbf{p}^{(j)}\right|_{[\ell_{\min}^{(r)},\ell_{\min}^{(r+1)}-1]}.$

Observe that, by induction, this implies that

$\left.\left(\sum_{j=1}^{r}\mathbf{p}^{(j)}\right)\right|_{[0,\ell_{\min}^{(r+1)}-1]}=\mathbf{p}|_{[0,\ell_{\min}^{(r+1)}-1]}.$

Now, we need to define
$\left.\mathbf{p}^{(r)}\right|_{[\ell_{\min}^{(r+1)},\ell_{\max}^{(r)}]}$ and
$v^{(r)}(X)$. Write

$v^{(r)}(X)=\sum_{j=j_{\min}^{(r)}}^{j_{\max}^{(r)}}v_{j}^{(r)}X^{j},$

where we must define the $v_{j}^{(r)}$. Whenever
$d^{(r)}-j\in[\ell_{\min}^{(r)},\ell_{\min}^{(r+1)}-1]$, we define

$v_{j}^{(r)}:=p^{(r)}_{d^{(r)}-j},$

noting that for such $j$, $p^{(r)}_{d^{(r)}-j}$ is already inductively
defined. Next, we choose the remaining coefficients $v_{j}^{(r)}$ in order to
make $v^{(r)}(X)$ vanish on $\mathcal{I}$. This is possible because the number
of free coefficients is at least $|\mathcal{I}|$. Indeed, we have already set
all of the coefficients for $j\geq d^{(r)}-\ell_{\min}^{(r+1)}+1$, and this
leaves free all of the coefficients from $j=j_{\min}^{(r)}$ to
$j=d^{(r)}-\ell_{\min}^{(r+1)}$. The number of these is

$\displaystyle d^{(r)}-\ell_{\min}^{(r+1)}-j_{\min}^{(r)}+1$
$\displaystyle=\left(d^{(r)}-j_{\min}^{(r)}\right)-\ell_{\min}^{(r+1)}+1$
$\displaystyle\geq\left(d^{(r)}-{j_{\min}}^{(r)}\right)-\left(d^{(r+1)}-{j_{\max}}^{(r+1)}\right)$
$\displaystyle\geq\gamma Q-1\geq|\mathcal{I}|,$

where in the last line we have used Claim 15, Item 4. Thus, we may choose the
remaining coefficients $v_{j}^{(r)}$ so that $v^{(r)}$ vanishes on
$\mathcal{I}$. Then we define

$p^{(r)}_{\ell}:=v_{d^{(r)}-\ell}^{(r)}$

for all $\ell\in[\ell_{\min}^{(r+1)},\ell_{\max}^{(r)}]$, noting that these
are all defined since $j_{\min}^{(r)}\leq d^{(r)}-\ell_{\max}^{(r)}$ and we
have defined the coefficients $v_{j}^{(r)}$ all the way down to
$j={j_{\min}}^{(r)}$.

Finally, we note that by construction,
$\mathrm{Supp}(\mathbf{p}^{(r)})\subseteq[\ell_{\min}^{(r)},\ell_{\max}^{(r)}]$,
and that $\mathbf{p}^{(r)}$ is consistent with $v^{(r)}$, so items 1 and 2 of
Claim 16 are satisfied for $r$.

Now we have constructed $\mathbf{p}^{(r)}$ and $v^{(r)}$ that satisfy the
inductive hypothesis (11) for $r$. By induction, we can construct these for
all $r=1,\ldots,s-1$.

To conclude, we will define $\mathbf{p}^{(s)}$ and $v^{(s)}$ slightly
differently. We choose $\mathbf{p}^{(s)}$ to have support contained in
$[\ell_{\min}^{(s)},k-1]$ so that

$\mathbf{p}^{(s)}|_{[\ell_{\min}^{(s)},k-1]}=\mathbf{p}|_{[\ell_{\min}^{(s)},k-1]}-\sum_{r=1}^{s-1}\mathbf{p}^{(r)}|_{[\ell_{\min}^{(s)},k-1]}.$

Then, as before, we define the corresponding coefficients of $v^{(s)}$ so that
$v^{(s)}$ is consistent with $\mathbf{p}^{(s)}$. To do this, we must define

$v^{(s)}_{j}:=p^{(s)}_{d^{(s)}-j}$

for all $j\in[{j_{\min}}^{(s)},{j_{\max}}^{(s)}]$ so that
$d^{(s)}-j\in[0,k-1]$. By Claim 15, Item 3, $d^{(s)}-{j_{\min}}^{(s)}\geq
k-1+\gamma Q$, so there are at least $\gamma Q$ values of
$j\in[{j_{\min}}^{(s)},{j_{\max}}^{(s)}]\setminus[d^{(s)}-k+1,d^{(s)}]$. Thus,
as above, we may use the fact that $|\mathcal{I}|<\gamma Q$ and choose
coefficients $v_{j}^{(s)}$ for $j$ in this set so that $v^{(s)}(X)$ vanishes
on $\mathcal{I}$.

Notice that Claim 15, Item 3, also implies that $\ell_{max}^{(s)}=k-1$, and so
we have that
$\mathrm{Supp}(\mathbf{p}^{(s)})\subseteq[\ell_{\min}^{(s)},\ell_{\max}^{(s)}]$
by construction. By construction we also have that $v^{(s)}(X)$ is consistent
with $\mathbf{p}^{(s)}$, and also that $v^{(s)}(X)$ vanishes on $\mathcal{I}$.
Thus points 1 and 2 in Claim 16 are satisfied for $\mathbf{p}^{(s)},v^{(s)}$
as well.

Finally, using (11) for $r=s-1$ and our choices for $\mathbf{p}^{(s)}$, we
have

$\displaystyle\sum_{r=1}^{s}\mathbf{p}^{(r)}$
$\displaystyle=\left.\left(\sum_{r=1}^{s}\mathbf{p}^{(r)}\right)\right|_{[0,\ell_{\min}^{(s)}-1]}+\left.\left(\sum_{r=1}^{s-1}\mathbf{p}^{(r)}\right)\right|_{[\ell_{\min}^{(s)},k-1]}+\mathbf{p}^{(s)}|_{[\ell_{\min}^{(s)},k-1]}$
$\displaystyle=\mathbf{p}|_{[0,\ell_{\min}^{(s)}-1]}+\mathbf{p}|_{[\ell_{\min}^{(s)},k-1]}$
$\displaystyle=\mathbf{p},$

as desired. This finishes the proof of the claim. ∎

Finally, we describe the scheme $\Phi$ that the theorem guarantees. For
$r=1,\ldots,s$, let $\mathcal{P}^{(r)}$ be the set of vectors
$\mathbf{p}^{(r)}\in{\mathbb{F}}^{k}$ that can arise from Claim 16. (That is,
Claim 16 says that for all $\mathbf{p}\in{\mathbb{F}}^{k}$, there exists
$\mathbf{p}^{(1)},\ldots,\mathbf{p}^{(s)}$ with particular properties; for
each $\mathbf{p}$ pick an arbitrary such sequence and include
$\mathbf{p}^{(r)}$ in $\mathcal{P}^{(r)}$.)

Let $\varphi^{(r)}$ be the linear scheme guaranteed by Theorem 11 for
$\mathcal{P}^{(r)}$, so $\varphi^{(r)}$ has bandwidth at most
$(n-|\mathcal{I}|)\lceil\log q\rceil$. (Here, we are using the fact from Claim
15 that $(d^{(r)},j_{\min}^{(r)},j_{\max}^{(r)})$ are good for $\mathcal{C}$).
The second point in Claim 16 ensures that each $\varphi^{(r)}$ tolerates
errors in $\mathcal{I}$.

Now, let $\Phi^{(r)}$ be the evaluation scheme guaranteed by Proposition 5. By
that proposition, each of these schemes has bandwidth at most
$(n-|\mathcal{I}|)\lceil\log q\rceil$, and also tolerates errors in
$\mathcal{I}$.

Finally, we define $\Phi$ as follows. Given $\mathbf{p}\in{\mathbb{F}}^{k}$,
define $F_{\mathbf{p}}:{\mathbb{F}}^{k}\to{\mathbb{F}}$ by
$F_{\mathbf{p}}(\mathbf{f})=\mathbf{f}^{T}\mathbf{p}$.

Scheme $\Phi$: Suppose that the original data was
$\mathbf{f}\in{\mathbb{F}}^{k}$. Given input $F_{\mathbf{p}}\in\mathcal{F}$:

  * •

Let $\mathbf{p}^{(1)},\ldots,\mathbf{p}^{(s)}$ be as in Claim 16.

  * •

For each $r=1,\ldots,s$, use $\Phi^{(r)}(\mathbf{p}^{(r)})$ to download
$(n-|\mathcal{I}|)\lceil\log q\rceil$ bits and recover
$\mathbf{f}^{T}\mathbf{p}^{(r)}$.

  * •

Return $\mathbf{f}^{T}\mathbf{p}=\sum_{r}\mathbf{f}^{T}\mathbf{p}^{(r)}$.

The correctness follows from Claim 16, and the bandwidth is at most

$(n-|\mathcal{I}|)\cdot s\cdot\lceil\log q\rceil.$

Plugging in the definition of $s$ proves the theorem.

∎

##  6 Conclusion

In this paper we considered low-bandwidth function evaluation on encoded data.
Special cases of this problem appear throughout computer science, engineering
and cryptography, and we believe that it is valuable to study this problem in
generality. We kick off this agenda by studying the problem for general linear
functions and for Reed-Solomon codes, arguably among the most natural classes
of functions and codes. However, we hope that this is just the tip of the
iceberg. We conclude with several questions left open by this work.

  1. 1.

Can we develop low-bandwidth evaluation schemes for other classes of
functions? (Beyond those mentioned in Remark 3 that are implied by our
results?) Low-degree polynomials are perhaps the next most natural class.

  2. 2.

Can we develop low-bandwidth evaluation schemes for linear functions, for
general linear codes? The first part of our framework (in Section 3) applies
to general linear codes, but the second part (Section 4) and our main theorem
applies only for RS codes.

  3. 3.

Can we extend our scheme to work in different parameter regimes? In
particular, our scheme works with full-length RS codes over extension fields.
Work from regenerating codes has shown how to use RS codes as regenerating
codes in very different parameter regimes, for example when $t$ is very large
[TYB18] or over prime fields [CT21]. Could these approaches be adapted to low-
bandwidth function evaluation?

## Acknowledgements

We thank Yuval Ishai for helpful conversations, and in particular for
suggesting the approach in Remark 4. We thank Ravi Vakil for helpful
conversations.

## References

  * [Bal12] Simeon Ball.  On sets of vectors of a finite vector space in which every subset of basis size is a basis.  Journal of the European Mathematical Society, 14(3):733–748, 2012\.
  * [BCG+17] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, and Michele Orrù.  Homomorphic secret sharing: optimizations and applications.  In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 2105–2122, 2017.
  * [BGI16] Elette Boyle, Niv Gilboa, and Yuval Ishai.  Breaking the circuit size barrier for secure computation under ddh.  In Annual International Cryptology Conference, pages 509–539. Springer, 2016.
  * [BGI+18] Elette Boyle, Niv Gilboa, Yuval Ishai, Huijia Lin, and Stefano Tessaro.  Foundations of homomorphic secret sharing.  In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * [BGP14] Daniele Bartoli, Massimo Giulietti, and Irene Platoni.  On the covering radius of mds codes.  IEEE Transactions on Information Theory, 61(2):801–811, 2014.
  * [BKS19] Elette Boyle, Lisa Kohl, and Peter Scholl.  Homomorphic secret sharing from lattices without fhe.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 3–33. Springer, 2019.
  * [CEPH] Ceph authors and contributors.  Ceph erasure code documentation.  https://docs.ceph.com/en/latest/rados/operations/erasure-code/, 2016\.  Last accessed: 2021.
  * [CGdW13] Victor Chen, Elena Grigorescu, and Ronald de Wolf.  Error-correcting data structures.  SIAM Journal on Computing, 42(1):84–111, 2013.
  * [CPE17] Zachary Charles, Dimitris Papailiopoulos, and Jordan Ellenberg.  Approximate gradient coding via sparse random graphs.  arXiv preprint arXiv:1711.06771, 2017.
  * [CT21] Roni Con and Itzhak Tamo.  Nonlinear repair schemes of reed-solomon codes.  arXiv preprint arXiv:2104.01652, 2021.
  * [DCG19] Sanghamitra Dutta, Viveck Cadambe, and Pulkit Grover.  “short-dot”: Computing large linear transforms distributedly using coded short dot products.  IEEE Transactions on Information Theory, 65(10):6171–6193, 2019\.
  * [DGW+10] Alexandros G Dimakis, P Brighten Godfrey, Yunnan Wu, Martin J Wainwright, and Kannan Ramchandran.  Network coding for distributed storage systems.  IEEE transactions on information theory, 56(9):4539–4551, 2010\.
  * [DM17] Hoang Dau and Olgica Milenkovic.  Optimal repair schemes for some families of full-length reed-solomon codes.  In 2017 IEEE International Symposium on Information Theory (ISIT), pages 346–350. IEEE, 2017.
  * [DRWS11] Alexandros G Dimakis, Kannan Ramchandran, Yunnan Wu, and Changho Suh.  A survey on network codes for distributed storage.  Proceedings of the IEEE, 99(3):476–489, 2011.
  * [FIKW21] Ingerid Fosli, Yuval Ishai, Victor Kolobov, and Mary Wootters.  On the download rate of homomorphic secret sharing, 2021.  Manuscript.
  * [FY92] Matthew Franklin and Moti Yung.  Communication complexity of secure computation.  In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 699–710, 1992.
  * [GW17] Venkatesan Guruswami and Mary Wootters.  Repairing Reed-Solomon codes.  IEEE transactions on Information Theory, 63(9):5684–5698, 2017\.
  * [HASH18] Wael Halbawi, Navid Azizan, Fariborz Salehi, and Babak Hassibi.  Improving distributed gradient descent using reed-solomon codes.  In 2018 IEEE International Symposium on Information Theory (ISIT), pages 2027–2031. IEEE, 2018.
  * [HDFS] Apache Hadoop.  HDFS erasure coding documentation.  https://hadoop.apache.org/docs/current/hadoop-project-dist/hadoop-hdfs/HDFSErasureCoding.html, 2015\.  Last accessed: 2021.
  * [LA20] Songze Li and Salman Avestimehr.  Coded Computing: Mitigating Fundamental Bottlenecks in Large-scale Distributed Computing and Machine Learning.  Now Foundations and Trends, 2020.
  * [LBWZY21] Andreas Lenz, Rawad Bitar, Antonia Wachter-Zeh, and Eitan Yaakobi.  Function-correcting codes.  arXiv preprint arXiv:2102.03094, 2021.
  * [LKAS18] Songze Li, Seyed Mohammadreza Mousavi Kalan, A Salman Avestimehr, and Mahdi Soltanolkotabi.  Near-optimal straggler mitigation for distributed gradient methods.  In 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pages 857–866. IEEE, 2018.
  * [LLP+17] Kangwook Lee, Maximilian Lam, Ramtin Pedarsani, Dimitris Papailiopoulos, and Kannan Ramchandran.  Speeding up distributed machine learning using codes.  IEEE Transactions on Information Theory, 64(3):1514–1529, 2017\.
  * [LMAYA17] Songze Li, Mohammad Ali Maddah-Ali, Qian Yu, and A Salman Avestimehr.  A fundamental tradeoff between computation and communication in distributed computing.  IEEE Transactions on Information Theory, 64(1):109–128, 2017.
  * [OSY21] Claudio Orlandi, Peter Scholl, and Sophia Yakoubov.  The rise of paillier: Homomorphic secret sharing and public-key silent ot.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 678–708. Springer, 2021.
  * [RS21] Lawrence Roy and Jaspal Singh.  Large message homomorphic secret sharing from dcr and applications.  IACR Cryptol. ePrint Arch., 2021:274, 2021.
  * [RTTD20] Netanel Raviv, Itzhak Tamo, Rashish Tandon, and Alexandros G Dimakis.  Gradient coding from cyclic mds codes and expander graphs.  IEEE Transactions on Information Theory, 66(12):7475–7489, 2020\.
  * [SPDC14] Karthikeyan Shanmugam, Dimitris S Papailiopoulos, Alexandros G Dimakis, and Giuseppe Caire.  A repair framework for scalar mds codes.  IEEE Journal on Selected Areas in Communications, 32(5):998–1007, 2014.
  * [TLDK17] Rashish Tandon, Qi Lei, Alexandros G Dimakis, and Nikos Karampatziakis.  Gradient coding: Avoiding stragglers in distributed learning.  In International Conference on Machine Learning, pages 3368–3376. PMLR, 2017.
  * [TYB18] Itzhak Tamo, Min Ye, and Alexander Barg.  The repair problem for reed–solomon codes: Optimal repair of single and multiple erasures with almost optimal node size.  IEEE Transactions on Information Theory, 65(5):2673–2695, 2018\.
  * [YA18] Min Ye and Emmanuel Abbe.  Communication-computation efficient gradient coding.  In International Conference on Machine Learning, pages 5610–5619. PMLR, 2018.
  * [YLR+19] Qian Yu, Songze Li, Netanel Raviv, Seyed Mohammadreza Mousavi Kalan, Mahdi Soltanolkotabi, and Salman A Avestimehr.  Lagrange coded computing: Optimal design for resiliency, security, and privacy.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1215–1225. PMLR, 2019.
  * [YMAA17a] Qian Yu, Mohammad Ali Maddah-Ali, and A Salman Avestimehr.  Coded fourier transform.  In 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 494–501. IEEE, 2017.
  * [YMAA17b] Qian Yu, Mohammad Ali Maddah-Ali, and A Salman Avestimehr.  Polynomial codes: an optimal design for high-dimensional coded matrix multiplication.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 4406–4416, 2017.

##  Appendix A Bandwidth lower bound

In this appendix, we observe a few lower bounds on the bandwidth required for
linear evaluation schemes.

We say that an MDS code with generator matrix
$\mathbf{G}\in{\mathbb{F}}^{n\times k}$ is maximal if there is no way to add a
row to extend $\mathbf{G}$ to a matrix
$\mathbf{G}^{\prime}\in{\mathbb{F}}^{(n+1)\times k}$ that is also MDS. The
following fact is standard.

######  Fact 17.

Reed-Solomon codes are not maximal.

###### Proof.

Let $\mathbf{G}\in{\mathbb{F}}^{n\times k}$ be the generator matrix for an RS
code over ${\mathbb{F}}={\mathbb{F}}_{Q}$. If $n<Q$, then we may extend
$\mathbf{G}$ to be the generator matrix of an RS code with a larger set of
evaluation points. If $n=Q$, then we may extend $\mathbf{G}$ to be the
generator matrix for the doubly-extended RS code, by adding the row
$(0,0,\ldots,0,1)$. ∎

First we observe that if $\mathcal{C}$ is a non-maximal MDS code, then any
lower bound that holds for repairing a single symbol in a regenerating code
also holds for linear evaluation schemes, for the class of all linear
functions. Indeed, suppose that $\mathbf{g}\in{\mathbb{F}}^{k}$ is the row
that we would add to $\mathbf{G}$ to get a new MDS matrix
$\mathbf{G}^{\prime}$. Then consider the linear function
$F(\mathbf{x})=\mathbf{g}^{T}\mathbf{x}$. Now $\mathbf{G}^{\prime}$
corresponds to an MDS code
$\mathcal{C}^{\prime}:{\mathbb{F}}^{k}\to{\mathbb{F}}^{n+1}$. If
$bc^{\prime}=\mathcal{C}^{\prime}(\mathbf{x})$, then
$c^{\prime}_{n+1}=F(\mathbf{x})$, and so any linear evaluation scheme that
will evaluate $F$ given access to $\mathbf{c}=\mathbf{c}^{\prime}|_{[n]}$ is
also a repair scheme for $\mathcal{C}^{\prime}$.

We can collect various lower bounds, including the cut-set bound of [DGW+10]
and the lower bound for MDS codes of [GW17] (see also [DM17] for a more
precise version), to obtain the following observation.

######  Observation 18.

Let ${\mathbb{F}}={\mathbb{F}}_{Q}$ where $Q=q^{t}$. Suppose that
$\mathcal{C}:{\mathbb{F}}^{k}\to{\mathbb{F}}^{n}$ is an MDS code that is not
maximally MDS. (In particular, $\mathcal{C}$ may be any RS code, by Fact 17).
Let $\mathcal{F}$ be the class of all linear functions
$F:{\mathbb{F}}^{k}\to{\mathbb{F}}$. Then any linear evaluation scheme for
$\mathcal{F}$ and for $\mathcal{C}$ over the base field
$\mathbb{B}={\mathbb{F}}_{q}$ must have bandwidth at least

$b\geq\max\left\\{k+t-1,t\left(\frac{n}{n-k+1}\right),n\log_{q}\left(\frac{n}{n-k+1}\right)\right\\}.$

We note that when $\mathcal{C}$ is a maximal MDS code (or not an MDS code at
all), the logic above does not go through. Indeed, if $\mathcal{C}$ is a
maximal MDS code, then definitionally any linear function of $\mathbf{x}$ can
be computed by looking at fewer than $k$ nodes. However, we are able to mimic
the proof of the lower bound from [GW17] for any linear code.

######  Proposition 19.

Let ${\mathbb{F}}={\mathbb{F}}_{Q}$, for $Q=q^{t}$. Let
$\mathcal{C}:{\mathbb{F}}^{k}\to{\mathbb{F}}^{n}$ be a linear code with
generator matrix $\mathbf{G}\in{\mathbb{F}}^{n\times k}$, let
$\mathbf{p}\in{\mathbb{F}}^{k}$, and suppose that $(V_{1},\ldots,V_{n})$ forms
a linear evaluation scheme for $\mathbf{p}$ and $\mathcal{C}$, over the base
field ${\mathbb{B}}={\mathbb{F}}_{q}$. Let $C=\mathcal{C}({\mathbb{F}}^{k})$.
Choose any $\mathbf{w}\in{\mathbb{F}}^{n}$ so that
$\mathbf{G}^{T}\mathbf{w}=\mathbf{p}$. Let

$d^{*}=\min_{\mathbf{y}\in C^{\perp}}\Delta(\mathbf{w},\mathbf{y}),$

where $\Delta$ denotes Hamming distance. Then the bandwidth $b$ of
$(V_{1},\ldots,V_{n})$ satisfies

$b\geq n\log_{q}\left(\frac{1}{1-(1-1/Q)d^{*}/n}\right).$

Before we prove Proposition 19, we observe a corollary for MDS codes.

######  Corollary 20.

Let ${\mathbb{F}}={\mathbb{F}}_{Q}$ where $Q=q^{t}$. Let
$\mathcal{C}:{\mathbb{F}}^{k}\to{\mathbb{F}}^{n}$ be an MDS code with $n>k+1$.
If $\varphi$ is a linear evaluation scheme for $\mathcal{C}$ and for
$\mathcal{P}={\mathbb{F}}^{k}$ over the base field
${\mathbb{B}}={\mathbb{F}}_{q}$, then $\varphi$ has bandwidth

$b\geq n\log_{q}\left(\frac{n}{n-k+3}\right).$

###### Proof.

Suppose that $\mathcal{C}:{\mathbb{F}}^{k}\to{\mathbb{F}}^{n}$ is an MDS code.
We show that the quantity $d^{*}$ in Proposition 19 is at least $k-1$. First,
we use the fact that the covering radius $r(\mathcal{C})$ of any MDS code
$\mathcal{C}$ satisfies

$r(\mathcal{C}):=\max_{\mathbf{w}\in{\mathbb{F}}^{n}}\min_{\mathbf{y}\in
C}\Delta(\mathbf{w},\mathbf{y})\geq n-k-1$ (12)

(see [BGP14]). Next, we observe that the quantity $\min_{\mathbf{y}\in
C^{\perp}}\Delta(\mathbf{w}^{T}\mathbf{p},\mathbf{y})$ does not depend on the
choice of $\mathbf{w}$. Indeed, suppose that $\mathbf{z}\in{\mathbb{F}}^{n}$
also satisfies $\mathbf{G}^{T}\mathbf{z}=\mathbf{p}$. Then
$\mathbf{G}^{T}(\mathbf{z}-\mathbf{w})=0$, so
$\mathbf{z}=\mathbf{w}+\mathbf{u}$ for some $\mathbf{u}\in C^{\perp}$. But
then

$\min_{\mathbf{y}\in
C^{\perp}}\Delta(\mathbf{w},\mathbf{y})=\min_{\mathbf{y}\in
C^{\perp}}\Delta(\mathbf{w},\mathbf{y}-\mathbf{u})=\min_{\mathbf{y}\in
C^{\perp}}\Delta(\mathbf{z},\mathbf{y}),$

where in the first equality we have changed the order of summation. In
particular, as $\mathbf{p}$ ranges over all of ${\mathbb{F}}^{k}$, we may
choose $\mathbf{w}$ to range over all of ${\mathbb{F}}^{n}$. Applying (12) for
$C^{\perp}$ (which we may do as the dual of an MDS code is again MDS), we see
that by choosing an appropriate $\mathbf{p}\in{\mathbb{F}}^{k}$, we may take

$d^{*}=\max_{\mathbf{w}\in{\mathbb{F}}^{n}}\min_{\mathbf{y}\in
C^{\perp}}\Delta(\mathbf{w},\mathbf{y})=r(C^{\perp})\geq k-1.$

(Above, we have switched the role of “$k$” and “$n-k$” from (12) since the
dimension of $C^{\perp}$ is $n-k$). This gives the required bound on $d^{*}$.
The corollary follows after plugging $d^{*}\geq k-1$ into Proposition 19, and
using the fact that $k\leq n\leq 2Q$ for any MDS code with $n>k+1$.444This
fact follows from (a) $q\geq n-k+1$ together with (b) $q\geq k+1$ if $n>k+1$.
See, e.g., [Bal12] Lemmas 1.2 and 1.3 for (a) and (b) respectively. ∎

###### Proof of Proposition 19.

The proof follows similarly to the lower bound for regenerating codes proved
in [GW17]. Let $\mathbf{p},\mathbf{w}$ be as in the statement of the
proposition and suppose that $(V_{1},\ldots,V_{n})$ forms a linear evaluation
scheme for $\mathbf{p}$ and $\mathcal{C}$, over the base field
${\mathbb{B}}={\mathbb{F}}_{q}$, with bandwidth at most $b$. Suppose that
$b_{j}=\dim(V_{j})$, so $\sum_{j=1}^{n}b_{j}\leq b$. Let
$C=\mathcal{C}({\mathbb{F}}^{k})$. By definition, this means that for all $i$,

$\zeta_{i}\mathbf{w}\in C^{T}+\mathcal{V},$

where $\mathcal{V}=V_{1}\times V_{2}\times\cdots\times V_{n}$. Let
$\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(t)}\in C^{\perp}$ and
$\mathbf{v}^{(1)},\ldots,\mathbf{v}^{(t)}\in\mathcal{V}$ be such that

$\zeta_{i}\mathbf{w}=\mathbf{y}^{(i)}+\mathbf{v}^{(i)}$

for all $i=1,\ldots,t$. Now consider a random vector
$\mathbf{b}\in{\mathbb{B}}^{t}$. From the above, we have

$\displaystyle\sum_{i}b_{i}\left(\zeta_{i}\mathbf{w}-\mathbf{y}^{(i)}\right)$
$\displaystyle=\sum_{i}b_{i}\mathbf{v}^{(i)}$
$\displaystyle\zeta_{\mathbf{b}}\mathbf{w}-\mathbf{y}_{\mathbf{b}}$
$\displaystyle\in\mathcal{V},$

where above we are defining $\zeta_{\mathbf{b}}=\sum_{i}b_{i}\zeta_{i}$ and
$\mathbf{y}_{\mathbf{b}}=\sum_{i}b_{i}\mathbf{y}^{(i)}$. Thus, the $j$’th
symbol of $\zeta_{\mathbf{b}}\mathbf{w}-\mathbf{y}_{\mathbf{b}}$ is in
$V_{j}$, and we claim that it is in fact uniform on a ${\mathbb{B}}$-subspace
of $V_{j}$. Indeed, this is because by definition we are choosing said $j$’th
symbol to be a random ${\mathbb{B}}$-linear combination of the elements
$\zeta_{i}w_{j}-y^{(i)}_{j}$ for $i=1,\ldots,t$, so it will be uniform on the
${\mathbb{B}}$-subspace spanned by those elements. Therefore, for each
$j=1,\ldots,n$, the probability that the $j$’th symbol of
$\zeta_{\mathbf{b}}\mathbf{w}-\mathbf{y}_{\mathbf{b}}$ is zero is at least
$1/|V_{j}|=q^{-b_{j}}$.

This implies that the expected number of zeros in
$\zeta_{\mathbf{b}}\mathbf{w}-\mathbf{y}_{\mathbf{b}}$ is at least

$\mathbb{E}\left|\left\\{j\in[n]\,:\,\zeta_{\mathbf{b}}w_{j}=(y_{\mathbf{b}})_{j}\right\\}\right|\geq\sum_{j=1}^{n}q^{-b_{j}}\geq
nq^{-b/n},$

where above we have used the fact that $\sum_{j}q^{-b_{j}}$ is minimized
(subject to $\sum_{j}b_{j}\leq b$) when all the $b_{j}$ are the same, and
equal to $b/n$. Thus,

$\mathbb{E}\Delta(\zeta_{\mathbf{b}}\mathbf{w},\mathbf{y}_{\mathbf{b}})\leq
n(1-q^{-b/n}).$

If $\mathbf{b}=\bm{0}$, the distance is zero, so

$\mathbb{E}\left[\Delta(\zeta_{\mathbf{b}}\mathbf{w},\mathbf{y}_{\mathbf{b}})\,\mid\,\mathbf{b}\neq\bm{0}\right]=\frac{q^{t}}{q^{t}-1}\mathbb{E}\Delta(\zeta_{\mathbf{b}}\mathbf{w},\mathbf{y}_{\mathbf{b}})\leq\frac{q^{t}}{q^{t}-1}n(1-q^{-b/n}).$

Thus, there exists a $\mathbf{b}\neq\bm{0}$ so that

$\Delta(\mathbf{w},\zeta^{-1}_{\mathbf{b}}\mathbf{y}_{\mathbf{b}})\leq\frac{q^{t}}{q^{t}-1}n(1-q^{-b/n}).$

Above, we have used the fact that $\zeta_{1},\ldots,\zeta_{t}$ form a basis,
so $\zeta_{\mathbf{b}}$ is nonzero if $\mathbf{b}$ is nonzero. As in the proof
of Corollary 20, we note that the definition of $d^{*}$ does not depend on the
choice of $\mathbf{w}$ so that $\mathbf{G}^{T}\mathbf{w}=\mathbf{p}$. Thus, by
the definition of $d^{*}$, we have that

$d^{*}\leq\Delta(\mathbf{w},\zeta^{-1}_{\mathbf{b}}\mathbf{y}_{\mathbf{b}})\leq\frac{q^{t}}{q^{t}-1}n(1-q^{-b/n}).$

Solving for $b$, we see that

$b\geq n\log_{q}\left(\frac{1}{1-(1-1/Q)d^{*}/n}\right),$

as desired. ∎