# Explicit Low-Bandwidth Evaluation Schemes for Weighted Sums of Reed-Solomon-
Coded Symbols

Han Mao Kiah  Wilton Kim  Stanislav Kruglik  San Ling  Huaxiong Wang
School of Physical and Mathematical Sciences Nanyang Technological University
Singapore
email: {hmkiah wilt0002  stanislav.kruglik  lingsan<EMAIL_ADDRESS>
###### Abstract

Motivated by applications in distributed storage, distributed computing, and
homomorphic secret sharing, we study communication-efficient schemes for
computing linear combinations of coded symbols. Specifically, we design low-
bandwidth schemes that evaluate the weighted sum of $\ell$ coded symbols in a
codeword $\boldsymbol{c}\in\mathbb{F}^{n}$, when we are given access to $d$ of
the remaining components in $\boldsymbol{c}$.

Formally, suppose that $\mathbb{F}$ is a field extension of $\mathbb{B}$ of
degree $t$. Let $\boldsymbol{c}$ be a codeword in a Reed-Solomon code of
dimension $k$ and our task is to compute the weighted sum of $\ell$ coded
symbols. In this paper, for some $s<t$, we provide an explicit scheme that
performs this task by downloading $d(t-s)$ sub-symbols in $\mathbb{B}$ from
$d$ available nodes, whenever $d\geq\ell|\mathbb{B}|^{s}-\ell+k$. In many
cases, our scheme outperforms previous schemes in the literature.

Furthermore, we provide a characterization of evaluation schemes for general
linear codes. Then in the special case of Reed-Solomon codes, we use this
characterization to derive a lower bound for the evaluation bandwidth.

##  1 Introduction

As applications in distributed storage and distributed computation become more
prevalent, communication bandwidth has become a critical performance metric of
codes. In such distributed settings, data is represented as a vector
${\boldsymbol{x}}=\mathbb{F}^{k}$ for some finite field $\mathbb{F}$. To
protect against erasures, the data is then encoded into a codeword
$\boldsymbol{c}=(c_{1},\ldots,c_{n})\in\mathbb{F}^{n}$ and each codeword
symbol $c_{i}$ is stored in one of $n$ nodes or servers. The beautiful Reed-
Solomon (RS) code [RS60] allows one to recover ${\boldsymbol{x}}$ by accessing
any available $k$ nodes. In other words, even if $n-k$ nodes fail, we are able
to recover the data. Unfortunately, this solution is not ideal in the scenario
where only one node fails. In this case, to repair a single node failure, i.e.
to recover one codeword symbol, we download $k$ codeword symbols. This is
costly as $k$ is usually much greater than one! Typically, the total amount of
information downloaded is referred to as the repair bandwidth and the repair
bandwidth problem was first introduced in [DGW+10]. Since then, there has been
a flurry of research to design new codes that reduce this repair bandwidth
[BKV+18, LO18]. Of interest to this paper is the pioneering work of Guruswami
and Wootters [GW17], where the authors revisit the ubiquitous Reed-Solomon
codes and demonstrate that the repair bandwidth can be reduced dramatically
when more than $k$ nodes are available. Later on, their methods were extended
in a variety of scenarios, including multiple erasures and different parameter
regimes [GW17, DM17, DD17, DDKM18, DDK+21, SW22, CT22, BBD+22].

In this paper, we consider the case where $\ell$ nodes are unavailable.
Instead of recovering the contents of these $\ell$ nodes, we recover a
weighted sum or linear combination of them. This is motivated by applications
in distributed computation. Specifically, in this setting, we have a
computation task ${\cal T}$ that is split into $\ell$ smaller subtasks ${\cal
T}_{1},{\cal T}_{2},\ldots,{\cal T}_{\ell}$, and we distribute these subtasks
to $\ell$ servers to compute locally. However, if there is a straggler among
these $\ell$ servers, that is, a server fails to complete its subtask, we are
unable to determine ${\cal T}$. To mitigate this straggler problem, we employ
coding and use $n>\ell$ servers. Specifically, we design a code and $n-\ell$
additional subtasks ${\cal T}_{\ell+1},{\cal T}_{\ell+2},\ldots,{\cal T}_{n}$
such that the following holds for any codeword
$\boldsymbol{c}=(c_{1},c_{2},\ldots,c_{n})$: we have $c_{i}$ corresponds to
the result of subtask ${\cal T}_{i}$ for $1\leq i\leq n$. As before, we
distribute these $n$ codeword symbols to $n$ servers. If the code is chosen to
be some code that corrects $n-d$ erasures, then we are able to determine
$c_{1},c_{2},\ldots,c_{\ell}$ as long as we have the results of any $d$ nodes.
Typically, for most computation tasks, the result of ${\cal T}$ is obtained
from a weighted sum of $c_{1},c_{2},\ldots,c_{\ell}$. Hence, the result of
${\cal T}$ is one symbol in $\mathbb{F}$. As before, we see that it is rather
wasteful if we simply download $d$ symbols from the $d$ available nodes.
Therefore, our central task is to reduce this amount of downloaded
information, which we refer to as evaluation bandwidth.

###  1.1 Motivating Example and Some Comparisons

We illustrate an application scenario of our evaluation schemes. Specifically,
we look at the problem of communication-efficient secure distributed matrix
multiplication (SDMM), studied by Machado et al. [MDEH21]. Consider two
matrices $\boldsymbol{A}$ and $\boldsymbol{B}$ with elements from $\mathbb{F}$
and we want to compute the product $\boldsymbol{A}\boldsymbol{B}$ in a secure
and distributed fashion. To this end, we split the initial task into $\ell$
subtasks of computing well-defined multiplication of sub-matrices
$\boldsymbol{A}_{i}\cdot\boldsymbol{B}_{i}$ ($i\in[\ell]$) where
$\boldsymbol{A}=\left[\begin{array}[]{c;{2pt/2pt}c;{2pt/2pt}c;{2pt/2pt}c}\boldsymbol{A}_{1}&\boldsymbol{A}_2&\cdots&\boldsymbol{A}_{\ell}\end{array}\right]$
and
$\boldsymbol{B}^{T}=\left[\begin{array}[]{c;{2pt/2pt}c;{2pt/2pt}c;{2pt/2pt}c}\boldsymbol{B}_{1}^{T}&\boldsymbol{B}_2^T&\cdots&\boldsymbol{B}_{\ell}^{T}\end{array}\right]^{T}$,
and $T$ denotes the transpose of the matrix. Therefore, we want to evaluate
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}=\sum_{i=1}^{\ell}\boldsymbol{A}_{i}\boldsymbol{B}_{i}$.

To both mitigate the presence of stragglers and provide security, Machado et
al. provided the following solution [MDEH21]. First, choose $n$ distinct
evaluation points
$\beta_{1},\ldots,\beta_{\ell},\alpha_{1},\ldots,\alpha_{n-\ell}$. Next, for
some security parameter $T\leq n-\ell$, generate $2T$ random matrices
$\boldsymbol{R}_{1},\ldots,\boldsymbol{R}_{T}$ and
$\boldsymbol{S}_{1},\ldots,\boldsymbol{S}_{T}$. Here, $\boldsymbol{R}_{i}$’s
and $\boldsymbol{A}_{i}$’s have the same dimensions, while
$\boldsymbol{S}_{i}$’s and $\boldsymbol{B}_{i}$’s have the same dimensions.
Next, we choose two polynomials111Strictly speaking, $\phi(x)$ (and $\psi(x)$)
is a multi-valued polynomial. That is,
$\phi(x)=\left[\phi_{st}(x)\right]_{st}$ where
$\left[\phi_{st}(x)\right]_{st}$ is matrix with the same dimensions as
$\boldsymbol{A}_{i}$’s and $\boldsymbol{R}_{i}$’s, and each $\phi_{st}(x)$ is
a polynomial of degree at most $\ell+T-1$. Nevertheless, the methods in our
work apply with a scaling of the bandwidth. $\phi(x)$ and $\psi(x)$ of degrees
at most $\ell+T-1$ such that the following hold.

$\displaystyle\phi(\beta_{i})$ $\displaystyle=\boldsymbol{A}_{i}$
$\displaystyle\psi(\beta_{i})$ $\displaystyle=\boldsymbol{B}_{i}$
$\displaystyle\text{ for }i\in[\ell],$ $\displaystyle\phi(\alpha_{i})$
$\displaystyle=\boldsymbol{R}_{i}$ $\displaystyle\psi(\alpha_{i})$
$\displaystyle=\boldsymbol{S}_{i}$ $\displaystyle\text{ for }i\in[T].$

Then for $i\in[n-\ell]$, we provide the server corresponding to $\alpha_{i}$
the values $\phi(\alpha_{i})$ and $\psi(\alpha_{i})$, and ask it to compute
$\theta(\alpha_{i})$ where $\theta(x)=\phi(x)\psi(x)$.

Now, observe that $\theta(x)$ is a polynomial of degree at most $2\ell+2T-2$
(see Section 2 for formal definitions). Hence, we have that
$\big{(}\theta(\beta_{1}),\ldots,\theta(\beta_{\ell}),\theta(\alpha_{1}),\ldots,\theta(\alpha_{n-\ell})\big{)}$
belongs to a Reed-Solomon code of length $n$ and dimension $k=2\ell+2T-1$.
Hence, we are able to find $\theta(\beta_{i})$’s and compute
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}$
using the results of any $k$ servers. Furthermore, Machado et al. showed that
any $T$ servers cannot collude to obtain any information on
$\boldsymbol{A}_{i}$’s and $\boldsymbol{B}_{i}$’s [MDEH21].

To reduce the evaluation bandwidth, Machado et al. in the same paper then
employ trace polynomials (see Section 2 for a formal definition) [MDEH21].
However, as the authors study codes that attain the so-called cut-set bound,
the proposed codes are defined over an impractically large field. For example,
when $\ell=4$ and $T=36$, then $k=79$, Machado et al.’s scheme requires a
minimal222Here, we refer to the smallest binary field ${\rm GF}(2^{t})$ where
the evaluation bandwidth is less than $kt$, the bandwidth used by the
classical approach. binary field $\textrm{GF}(2^{8085})$ and when
$\mathbb{F}={\rm GF}(2^{8085})$, the number of servers $n-\ell$ is at most
$128$. In this case, when $89$ nodes are available, Machado et al.’s scheme
recovers the four code symbols by downloading $516096$ bits. In contrast,
Scheme 1 (see Section 3) from this work can be defined over $\mathbb{F}={\rm
GF}(2^{8})$ and allows up to $n-\ell=252$ servers. In comparison333Admittedly,
relative to the codeword symbol, Machado et al.’s scheme downloads only 63.83
code symbols, while Scheme 1 downloads 69.5 code symbols and Scheme 2
downloads 66.9 code symbols. Nevertheless, Scheme 1 and Scheme 2 perform field
operations over a significantly smaller field., the evaluation bandwidth of
Scheme 1 only downloads 556 bits of information whenever 139 nodes are
available while the evaluation bandwidth of Scheme 2 only downloads 535 bits
whenever 107 nodes are available.

Figure 1: Recovery bandwidth for sums of $\ell=2$ codesymbols of RS code over
$\textrm{GF}(2^{8})$ with $k=79$

Next, we briefly describe certain evaluation / repair schemes that apply to
our scenario and (a detailed discussion is given in both Sections 2.2 and 5).
The first work due to Shutty and Wootters [SW22] considers a problem similar
to ours. Specifically, given some data vector
$\boldsymbol{x}\in\mathbb{F}^{k}$ and some linear function $S$, the authors
aim to recover $S({\boldsymbol{x}})$. Here, $k$ denotes the dimension of the
underlying code. In [SW22], a general low-bandwidth evaluation framework was
introduced and the authors demonstrate the existence of low-bandwidth
evaluation schemes. In contrast, for our setup, we are interested in obtaining
the weighted sum of $\ell$ coded symbols where $\ell<k$. While the schemes in
[SW22] clearly apply to our scenario, we exploit the fact that $\ell$ is small
to further reduce the bandwidth. For example, when $\ell=4$, $k=2^{30}$, and
$n=|\mathbb{F}|=2^{32}$, the scheme in [SW22] evaluates $S({\boldsymbol{x}})$
by downloading $26\cdot 2^{30}$ bits of information from $n-\ell$ available
nodes. In contrast, for the task with the same set of parameters, Schemes 1
and 2 only download $8\times 2^{30}$ and $7.5\times 2^{30}$ bits,
respectively. We also remark that generally the schemes in [SW22] require
large values of $|\mathbb{F}|$ and $k$ to improve over the classical repair
bandwidth.

Another approach to our task is to recover the $\ell$ coded symbols
independently and then proceed to evaluate
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}$.
This is therefore equivalent to the repair problem for multiple erasures.
Recently, Dau et al. [DDKM18] generalized the work of Guruswami and Wootters
to obtain low-bandwidth repair schemes for two and three erasures. Later,
Mardia, Bartan, and Wootters [MBW19] extended the repair schemes for any
number of erasures and improved the repair bandwidth in some cases. For
example, when $\ell=4$, $k=79$, and $n=|\mathbb{F}|=2^{8}$, the best scheme in
[MBW19] recovers all four code symbols by downloading $600$ bits of
information from $n-\ell$ available nodes. In contrast, when we simply want to
find a linear combination of these four symbols, the bandwidth can be reduced.
For the same set of parameters, Schemes 1 and 2 download $556$ and $535$ bits,
respectively.

To summarize this example, we fix $n=|\mathbb{F}|=2^{8}$ and $k=79$. In Figure
1, we fix $\ell=2$, vary the number of available nodes, and compare the
evaluation bandwidths of our schemes with those in [MBW19, SW22]. On the other
hand, in Table 1, we fix the number of available nodes to be $n-\ell$, vary
$\ell$ (the size of the weighted sum), and compare the evaluation bandwidths.
In the table, we also highlight the schemes that yield the lowest bandwidths.
In Section 5, we provide a more comprehensive set of comparisons by varying
$d$ and $\ell$. Generally, we observe that for most values of $d$ and $\ell$,
our schemes outperform those in [MBW19, SW22].

Scheme | $\ell=k=79$ | $\ell=40$ | $\ell=11$ | $\ell=5$ | $\ell=4$ | $\ell=2$
---|---|---|---|---|---|---
Naive | $632$ | $632$ | $632$ | $632$ | $632$ | $632$
[SW22] | $632$ | $632$ | $632$ | $632$ | $632$ | $632$
Scheme $1$ | $632$ | $632$ | $632$ | $616$ | $556$ | $410$
Scheme $2$ | $632$ | $632$ | $630$ | $564$ | $535$ | $410$
[MBW19, Theorem 2] | $632$ | $632$ | $632$ | $616$ | $600$ | $496$
[MBW19, Theorem 3] | $632$ | $632$ | $632$ | $632$ | $632$ | $409$
Fractional (Lower) Bound | $2$ | $64$ | $117$ | $128$ | $130$ | $134$
Integral (Lower) Bound | $2$ | $80$ | $139$ | $150$ | $152$ | $156$
Table 1: Recovery bandwidth for Reed-Solomon code over $\textrm{GF}(2^{8})$
and $k=79$

###  1.2 Our Contributions

Therefore, our task can be stated as follows. Consider a codeword
$\boldsymbol{c}=(c_{1},c_{2},\ldots,c_{n})$ of a Reed-Solomon code of length
$n$ and dimension $k$. Without loss of generality, we consider the first
$\ell$ positions and fix $\ell$ nonzero coefficients
$\kappa_{1},\kappa_{2},\ldots,\kappa_{\ell}\in\mathbb{F}$. Then given any
$d\leq n$ nodes, our objective is to design schemes that evaluate the sum
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}\triangleq\sum_{i=1}^{\ell}\kappa_{i}c_{i}$
by downloading as little information as possible from these $d$ nodes. For
ease of exposition, we assume that these $d$ nodes are distinct from the nodes
containing $c_{1},c_{2},\ldots,c_{\ell}$.

  1. (A)

Explicit low-bandwidth evaluation schemes for Reed-Solomon codes. In Section
3, we provide two explicit schemes to recover
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}=\sum_{i=1}^{\ell}\kappa_{i}c_{i}$
from some $d$ available nodes. We explicitly formulate the information to be
downloaded in terms of trace polynomials and subspace polynomials. While our
methods build upon the frameworks of [GW17, DDKM18, DDK+21], a key feature of
our schemes is that they can be adjusted according to the parameters: $\ell$
(the number of coded symbols in the sum
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}$)
and $d$ (the number of available nodes). As expected, the evaluation bandwidth
of our schemes is smaller when $\ell$ is smaller, or when $d$ is bigger.
Specifically, the evaluation bandwidths of the two schemes are as follows.

$\bullet$ Scheme 1: Let $\mathbb{F}$ be a field extension of $\mathbb{B}$ of
degree $t$. Whenever $d\geq\ell|\mathbb{B}|^{t-1}-\ell+k$, we can recover
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}$
by downloading $d$ subsymbols (in $\mathbb{B}$), or
$d\lceil\log_{2}|\mathbb{B}|\rceil$ bits, from any $d$ available nodes.

$\bullet$ Scheme 2: Suppose further that $W$ is a $\mathbb{B}$-linear subspace
of $\mathbb{F}$ with dimension $s$. Whenever
$d\geq\ell|\mathbb{B}|^{s}-\ell+k$, we can recover
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}$
by downloading $d(t-s)$ subsymbols (in $\mathbb{B}$), or
$d(t-s)\lceil\log_{2}|\mathbb{B}|\rceil$ bits, from any $d$ available nodes.

  2. (B)

Lower bound for the evaluation bandwidth for Reed-Solomon codes. By modifying
the techniques in [MBW19] and [LWJ19], we provide a characterization of
$\mathbb{B}$-linear evaluation schemes for general linear codes. Then in the
special case of Reed-Solomon codes, we use this characterization to determine
the required evaluation bandwidth. As with our evaluation schemes, the lower
bound depends on both $\ell$ and $d$. In the case where $\ell=1$ and $d=n-1$,
we recover the bounds obtained in [GW17, DM17]. Unfortunately, the bound is
not tight in general (see Figures 1 and 2, and Tables 1 and 2). Nevertheless,
this is the first nontrivial $\ell$\- and $d$-dependent bound, and is also a
lower bound on the repair bandwidth of multiple erasures (studied in [DDKM18,
MBW19]).

##  2 Preliminaries

Let $[n]$ denote the set of integers $\\{1,2,\ldots,n\\}$ and let $\mathbb{F}$
denote a finite field. An $\mathbb{F}$-linear code $[n,k]$ code $\mathcal{C}$
is an $\mathbb{F}$-linear subspace of dimension $k$. Each element of $\cal C$
is called a codeword. The orthogonal complement to $\mathcal{C}$ is called the
dual code $\mathcal{C}^{\perp}$. Then by definition, for each
$\boldsymbol{c}=(c_{1},\ldots,c_{n})\in\mathcal{C}$ and
$\boldsymbol{c}^{\perp}=(c_{1}^{\perp},\ldots,c_{n}^{\perp})\in\mathcal{C}^{\perp}$,
we have that $\sum_{i=1}^{n}c_{i}c_{i}^{\perp}=0$.

Of interest to this paper is the ubiquitous Reed-Solomon codes [RS60,
DNNM+22].

######  Definition 1.

Let $\mathbb{F}[x]$ denote the ring of polynomials over $\mathbb{F}$. The
Reed-Solomon code ${\rm RS}(\mathcal{W},k)$ of dimension $k$ with evaluation
points $\mathcal{W}=\\{\omega_{1},\dots,\omega_{n}\\}\subseteq\mathbb{F}$ is
defined as:

${\rm
RS}(\mathcal{W},k)=\left\\{(f(\omega_{1}),\ldots,f(\omega_{n})):f\in\mathbb{F}[x],\,\deg(f)<k\right\\}.$

On the other hand, the generalized Reed-Solomon code ${\rm
GRS}(\mathcal{W},k,\boldsymbol{\lambda})$ of dimension $k$ with evaluation
points $\mathcal{W}$ and multiplier
$\boldsymbol{\lambda}=(\lambda_{1},...,\lambda_{n})\in\mathbb{F}^{n}$, where
$\lambda_{i}\neq 0$ for all $i\in[n]$, is defined as:

${\rm
GRS}(\mathcal{W},k,\boldsymbol{\lambda})=\left\\{(\lambda_{1}f(\omega_{1}),\ldots,\lambda_{n}f(\omega_{n})):f\in\mathbb{F}[x],\,\text{deg}(f)<k\right\\}.$

Clearly, the generalized Reed-Solomon code ${\rm
GRS}(\mathcal{W},k,\boldsymbol{\lambda})$ with multiplier vector
$\boldsymbol{\lambda}=(1,...1)$ is a Reed-Solomon code
$\textrm{RS}(\mathcal{W},k)$ with the same set of evaluation points and
dimension. Another important fact is that the dual of
$\textrm{RS}(\mathcal{W},k)$ is
$\textrm{GRS}(\mathcal{W},n-k,\boldsymbol{\lambda})$, where the multiplier
vector can be explicitly given as (see, for example [MS77, Ch. 10, 12])

$\lambda_{i}=\prod_{j\in[n]\setminus\\{i\\}}(\omega_{i}-\omega_{j}).$ (1)

For convenience, when it is clear from context, $f(x)$ denotes a polynomial of
degree at most $k-1$ corresponding to a codeword in ${\rm RS}(\mathcal{W},k)$,
while $r(x)$ denotes a polynomial of degree at most $n-k-1$ corresponding to a
dual codeword from ${\rm GRS}(\mathcal{W},n-k,\boldsymbol{\lambda})$. Our low-
bandwidth schemes rely on the existence of low-degree polynomials $r(x)$ and
the following relation

$\displaystyle\sum_{i=1}^{n}\lambda_{i}f(\omega_{i})r(\omega_{i})=0.$ (2)

In what follows, we refer to polynomials $r(x)$ as parity-check polynomials
for $\mathcal{C}$. Of interest, we employ trace polynomials and subspace
polynomials. Formally, we describe our evaluation framework in the next
subsection.

###  2.1 Trace Recovery Framework

Suppose that $\mathbb{F}$ is a field extension of $\mathbb{B}$ of degree
$t\geq 1$. Throughout this paper, we refer to the elements of $\mathbb{F}$ as
symbols and the elements of $\mathbb{B}$ as sub-symbols. We also denote the
nonzero elements of $\mathbb{F}$ as $\mathbb{F}_{*}$. As mentioned in the
introduction, a remarkable property of Reed-Solomon codes is the following:
for any Reed-Solomon code of dimension $k$, we can reconstruct the entire word
$\boldsymbol{c}$ by accessing any $k$ symbols in $\boldsymbol{c}$. This is
also known as the maximum distance separable (MDS) property.

Fix $\ell\geq 1$ and some $\ell$-tuple
$\boldsymbol{\kappa}\in\mathbb{F}_{*}^{\ell}$. In this work, we are interested
in recovering the weighted sum
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}=\sum_{i=1}^{\ell}\kappa_{i}$
by accessing some $d\geq k$ available nodes. The classical approach downloads
$k$ symbols from any $k$-subset of the $d$ available nodes. Over $\mathbb{B}$,
the number of sub-symbols downloaded is $kt$ and the question we want to
address is: can we download less than $kt$ sub-symbols, especially when $d$ is
much greater than $k$?

Let us formally define a weighted-sum evaluation scheme for general
$\mathbb{F}$-linear code.

######  Definition 2.

Let $\mathbb{F}$ be a degree-$t$ field extension of $\mathbb{B}$. Let $\ell$
and $d$ be integers and $\mathcal{C}$ be an $\mathbb{F}$-linear code of length
$\ell+d$. We fix a set of coefficients
$\boldsymbol{\kappa}\in\mathbb{F}_{*}^{\ell}$. A
$(\boldsymbol{\kappa},\mathcal{C})$-weighted-sum evaluation scheme is defined
to be a collection of $d$ functions

$\displaystyle g_{j}\;:\;\mathbb{F}\to\mathbb{B}^{b_{j}}\text{ for }j\in[d]$
(3)

such that for all codewords $\boldsymbol{c}\in\mathcal{C}$, the weighted sum
$\sum_{i=1}^{\ell}\kappa_{i}c_{i}$ can be computed using values in the set
$\\{g_{j}(c_{\ell+j})\,:\,j\in[d]\\}$. The evaluation bandwidth $b$ is given
by $\sum_{j=1}^{d}b_{j}$. If the functions $g_{j}(j\in[d])$ along with the
function that determines the weighted sum $\sum_{i=1}^{\ell}\kappa_{i}c_{i}$
are all $\mathbb{B}$-linear, we say that the
$(\boldsymbol{\kappa},\mathcal{C})$-weighted sum evaluation scheme is
$\mathbb{B}$-linear.

In this work, we limit our attention to $\mathbb{B}$-linear evaluation schemes
only. To this end, we consider the trace function ${\rm
Tr}:\mathbb{F}\to\mathbb{B}$ defined as follows:

${\rm Tr}(x)=\sum_{i=0}^{t-1}x^{|\mathbb{B}|^{i}}\text{ for }x\in\mathbb{F}.$
(4)

It is straightforward to see that the trace function is $\mathbb{B}$-linear.
Furthermore, ${\rm Tr}(x)$ is a polynomial in $x$ with degree
$|\mathbb{B}|^{t-1}$. Hence, in this paper, we also refer to ${\rm Tr}(x)$ as
a trace polynomial. We also refer the interested reader to Lidl and
Niedderreiter [LN96, Ch. 2] for an in-depth overview of the properties of the
trace function. In fact, one crucial fact is that all $\mathbb{B}$-linear maps
defined over $\mathbb{F}$ can be described in terms of trace functions.

Thus far, we have a function that maps symbols in $\mathbb{F}$ to sub-symbols
in $\mathbb{B}$. Next, we describe a procedure to recover a symbol in
$\mathbb{F}$ using sub-symbols in $\mathbb{B}$. If we view $\mathbb{F}$ as a
$\mathbb{B}$-linear subspace of dimension $t$, we can define a
$\mathbb{B}$-basis $\\{u_{1},\ldots,u_{t}\\}$ for $\mathbb{F}$. Furthermore,
there exists a trace-dual basis
$\\{\widetilde{u}_{1},\ldots,\widetilde{u}_{t}\\}$ for $\mathbb{F}$ such that
${\rm Tr}(u_{i}\widetilde{u}_{j})=1$ if $i=j$, and ${\rm
Tr}(u_{i}\widetilde{u}_{j})=0$, otherwise. The following result plays a
crucial role in our evaluation framework.

######  Proposition 1.

[LN96, Ch. 2] Let $\\{u_{1},\ldots,u_{t}\\}$ be a $\mathbb{B}$-basis of
$\mathbb{F}$. Then there exists a trace-dual basis
$\\{\widetilde{u}_{1},\ldots,\widetilde{u}_{t}\\}$ and we can write each
element $x\in\mathbb{F}$ as

$x=\sum_{i=1}^{t}{\rm Tr}(u_{i}x)\widetilde{u}_{i}.$

Hence, following [GW17], our strategy to evaluate
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}$
is to compute $t$ independent traces ${\rm
Tr}(u_{i}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}})\,(i\in[t])$
by utilizing as little symbols in $\mathbb{B}$ as possible.

###  2.2 Related Work

As mentioned earlier, our problem of interest bears similarities with certain
previous work. Namely, one can obtain the evaluation of a weighted sum by
employing a scheme that either repairs multiple erasures or evaluates a
weighted sum of all data symbols. Hence, in this subsection, we review state-
of-the-art schemes for these scenarios and reformulate their results in terms
of $(\boldsymbol{\kappa},\mathcal{C})$-evaluation schemes.

  * •

Low-bandwidth repair of multiple erasures. Low-bandwidth repair for Reed-
Solomon codes was initiated by the pioneering paper of Guruswami and Wootters
[GW17]. In this work, Guruswami and Wootters introduced the trace repair
framework and designed an optimal repair schemes for the case of single
erasure. Specifically, they used trace polynomials as parity-check polynomials
and formed equations to determine the traces to download.

Later, in place of trace polynomials, Dau and Milenkovic studied the use of
subspace polynomials as parity-check polynomials and designed another class of
optimal repair schemes [DM17]. This setup was then generalized to the case of
two and three erasures in centralized and decentralized repair models in
papers [DDKM18, DDK+21, MBW19]. The trade-off between the sub-packetization
and bandwidth for multiple erasures was investigated in [LWJ19, CV21]. Herein,
we focus on the case of small sub-packetization level (of the order
$\log(n)$).

We also do not impose restrictions on the set of evaluation points and this is
noticeably different from related secret-sharing schemes in which each secret
is represented by a single field symbol (see, for example, [DLWX22] and the
references wherein). Specifically, in [DLWX22], the evaluation points, which
correspond to secrets, are required to satisfy certain algebraic properties.

Now, suppose that we have a low-bandwidth scheme that repairs $\ell$ erasures
by downloading information from any $d$ available nodes. Then for
$\boldsymbol{\kappa}\in\mathbb{F}_{*}^{\ell}$, we can first use the repair
scheme to recover the coded symbols $c_{1},c_{2},\ldots,c_{\ell}$ and then
compute the weighted sum
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}=\sum_{i\in[\ell]}\kappa_{i}c_{i}$.
Therefore, we obtain an $(\boldsymbol{\kappa},\mathcal{C})$-evaluation scheme
with the same bandwidth. In the following theorem, we summarize the state-of-
the-art results for low-bandwidth repair of multiple erasures.

######  Theorem 2 ([MBW19, Theorems 2 and 3]).

Let $\mathcal{B}$ and $\mathcal{A}$ be two disjoint subsets of distinct points
in $\mathbb{F}$ with $|\mathcal{B}|=\ell$ and $|\mathcal{A}|=d$ and let
$\boldsymbol{\kappa}\in\mathbb{F}_{*}^{\ell}$. For $\ell\leq k\leq\ell+d$, let
$\mathcal{C}$ be the Reed-Solomon code ${\rm
RS}(\mathcal{B}\cup\mathcal{A},k)$.

Suppose that $\mathbb{F}$ is a field extension of $\mathbb{B}$ with degree
$t$.

    1. (i)

If $s\leq t$ and $d\geq|\mathbb{B}|^{s}(2\ell-1)-2\ell+k+1$, there is an
$(\boldsymbol{\kappa},\mathcal{C})$-evaluation scheme with bandwidth $d(t-s)$
[MBW19, Theorem 2].

    2. (ii)

If
$t>\binom{\ell}{2}+\log_{|\mathbb{B}|}(1+\ell(\ell+\binom{\ell}{2}(|\mathbb{B}|-1))(|\mathbb{B}|-1))$
and $d\geq|\mathbb{B}|^{t-1}-\ell+k$, there is an
$(\boldsymbol{\kappa},\mathcal{C})$-evaluation scheme with bandwidth
$d\ell-(|\mathbb{B}|-1)\binom{\ell}{2}$ [MBW19, Theorem 3].

######  Remark 1.

Of interest are two parameter regimes for the repair of MDS codes that depends
on the degree of field extension $t$. The first one is when $t$ is
significantly larger than $n-k$. In this regime, we have the famous cut-set
(lower) bound [DGW+10] on repair bandwidth and there are codes attaining it
for one or several erasures [TYB19]. Another regime, which is more interesting
from the practical point of view, is when $t$ is small compared to $n-k$. In
this case, the cut-set bound cannot be met, but there exists a matching lower
bound for single erasure repair [DM17, GW17]. We note that deriving matching
lower bound for several erasures repair remains open. In our work, we focus on
this parameter regime, that is, $t$ is small.

  * •

Low-bandwidth function evaluation of Reed-Solomon encoded data. Recently, Lenz
et al. investigated the problem of designing codes for function evaluation of
information symbols transmitted over a noisy channel [LBWZY21]. In the paper,
the authors analyzed the trade-off between channel noise and coding rates for
general coding channels. Later, Shutty and Wootters studied such a problem for
Reed-Solomon codes and investigated the efficiency on the receiver side
[SW22]. More formally, they introduced the framework for low-bandwidth
recovery of weighted sum of Reed-Solomon encoded data while some of the coded
symbols may be erased.

Now, suppose that we have such a scheme that can tolerate $\ell$ erasures by
employing $d$ available nodes. Clearly, for
$\boldsymbol{\kappa}\in\mathbb{F}_{*}^{\ell}$ the weighted sum
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}=\sum_{i\in[\ell]}\kappa_{i}c_{i}$
of coded symbols $c_{1},c_{2},...,c_{\ell}$ can be transformed to the weighted
sum of information symbols. Therefore, we obtain an
$(\boldsymbol{\kappa},\mathcal{C})$-evaluation scheme with the same bandwidth.
The following theorem formalizes such a result.

######  Theorem 3 ([SW22]).

Let $\mathcal{B}$ and $\mathcal{A}$ be two disjoint subsets of distinct points
in $\mathbb{F}$ with $|\mathcal{B}|=\ell$ and $|\mathcal{A}|=d$ and let
$\boldsymbol{\kappa}\in\mathbb{F}_{*}^{\ell}$. For $\ell\leq k\leq\ell+d$, let
$\mathcal{C}$ be the Reed-Solomon code ${\rm
RS}(\mathcal{B}\cup\mathcal{A},k)$.

Suppose that $\mathbb{F}$ is a field extension of $\mathbb{B}$ with degree
$t$. For any positive number $s$, if $|\mathbb{B}|^{t-1}(s+1)+k+1\leq
d\leq|\mathbb{B}|^{t}-\ell$, then there is a
$(\boldsymbol{\kappa},\mathcal{C})$-evaluation scheme with bandwidth
$d|\mathbb{B}|/s$.

######  Remark 2.

Our notion of low-bandwidth function evaluation of Reed-Solomon encoded data
is closely related to information-theoretically secure single-client compact
Homomorphic Secret-Sharing (HSS) scheme whose parties jointly compute the sum
of the secrets from short messages formed by shares [BGI16, BCG+17, BGI+18,
RS21]. To the best of our knowledge, most constructions for HSS focus on
cryptographic security. The only exceptions are [SW22], whose main result is
formulated in Theorem 3, and [FIKW22], which focus on multi-client setup.

###  2.3 Results Overview

As mentioned earlier, our first result is the explicit construction of two
low-bandwidth weighted sum evaluation schemes. The schemes are formally
described in Section 3 and their properties are summarized in the following
theorem.

######  Theorem 4.

Let $\mathcal{B}$ and $\mathcal{A}$ be two disjoint subsets of distinct points
in $\mathbb{F}$ with $|\mathcal{B}|=\ell$ and $|\mathcal{A}|=d$ and let
$\boldsymbol{\kappa}\in\mathbb{F}_{*}^{\ell}$. For $\ell\leq k\leq\ell+d$, let
$\mathcal{C}$ be the Reed-Solomon code ${\rm
RS}(\mathcal{B}\cup\mathcal{A},k)$.

  1. (i)

Suppose $\mathbb{F}$ is a field extension of $\mathbb{B}$ with degree $t$. If
$d\geq\ell|\mathbb{B}|^{t-1}-\ell+k$, then Scheme 1 is a
$(\boldsymbol{\kappa},\mathcal{C})$-weighted sum evaluation scheme with
bandwidth $d$.

  2. (ii)

Suppose further ${\cal W}$ is a $\mathbb{B}$-linear subspace of $\mathbb{F}$
with dimension $s$. If $d\geq\ell|\mathbb{B}|^{s}-\ell+k$, then Scheme 2 is a
$(\boldsymbol{\kappa},\mathcal{C})$-weighted sum evaluation scheme with
bandwidth $d(t-s)$.

Our next result is a lower bound on the evaluation bandwidth of weighted-sum
schemes involving Reed-Solomon codes.

######  Theorem 5.

Let $\mathcal{B}$ and $\mathcal{A}$ be two disjoint subsets of distinct points
in $\mathbb{F}$ with $|\mathcal{B}|=\ell$ and $|\mathcal{A}|=d$. For $\ell\leq
k\leq\ell+d$, let $\mathcal{C}$ be the Reed-Solomon code ${\rm
RS}(\mathcal{B}\cup\mathcal{A},k)$. Then for any
$\boldsymbol{\kappa}\in\mathbb{F}_{*}^{\ell}$, we have that the evaluation
bandwidth is at least $b_{\min}$ where

$b_{\text{min}}=n_{0}\left\lfloor\log_{|\mathbb{B}|}\frac{d}{L}\right\rfloor+(d-n_{0})\left\lceil\log_{|\mathbb{B}|}\frac{d}{L}\right\rceil,$
(5)

and

$\displaystyle n_{0}$
$\displaystyle=\left\lfloor\frac{L-d|\mathbb{B}|^{-\left\lceil\log_{|\mathbb{B}|}\frac{d}{L}\right\rceil}}{|\mathbb{B}|^{-\left\lfloor\log_{|\mathbb{B}|}\frac{d}{L}\right\rfloor}-|\mathbb{B}|^{-\left\lceil\log_{|\mathbb{B}|}\frac{d}{L}\right\rceil}}\right\rfloor\,,$
(6) $\displaystyle L$
$\displaystyle=\frac{1}{|\mathbb{F}|}\Big{(}(|\mathbb{F}|-1)(\ell+d-k-1)+d\Big{)}\,.$
(7)

It is clear that any $\ell\leq k$ code symbols of the Reed-Solomon code are
linearly independent as vectors over $\mathbb{B}$, hence we cannot recover
$\ell$ erased code symbols with bandwidth smaller than those for evaluation of
their weighted sum. As a result, we can formulate the following corollary.

######  Corollary 6.

Let $\mathcal{B}$ and $\mathcal{A}$ be two disjoint subsets of distinct points
in $\mathbb{F}$ with $|\mathcal{B}|=\ell$ and $|\mathcal{A}|=d$. For $\ell\leq
k\leq\ell+d$, let $\mathcal{C}$ be the Reed-Solomon code ${\rm
RS}(\mathcal{B}\cup\mathcal{A},k)$. Then for erased symbols
$c_{1},c_{2},...,c_{\ell}$ we have that the recovery bandwidth is at least
$b_{\min}$, as defined by (5), (6) and (7).

##  3 Low-Bandwidth Evaluation Schemes

In this section, we provide two low-bandwidth schemes that evaluate the
weighted sum of $\ell$ Reed-Solomon coded symbols. Throughout this section, we
set $\mathcal{B}\triangleq\\{\beta_{1},...,\beta_{\ell}\\}$ and
$\mathcal{A}\triangleq\\{\alpha_{1},...,\alpha_{d}\\}$ to be two disjoint
subsets of distinct points in $\mathbb{F}$. Hence, we have that
$\ell+d\leq|\mathbb{F}|$. We further choose $f(x)$ to be a polynomial over
$\mathbb{F}$ with degree less than $k$. Suppose we have $d\geq k$ nodes and
for $j\in[d]$ we store in node $j$, the value $f(\alpha_{j})$.

Next, we fix an $\ell$-tuple of coefficients
$\boldsymbol{\kappa}\in\mathbb{F}_{*}^{\ell}$ and our task is to compute
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}=\sum_{i=1}^{\ell}\kappa_{i}f(\beta_{i})$
by downloading as few symbols from the other $d$ nodes. Specifically, we
provide a $(\kappa,\mathcal{C})$-weighted-sum evaluation scheme where
$\mathcal{C}$ is the Reed-Solomon code ${\rm RS}({\cal B}\cup{\cal A},k)$. To
this end, we consider a base field $\mathbb{B}$ such that $\mathbb{F}$ is a
field extension of degree $t$ over $\mathbb{B}$. We let
$\\{u_{1},\ldots,u_{t}\\}$ be a $\mathbb{B}$-basis of $\mathbb{F}$ and
$\\{\tilde{u}_{1},\ldots,\tilde{u}_{t}\\}$ be the corresponding dual basis.
Our first scheme (Scheme 1) uses trace polynomials defined by (4) and it
demonstrates our general framework. Later on, we describe Scheme 2 which uses
subspace polynomials in lieu of trace polynomials.

Scheme 1 : Scheme based on Trace Polynomials. Bandwidth:
$d\log_{2}{|\mathbb{B}|}$ bits

0: $\mathcal{A}\triangleq\\{\alpha_{j}:j\in[d]\\}$,
$\mathcal{B}\triangleq\\{\beta_{j}:j\in[\ell]\\}$, $f$ polynomial of degree at
most $k-1$

0:
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}\triangleq\sum_{i=1}^{\ell}\kappa_{i}c_{i}$

Pre-computation Phase

for $i\in[t]$, $j\in[d]$ do

pre-compute $\sigma_{i,j}\triangleq{\rm
Tr}(u_{i}(\alpha_{j}-\beta_{1})...(\alpha_{j}-\beta_{\ell}))$

Download Phase

for $j\in[d]$ do

download from node $j$ $\tau_{j}={\rm
Tr}\left(\frac{g(\alpha_{j})\lambda_{\ell+j}f(\alpha_{j})}{(\alpha_{j}-\beta_{1})\cdots(\alpha_{j}-\beta_{\ell})}\right)\in\mathbb{B}$
(8) where
$g(x)=\sum_{j=1}^{\ell}\frac{\kappa_{j}}{\lambda_{j}}\frac{\prod_{k\in[\ell],k\neq
j}(x-\beta_{k})}{\prod_{k\in[\ell],k\neq j}(\beta_{j}-\beta_{k})},$ (9) and
$\lambda_{j}$ are multipliers of the dual GRS code defined by (1).

Evaluation Phase

for $i\in[t]$ do

compute trace of
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}$
with respect to the basis element $u_{i}$. That is,  ${\rm
Tr}(u_{i}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}})=-\sum_{j=1}^{d}\sigma_{i,j}\tau_{j}.$
(10)

Finally, recover
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}$
using Proposition 1. That is, set
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}=\sum_{i=1}^{t}{\rm
Tr}(u_{i}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}})\tilde{u}_{i}$.

First, we provide a formal description of Scheme 1 and demonstrate its
correctness.

###### Proof of Theorem 4(i).

First, it is straightforward verify that only one sub-symbol in $\mathbb{B}$
is downloaded from each node. Hence, the evaluation bandwidth is $d$.

Next, we show that Scheme 1 is correct. Crucially, we prove that (10) holds
for all $i\in[t]$. Now, since
$(f(\omega))_{\omega\in\mathcal{B}\cup\mathcal{A}}$ belongs to ${\rm
RS}(\mathcal{B}\cup\mathcal{A},k)$, we consider its dual code ${\rm
GRS}(\mathcal{B}\cup\mathcal{A},n-k,\boldsymbol{\lambda})$ where
$\boldsymbol{\lambda}$ is defined by (1). Next, we use trace polynomials to
form parity-check polynomials. For $i\in[t]$, let

$r_{i}(x)\triangleq\frac{g(x){\rm
Tr}\left(u_{i}\prod_{j\in[\ell]}(x-\beta_{j})\right)}{\prod_{j\in[\ell]}(x-\beta_{j})},$
(11)

where $g(x)$ and $\boldsymbol{\lambda}$ are defined by (9) and (1),
respectively.

Observe that $g(\beta_{j})={\kappa_{j}}/{\lambda_{j}}$ for all $j\in[\ell]$.
Hence, $r_{i}(\beta_{j})=\frac{\kappa_{j}}{\lambda_{j}}u_{i}$ for all
$j\in[\ell]$. Furthermore, the polynomial $r_{i}(x)$ has degree
$\ell-1+\ell|\mathbb{B}|^{t-1}-\ell=\ell|\mathbb{B}|^{t-1}-1$. As
$d\geq\ell|\mathbb{B}|^{t-1}-\ell+k$, the polynomial $r_{i}(x)$ is indeed a
parity-check polynomial for $f(x)$. So, it follows from (2) that for
$i\in[t]$,

$\displaystyle
r_{i}(\beta_{1})\lambda_{1}f(\beta_{1})+\dots+r_{i}(\beta_{\ell})\lambda_{\ell}f(\beta_{\ell})$
$\displaystyle=-\sum_{j\in[d]}r_{i}(\alpha_{j})\lambda_{\ell+j}f(\alpha_{j}),\text{~{}~{}~{}or,}$
$\displaystyle
u_{i}\kappa_{1}f(\beta_{1})+\dots+u_{i}\kappa_{\ell}f(\beta_{\ell})$
$\displaystyle=-\sum_{j\in[d]}r_{i}(\alpha_{j})\lambda_{\ell+j}f(\alpha_{j}).$
(12)

Applying the trace function to both sides of the equation and utilizing its
linearity, we obtain

$\displaystyle{\rm
Tr}(u_{i}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}})$
$\displaystyle={\rm
Tr}\left(u_{i}\sum_{j\in[\ell]}\kappa_{j}f(\beta_{j})\right)$
$\displaystyle=-\sum_{j\in[d]}{\rm
Tr}(r_{i}(\alpha_{j})\lambda_{\ell+j}f(\alpha_{j}))$
$\displaystyle=-\sum_{j\in[d]}{\rm
Tr}\left(u_{i}(\alpha_{j}-\beta_{1})\cdots(\alpha_{j}-\beta_{\ell})\right){\rm
Tr}\left(\frac{g(\alpha_{j})\lambda_{\ell+j}f(\alpha_{j})}{(\alpha_{j}-\beta_{1})\cdots(\alpha_{j}-\beta_{\ell})}\right)$
$\displaystyle=-\sum_{j=1}^{d}\sigma_{i,j}\tau_{j},$

as required. ∎

Next, we present an instructive example of Scheme 1.

######  Example 1.

Let $\mathbb{B}=\textrm{GF}(4)=\\{0,1,b,1+b\\}$ with $b^{2}=b+1$, and let
$\mathbb{F}=\textrm{GF}(4^{2})=\\{0,1,\alpha,\ldots,\alpha^{14}\\}$ with
$\alpha^{2}=\alpha+b$ and $\alpha^{4}=\alpha+1$. So, $\mathbb{F}$ is a field
extension of $\mathbb{B}$ with degree $t=2$ and basis
$\\{u_{1},u_{2}\\}=\\{1,\alpha\\}$.

Set $\mathcal{B}=\\{0,1\\}$ and $\mathcal{A}=\\{\alpha,\ldots,\alpha^{14}\\}$
with $\ell=2$ and $d=14$. We consider the Reed-Solomon code $\mathcal{C}={\rm
RS}(\mathcal{B}\cup\mathcal{A},k)$ with $k=8$ and the polynomial $f(x)=x^{7}$.
In what follows, utilizing Scheme 1, we demonstrate the evaluation of
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}=f(0)+f(1)$
by downloading $d=14$ sub-symbols (in $\mathbb{B}$) from the nodes
corresponding to $\mathcal{A}$.

In the pre-computation phase, we compute the 28 values $\sigma_{i,j}={\rm
Tr}(u_{i})$ for $i\in[2]$ and $j\in[14]$. Then from the node storing $f(x)$,
we download the sub-symbol ${\rm
Tr}\left(\frac{f(x)}{x(x-1)}\right)\in\mathbb{B}$. Recall that in this case,
we have that ${\rm Tr}(x)=x+x^{4}$.

In summary, we have the following pre-computed and downloaded values.

Node $j$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Evaluation point | $\alpha$ | $\alpha^{2}$ | $\alpha^{3}$ | $\alpha^{4}$ | $\alpha^{5}$ | $\alpha^{6}$ | $\alpha^{7}$ | $\alpha^{8}$ | $\alpha^{9}$ | $\alpha^{10}$ | $\alpha^{11}$ | $\alpha^{12}$ | $\alpha^{13}$ | $\alpha^{14}$
$\sigma_{1,j}$ | $0$ | $0$ | $1$ | $0$ | $0$ | $1$ | $1$ | $0$ | $1$ | $0$ | $1$ | $1$ | $1$ | $1$
$\sigma_{2,j}$ | $b$ | $1+b$ | $1+b$ | $b$ | $1$ | $0$ | $1$ | $1+b$ | $1$ | $1$ | $b$ | $b$ | $0$ | $1+b$
$\tau_{j}$ | $1$ | $1$ | $1$ | $1$ | $0$ | $1$ | $1+b$ | $1$ | $1$ | $0$ | $b$ | $1$ | $1+b$ | $b$

Then in the evaluation phase, we use these values and (10) to obtain two
independent traces:

${\rm
Tr}(u_{1}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}})=0\quad\text{and}\quad{\rm
Tr}(u_{2}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}})=1,$

and using trace-dual basis
$\\{\widetilde{u}_{1},\widetilde{u}_{2}\\}=\\{\alpha^{4},1\\}$, we obtain our
desired value:

$f(0)+f(1)={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}={\rm
Tr}(u_{1}S)\widetilde{u}_{1}+{\rm
Tr}(u_{2}S)\widetilde{u}_{2}=0\cdot\alpha^{4}+1\cdot 1=1.$

In this case, we downloaded $14$ target traces of $2$ bits (in total $28$
bits), which is less than $32$ bits (if we download $8$ available symbols of
$4$ bits each).

Scheme 1 utilizes trace polynomials to form parity-check equations. In the
next scheme, we replace these polynomials by subspace polynomials and hence,
we obtain more flexibility in terms of possible values of $t$ and
$|\mathbb{B}|$ (see Section 5).

######  Definition 3.

Let $W$ be a $\mathbb{B}$-subspace of $\mathbb{F}$ with dimension $s<t$. The
subspace polynomial defined by $W$ can be written as

$L_{W}(x)=\prod_{\alpha\in W}(x-\alpha)=x\prod_{\alpha\in
W\setminus\\{0\\}}(x-\alpha)=\sum_{j=1}^{s}c_{j}x^{|\mathbb{B}|^{j}}\,.$ (13)

Observe that when $W$ is the kernel of the trace function (4), the subspace
polynomial corresponding to $W$ is in fact the trace polynomial. Moreover, one
can show that $L_{W}:\mathbb{F}\to\mathbb{F}$ is a $\mathbb{B}$-linear mapping
whose kernel is given by the subspace $W$. Therefore, the image of $L_{W}$,
denoted as $\textrm{Im}(L_{W})$, is a subspace of dimension $t-s$ over
$\mathbb{B}$ and we let $\\{\chi_{1},\dots,\chi_{t-s}\\}$ be a basis. Hence,
each element of it can be represented as a $\mathbb{B}$-linear combination of
the elements in $\\{\chi_{1},\dots,\chi_{t-s}\\}$.

We are now ready to describe Scheme 2 and provide the proof of Theorem 4(ii).

###### Proof of Theorem 4(ii).

First, it is straightforward to verify that $(t-s)$ sub-symbols in
$\mathbb{B}$ are downloaded from each node. Hence, the evaluation bandwidth is
$d(t-s)$.

Next, we show that Scheme 2 is correct, i.e., we prove that (19) holds for all
$i\in[t]$. Similarly, since
$(f(\omega))_{\omega\in\mathcal{B}\cup\mathcal{A}}$ belongs to ${\rm
RS}(\mathcal{B}\cup\mathcal{A},k)$, we consider its dual code ${\rm
GRS}(\mathcal{B}\cup\mathcal{A},n-k,\boldsymbol{\lambda})$ where
$\boldsymbol{\lambda}$ is defined by (1). However, instead of using trace
polynomials, we use subspace polynomials to form parity-check polynomials.
Specifically, for all $i\in[t]$, we set

$r_{W,i}(x)\triangleq\frac{g(x)L_{W}\left(u_{i}\prod_{j\in[\ell]}(x-\beta_{j})\right)}{\prod_{j\in[\ell]}(x-\beta_{j})},$
(14)

where $g(x)$ and $\boldsymbol{\lambda}$ are defined by (9) and (1),
respectively.

Observe that $g(\beta_{j})=\frac{\kappa_{j}}{c_{0}\lambda_{j}}$ for all
$j\in[\ell]$. Hence,
$r_{W,i}(\beta_{j})=g(\beta_{j})c_{0}u_{i}=u_{i}\frac{\kappa_{j}}{\lambda_{j}}$
for all $j\in[\ell]$. Furthermore, the polynomial $r_{W,i}(x)$ has degree
$\ell-1+\ell|\mathbb{B}|^{s}-\ell=\ell|\mathbb{B}|^{s}-1$. As
$d\geq\ell|\mathbb{B}|^{s}-\ell+k$, the polynomial $r_{W,i}(x)$ is indeed a
parity-check polynomial for $f(x)$. So, it follows from (2) that for
$i\in[t]$,

$\displaystyle
r_{W,i}(\beta_{1})\lambda_{1}f(\beta_{1})+\dots+r_{W,i}(\beta_{\ell})\lambda_{\ell}f(\beta_{\ell})$
$\displaystyle=-\sum_{j\in[d]}r_{W,i}(\alpha_{j})\lambda_{\ell+j}f(\alpha_{j}),\text{~{}~{}~{}or,}$
(15) $\displaystyle
u_{i}\kappa_{1}f(\beta_{1})+\dots+u_{i}\kappa_{\ell}f(\beta_{\ell})$
$\displaystyle=-\sum_{j\in[d]}r_{W,i}(\alpha_{j})\lambda_{\ell+j}f(\alpha_{j})$
(16)

Note that, for any $i\in[t]$,

$\displaystyle r_{W,i}(\alpha_{j})$
$\displaystyle=\frac{g(\alpha_{j})}{(\alpha_{j}-\beta_{1})\cdots(\alpha_{j}-\beta_{l})}L_{W}(u_{i}(\alpha_{j}-\beta_{1})\cdots(\alpha_{j}-\beta_{\ell}))$
$\displaystyle=\frac{g(\alpha_{j})}{(\alpha_{j}-\beta_{1})\cdots(\alpha_{j}-\beta_{\ell})}(\sigma_{i,j,1}\chi_{1}+\cdots+\sigma_{i,j,t-s}\chi_{t-s}),$

where $\sigma_{i,j,1},...,\sigma_{i,j,t-s}\in\mathbb{B}$ for all $j\in[d]$.
Applying the trace function to both sides of the equation (16) and utilizing
its linearity, we obtain

$\displaystyle{\rm
Tr}(u_{i}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}})$
$\displaystyle={\rm
Tr}\left(u_{i}\sum_{j\in[\ell]}\kappa_{j}f(\beta_{j})\right)$
$\displaystyle=-\sum_{j\in[d]}{\rm
Tr}\left(r_{W,i}(\alpha_{j})\lambda_{\ell+j}f(\alpha_{j})\right)$
$\displaystyle=-\sum_{j\in[d]}{\rm
Tr}\left(\frac{\sigma_{i,j,1}g(\alpha_{j})\lambda_{\ell+j}f(\alpha_{j})\chi_{1}}{(\alpha_{j}-\beta_{1})\ldots(\alpha_{j}-\beta_{\ell})}+\cdots+\frac{\sigma_{i,j,t-s}g(\alpha_{j})\lambda_{\ell+j}f(\alpha_{j})\chi_{t-s}}{(\alpha_{j}-\beta_{1})\ldots(\alpha_{j}-\beta_{\ell})}\right)$
$\displaystyle=-\sum_{j\in[d]}\left(\sigma_{i,j,1}\tau_{j,1}+\cdots+\sigma_{i,j,t-s}\tau_{j,t-s}\right),$

as required. ∎

Scheme 2 : Scheme based on Subspace Polynomials. Bandwidth:
$d(t-s)\log_{2}{|\mathbb{B}|}$ bits

0: $\mathcal{A}\triangleq\\{\alpha_{j}:j\in[d]\\}$,
$\mathcal{B}\triangleq\\{\beta_{j}:j\in[\ell]\\}$, $f$ polynomial of degree at
most $k-1$

0:
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}\triangleq\sum_{i=1}^{\ell}\kappa_{i}c_{i}$

Pre-computation Phase

for $i\in[t]$, $j\in[d]$ do

pre-compute $\sigma_{i,j,1},...,\sigma_{i,j,t-s}$ coefficients of
$L_{W}(u_{i}(\alpha_{j}-\beta_{1})\cdots(\alpha_{j}-\beta_{\ell}))$ in basis
$\\{\chi_{1},...,\chi_{t-s}\\}$

Download Phase

for $j\in[d]$ do

download from node $j$ $\tau_{j,m}={\rm
Tr}\left(\frac{g(\alpha_{j})\lambda_{\ell+j}f(\alpha_{j})\chi_{t-s}}{(\alpha_{j}-\beta_{1})\cdots(\alpha_{j}-\beta_{\ell})}\right)\in\mathbb{B}\text{~{}~{}~{}~{}for
$m\in[t-s]$,}$ (17) where,  $\displaystyle
g(x)=\sum_{j=1}^{\ell}\frac{\kappa_{j}}{\lambda_{j}}\frac{\prod_{k\in[\ell],k\neq
j}(x-\beta_{k})}{\prod_{k\in[\ell],k\neq j}(\beta_{j}-\beta_{k})},$ (18) and
$\lambda_{j}$ are multipliers of the dual GRS code defined by (1).

Evaluation Phase

for $i\in[t]$ do

compute trace of
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}$
with respect to the basis element $u_{i}$. That is,  ${\rm
Tr}(u_{i}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}})=-\sum_{j=1}^{d}\big{(}\sigma_{i,j,1}\tau_{j,1}+\cdots+\sigma_{i,j,t-s}\tau_{j,t-s}\big{)}$
(19)

Finally, recover
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}$
using Proposition 1. That is, set
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}=\sum_{i=1}^{t}{\rm
Tr}(u_{i}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}})\tilde{u}_{i}$.

##  4 Lower Bound on Evaluation Bandwidth

In this section, we provide a detailed proof of Theorem 5. First, following
[MBW19, LWJ19], we characterize a $(\boldsymbol{\kappa},\mathcal{C})$-weighted
sum recovery scheme for any $\mathbb{F}$-linear code in terms of a matrix
whose columns belong to its dual code.

Henceforth, $\mathbb{F}$ is an extension field of $\mathbb{B}$ with degree
$t$. Hence, each element in $\mathbb{F}$ can be considered as a column vector
of length $t$ over $\mathbb{B}$. In particular, we represent a vector in
$\mathbb{F}^{d}$ as a $(t\times d)$-matrix $\boldsymbol{M}$ over
$\mathbb{\mathbb{B}}$. Then we use ${\rm rank}_{\mathbb{B}}(\boldsymbol{M})$
to denote the rank of $\boldsymbol{M}$ over $\mathbb{B}$. We also adopt the
following matrix-vector notation. For a matrix $\boldsymbol{M}$, we use
$\boldsymbol{M}[i,j]$ to denote the entry in the $i$-th row and $j$-th column.
Moreover, we use $\boldsymbol{M}[i,:]$ and $\boldsymbol{M}[:,j]$ to refer to
the $i$-th row and $j$-th column of $\boldsymbol{M}$, respectively.

######  Definition 4.

Let $\mathcal{C}\subseteq\mathbb{F}^{\ell+d}$ be an $\mathbb{F}$-linear code.
Let us fix $\boldsymbol{\kappa}\in\mathbb{F}_{*}^{\ell}$. Then an
$(\ell+d)\times t$ matrix $\boldsymbol{M}$ whose entries belong to
$\mathbb{F}$ is called a $(\boldsymbol{\kappa},\mathcal{C})$-evaluation matrix
with bandwidth $b$ if the following conditions hold:

  1. (C1)

Columns of $\boldsymbol{M}$ are codewords in the dual code
$\mathcal{C}^{\perp}$.

  2. (C2)

For $i\in[\ell]$, the following holds

$\left(\prod_{i\neq 1}\kappa_{i}\right)\boldsymbol{M}[1,:]=\left(\prod_{i\neq
2}\kappa_{i}\right)\boldsymbol{M}[2,:]=\cdots=\left(\prod_{i\neq\ell}\kappa_{i}\right)\boldsymbol{M}[\ell,:].$
(20)

For convenience, we set $\boldsymbol{M}_{0}=(\prod_{i\neq
1}\kappa_{i})\boldsymbol{M}[1,:]$. Furthermore, we have ${\rm
rank}_{\mathbb{B}}\boldsymbol{M}_{0}=t$.

  3. (C3)

We have that

$\sum_{j\in[d]}{\rm rank}_{\mathbb{B}}\boldsymbol{M}[\ell+j,:]=b.$ (21)

Using this notion of evaluation matrix, we characterize when a code
$\mathcal{C}$ admits an evaluation scheme with certain bandwidth.

######  Theorem 7.

Let $\mathcal{C}\subseteq\mathbb{F}^{\ell+d}$ be an $\mathbb{F}$-linear code
and $\boldsymbol{\kappa}\in\mathbb{F}_{*}^{\ell}$. Then $\mathcal{C}$ admits a
$(\boldsymbol{\kappa},\mathcal{C})$-weighted-sum evaluation scheme with
bandwidth $b$ if and only if there exists a
$(\boldsymbol{\kappa},\mathcal{C})$-evaluation matrix with bandwidth $b$ that
satisfies the conditions in Definition 4.

The proof of Theorem 7 is similar to that in [MBW19, LWJ19] and so, we defer
it to the appendix. Instead, we construct the evaluation matrix corresponding
to Scheme 1 and verify Conditions (C1), (C2) and (C3).

######  Example 2.

Let $\mathcal{B}$ and $\mathcal{A}$ be sets of evaluation points as defined in
Section 3. Set $\mathcal{C}$ to be the Reed-Solomon code ${\rm
RS}(\mathcal{B}\cup\mathcal{A},k)$ and we consider the
$(\boldsymbol{\kappa},\mathcal{C})$-weighted-sum evaluation scheme given by
Scheme 1. Let $\\{u_{1},u_{2},\ldots,u_{t}\\}$ be $\mathbb{B}$-basis of
$\mathbb{F}$, then the corresponding evaluation matrix $\boldsymbol{M}$ is

$\boldsymbol{M}=\left[\begin{matrix}\kappa_{1}u_{1}&\cdots&\kappa_{1}u_{t}\\\
\vdots&\ddots&\vdots\\\ \kappa_{\ell}u_{1}&\ldots&\kappa_{\ell}u_{t}\\\
\dfrac{\sigma_{1,1}\lambda_{\ell+1}g(\alpha_{1})}{\prod_{j\in[\ell]}(\alpha_{1}-\beta_{j})}&\cdots&\dfrac{\sigma_{t,1}\lambda_{\ell+1}g(\alpha_{1})}{\prod_{j\in[\ell]}(\alpha_{1}-\beta_{j})}\\\
\vdots&\ddots&\vdots\\\
\dfrac{\sigma_{1,d}\lambda_{\ell+d}g(\alpha_{d})}{\prod_{j\in[\ell]}(\alpha_{d}-\beta_{j})}&\ldots&\dfrac{\sigma_{t,d}\lambda_{\ell+d}g(\alpha_{d})}{\prod_{j\in[\ell]}(\alpha_{d}-\beta_{j})}\end{matrix}\right]\,,$

where $g(x)$ and $\sigma_{i,j}$ are defined in Scheme 1.

To verify Condition (C1), we recall the definition of $r_{m}(x)$ in the proof
of Theorem 4(i) for $m\in[t]$. Then we observe that
$\kappa_{i}u_{m}=\lambda_{i}r_{m}(\beta_{i})$ for $i\in[\ell]$, and that
$\frac{\sigma_{m,i}\lambda_{\ell+i}g(\alpha_{i})}{\prod_{j\in[\ell]}(\alpha_{1}-\beta_{j})}=\lambda_{\ell+i}r_{m}(\alpha_{i})$.
In other words, the $m$-th column is given by
$(\lambda_{1}r_{m}(\beta_{1}),\ldots,\lambda_{\ell}r_{m}(\beta_{\ell}),\lambda_{\ell+d}r_{m}(\alpha_{\ell+1}),\ldots,\lambda_{\ell+d}r_{m}(\alpha_{\ell+d}))^{T}$.
Since $r_{m}(x)$ is a polynomial of degree at most $\ell+d-k-1$, the column is
a codeword in the dual of ${\rm RS}(\mathcal{B}\cup\mathcal{A},k)$.

To verify Condition (C2), we observe that $\left(\prod_{j\neq
i}\kappa_{j}\right)\boldsymbol{M}[i,:]=\left(\prod_{j\neq
i}\kappa_{j}\right)[u_{1},u_{2},\ldots,u_{t}]$. Since
$\\{u_{1},u_{2},\ldots,u_{t}\\}$ is a basis, we have that $\left(\prod_{j\neq
i}\kappa_{j}\right)[u_{1},u_{2},\ldots,u_{t}]$ is of full-rank over
$\mathbb{B}$, as required by Condition (C2).

Finally, for $i\in[d]$, we have that

$\boldsymbol{M}[\ell+i,:]=\Big{[}\sigma_{1,i},\sigma_{2,i},\ldots,\sigma_{t,i}\Big{]}\frac{\lambda_{\ell+i}g(\alpha_{i})}{\prod_{i\in[\ell]}(\alpha_{i}-\beta_{j})}\,,$

and thus, ${\rm rank}_{\mathbb{B}}\boldsymbol{M}[\ell+i,:]=1$. Therefore, we
verify Condition (C3) and have that the corresponding evaluation bandwidth is
$d$, corroborating Theorem 4(i).

As before, we pick two disjoint subsets
$\mathcal{B}\triangleq\\{\beta_{i}:i\in[\ell]\\}$,
$\mathcal{A}\triangleq\\{\alpha_{j}:j\in[d]\\}$ and $k\leq\ell+d$. We set
$\mathcal{C}$ to be the Reed-Solomon code ${\rm
RS}(\mathcal{B}\cup\mathcal{A},k)$ and for the rest of the section, we derive
a lower bound for the evaluation bandwidth of a
$(\boldsymbol{\kappa},\mathcal{C})$-weighted sum recovery scheme.

First, we characterize the evaluation matrix (defined in Theorem 7) in terms
of parity-check polynomials in its dual code. Specifically, we have the
following lemma.

######  Lemma 8.

Let $\mathcal{C}$ be ${\rm RS}(\mathcal{B}\cup\mathcal{A},k)$. If
$\boldsymbol{M}\in\mathbb{F}^{(\ell+d)\times t}$ is a
$(\boldsymbol{\kappa},\mathcal{C})$-evaluation matrix, then there exist $t$
polynomials $p_{1}(X),\ldots,p_{t}(X)$ with $\deg p_{j}(X)\leq\ell+d-k-1$ so
that for all $j\in[t]$,

$\boldsymbol{M}[i,j]=\begin{cases}\lambda_{i}p_{j}(\beta_{i}),&\text{ if
}i\leq\ell,\\\ \lambda_{i}p_{j}(\alpha_{i-\ell}),&\text{ if }\ell+1\leq i\leq
d+\ell.\end{cases}$ (22)

Here, $\lambda_{i}$ are multipliers of the dual GRS code defined by (1).

###### Proof.

The result immediately follows from the fact that the dual of the Reed-Solomon
code is a generalized Reed-Solomon code with multipliers given by (1) and
Condition (C1) of an evaluation matrix. ∎

Let ${\cal P}$ be the set of polynomials $p_{1}(X),\ldots,p_{t}(X)$ in Lemma
8. For ${\boldsymbol{x}}=(x_{1},\ldots,x_{t})\in\mathbb{B}^{t}$, we set
$p_{{\boldsymbol{x}}}(X)\triangleq x_{1}p_{1}(X)+\cdots+x_{t}p_{t}(X)$, a
$\mathbb{B}$-linear combination of polynomials in ${\cal P}$. Then for
$\omega\in\mathcal{B}\cup\mathcal{A}$, we consider the set
$S_{\omega}=\\{{\boldsymbol{x}}\in\mathbb{B}^{t}\setminus\\{\boldsymbol{0}\\}:\,p_{\boldsymbol{x}}(\omega)=0\\}$
and the quantity

$\Omega=\frac{1}{|\mathbb{F}|-1}\sum_{{\boldsymbol{x}}\in\mathbb{B}^{t}\setminus\\{\boldsymbol{0}\\}}\sum_{\omega\in\mathcal{B}\cup\mathcal{A}}\mathbb{I}({\boldsymbol{x}}\in
S_{\omega}).$ (23)

Here, $\mathbb{I}$ is the indicator function.

Now, for $i\in[d]$, we consider the value $b_{i}\triangleq{\rm
rank}_{\mathbb{B}}(\boldsymbol{M}[\ell+i,:])=$ ${\rm
rank}_{\mathbb{B}}\\{\lambda_{i}p_{1}(\alpha_{i}),\ldots,\lambda_{i}p_{t}(\alpha_{i})\\}={\rm
rank}_{\mathbb{B}}\\{p_{1}(\alpha_{i}),\ldots,p_{t}(\alpha_{i})\\}$. Then from
Condition (C3) of Definition 4, we have that $\sum_{i\in[d]}b_{i}=b$. In what
follows, we compute $\Omega$ in two different ways and obtain certain
constraints on the values of $b_{i}$’s.

######  Lemma 9.

The quantity $\Omega$ is given by

$\Omega=\frac{1}{|\mathbb{F}|-1}\sum_{i\in[d]}(|\mathbb{B}|^{t-b_{i}}-1).$

###### Proof.

First, observe that ${\boldsymbol{x}}\in S_{\omega}$ if and only if
${\boldsymbol{x}}$ belongs to the null space of the matrix
$[p_{1}(\omega),\ldots,p_{t}(\omega)]$. In other words, for
$\omega\in\mathcal{B}\cup\mathcal{A}$, we have
$\sum_{{\boldsymbol{x}}\in\mathbb{B}^{t}\setminus\\{\boldsymbol{0}\\}}\mathbb{I}({\boldsymbol{x}}\in
S_{\omega})=|\mathbb{B}|^{t-b_{\omega}}-1$, where $b_{\omega}$ is the rank of
$[p_{1}(\omega),\ldots,p_{t}(\omega)]$. Now, if $\omega\in\mathcal{B}$, we
have that $b_{\omega}=t$ from Condition (C2) and so,
$\sum_{{\boldsymbol{x}}\in\mathbb{B}^{t}\setminus\\{\boldsymbol{0}\\}}\mathbb{I}({\boldsymbol{x}}\in
S_{\omega})=0$. On the other hand, for $i\in[d]$, we have that
$b_{\alpha_{i}}=b_{i}$ and so,
$\sum_{{\boldsymbol{x}}\in\mathbb{B}^{t}\setminus\\{\boldsymbol{0}\\}}\mathbb{I}({\boldsymbol{x}}\in
S_{\alpha_{i}})=|\mathbb{B}|^{t-b_{i}}-1$. Therefore, after switching the
summation order, we have

$\sum_{{\boldsymbol{x}}\in\mathbb{B}^{t}\setminus\\{\boldsymbol{0}\\}}\sum_{\omega\in\mathcal{B}\cup\mathcal{A}}\mathbb{I}({\boldsymbol{x}}\in
S_{\omega})=\sum_{\omega\in\mathcal{B}\cup\mathcal{A}}\sum_{{\boldsymbol{x}}\in\mathbb{B}^{t}\setminus\\{\boldsymbol{0}\\}}\mathbb{I}({\boldsymbol{x}}\in
S_{\omega})=\sum_{i\in[d]}(|\mathbb{B}|^{t-b_{i}}-1)\,.$

Hence, the lemma follows. ∎

######  Lemma 10.

We have the following inequality:

$\Omega\leq(l+d)-k-1.$

###### Proof.

Now, ${\boldsymbol{x}}^{*}\in S_{\omega}$ implies that $\omega$ is a root of
the polynomial $x_{1}^{*}p_{1}(X)+\cdots+x_{t}^{*}p_{t}(X)$. Since $\Omega$ is
the average number of such roots, there exists
${\boldsymbol{x}}^{*}\in\mathbb{B}^{t}\setminus\\{\boldsymbol{0}\\}$ so such
polynomial $x_{1}^{*}p_{1}(X)+...+x_{t}^{*}p_{t}(X)$ has at least $\Omega$
roots. On the other hand, since the polynomials $p_{1}(X),\ldots,p_{t}(X)$
have degree at most $\ell+d-k-1$, the polynomial
$x_{1}^{*}p_{1}(X)+...+x_{t}^{*}p_{t}(X)$ has no more than $l+d-k-1$ roots and
so, the lemma follows. ∎

Putting Lemmas 9 and 10 together, we have that
$\sum_{i\in\mathcal{A}}b_{i}\geq b_{\min}$, where

$b_{\min}=\min_{b_{i}\in\\{0,1,\ldots,t\\}}\left\\{\sum_{i\in[d]}b_{i}:\sum_{i\in[d]}|\mathbb{B}|^{-b_{i}}\leq
L\right\\}\,.$ (24)

Here, $L$ denotes the quantity
$\frac{1}{|\mathbb{F}|}\Big{[}(|\mathbb{F}|-1)(\ell+d-k-1)+d\Big{]}$ (see
also, (7)).

If we relax $b_{i}$’s to take fractional values, the minimum is achieved when
$b_{1}=b_{2}=\ldots=b_{d}$ and we have the optimal value

$b_{\min}\geq
b^{*}_{\min}=d\log_{|\mathbb{B}|}\frac{|\mathbb{F}|d}{(|\mathbb{F}|-1)(\ell+d-k-1)+d}\,.$
(25)

As in [DM17], the exact solution can also be obtained by solving the integer
program (24). That is, we insist that $b_{i}\in\\{0,1,\ldots,t\\}$ for all
$i\in[d]$. More precisely, for the case where
$\log_{|\mathbb{B}|}\frac{d}{L}\notin\mathbb{Z}$, the following bound improves
(25). Specifically, we let $n_{0}$ be as defined in (6) and set

$b_{1}^{*}=\cdots=b_{n_{0}}^{*}=\left\lfloor\log_{|\mathbb{B}|}\frac{d}{L}\right\rfloor\quad\text{and}\quad
b_{n_{0}+1}^{*}=\cdots=b_{\ell+d-\ell}^{*}=\left\lceil\log_{|\mathbb{B}|}\frac{d}{L}\right\rceil\,.$
(26)

Then $b_{1}^{*},b_{2}^{*},\ldots,b_{d}^{*}$ is the optimal solution for (24).
Computing the optimal value, we complete the proof of Theorem 5.

##  5 Numerical results

Figure 2: Recovery bandwidth for sums of $\ell=4$ coded symbols of RS code
over $\textrm{GF}(2^{8})$ with $k=79$

In this section, we compare the evaluation bandwidth of our schemes with those
in previous work and lower bounds. Motivated by practical applications, we
consider two different scenarios. In the first one, we vary the number of
available nodes while the size $\ell$ of the weighted sum is fixed. In the
second one, we change $\ell$ while the number of available nodes is such that
it ensures the best bandwidth value.

  1. (a)

Varying Number of Available Nodes, $d$. Let us set $\ell=2$ and $k=79$.
Consider $\mathbb{F}=\textrm{GF}(2^{8})$ and $n=|\mathbb{F}|-\ell=254$ nodes.
Hence, the classical evaluation scheme can compute any weighted sum
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}$
of two coded symbols using any $k=79$ coded symbols, or equivalently,
downloading $632$ bits from any $79$ available nodes.

First, suppose that $d=141$ nodes are available. Then Schemes 1 and 2 are able
to evaluate
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}$
with $436$ and $423$ bits, respectively. In contrast, the schemes in Theorem
2(i) [MBW19] and Theorem 2(ii) [MBW19] have evaluation bandwidth $496$ and
$558$ bits, respectively, while the schemes in Theorem 3 [SW22] is unable to
improve the classical evaluation bandwidth. Suppose further that all $d=254$
nodes are available. Then the evaluation bandwidth of both Schemes 1 and 2 is
$410$ bits. In contrast, the schemes in Theorem 2(i) [MBW19] and Theorem 2(ii)
[MBW19] have evaluation bandwidth $496$ and $409$ bits, respectively, while
the schemes in Theorem 3 [SW22] cannot improve the classical evaluation
bandwidth. We do note that such an improvement of scheme in Theorem 2(ii)
[MBW19] over our Schemes 1 and 2 can be obtained only for the fields of small
size and high number of available nodes $d$. In Figure 1, we complete the
picture and provide the evaluation bandwidth for various schemes and lower
bounds for $79\leq d\leq 254$. We do note that during plotting the graph
hereinafter we take minimum overall bandwidth for a smaller or equal number of
available nodes. We also emphasize the significant gap between constructions
and lower bounds that grows with the increase of $d$.

Next, we consider the case of $\ell=4$ while the other settings remain the
same. Again, the classical evaluation bandwidth remains at 632 bits. Suppose
that all $d=252$ nodes are available. Then Schemes 1 and 2 are able to
evaluate
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathsf{S}}$
with $556$ and $535$ bits, respectively. In contrast, the scheme in Theorem
2(i) [MBW19] has evaluation bandwidth $600$ bits, while the schemes in Theorem
2(ii) [MBW19] and Theorem 3 [SW22] cannot improve the classical evaluation
bandwidth. In Figure 2, we complete the picture and provide the evaluation
bandwidth for various schemes and lower bounds for $79\leq d\leq 252$.

  2. (b)

Varying Size of Weighted Sum, $\ell$. Let us consider the case of
$\textrm{GF}(2^{32})$ and $k=2^{30}$ when our Schemes 1 and 2 and scheme from
Theorem 3 [SW22] can provide results that differ from the classical evaluation
scheme. The values of bandwidth in bits for different values of $\ell$ are
presented in Table 2. Note that we vary the number of code symbols
participated in the recovery process to obtain the best bandwidth value, but
such a number must be less than $q^{t}-\ell$ as $\ell$ symbols are assumed to
be erased. We see that for high values of $\ell$, the scheme from Theorem 3
[SW22] provides better results. In contrast, for small values of $\ell$,
results by Schemes 1 and 2 are better. Another interesting observation is that
the gap between constructions and lower bounds decreases with $\ell$. We do
note that such behavior also holds for the higher size of field and values of
$k$ when our Schemes 1 and 2 and the scheme from Theorem 3 [SW22] improves
over the classical evaluation scheme.

Scheme | $\ell=k$ | $\ell=\frac{k}{2}$ | $\ell=\frac{k}{2^{5}}$ | $\ell=\frac{k}{2^{12}}$ | $\ell=\frac{k}{2^{20}}$ | $\ell=\frac{k}{2^{28}}$
---|---|---|---|---|---|---
Scheme 1 | $32\cdot 2^{30}$ | $32\cdot 2^{30}$ | $32\cdot 2^{30}$ | $32\cdot 2^{30}$ | $\boldsymbol{17\cdot 2^{30}}$ | $8\cdot 2^{30}$
Scheme 2 | $32\cdot 2^{30}$ | $32\cdot 2^{30}$ | $31.9\cdot 2^{30}$ | $\boldsymbol{25.5\cdot 2^{30}}$ | $\boldsymbol{17\cdot 2^{30}}$ | $\boldsymbol{7.5\cdot 2^{30}}$
Theorem 2(i) [MBW19] | $32\cdot 2^{30}$ | $32\cdot 2^{30}$ | $32\cdot 2^{30}$ | $26.5\cdot 2^{30}$ | $19\cdot 2^{30}$ | $8.5\cdot 2^{30}$
Theorem 2(ii) [MBW19] | $32\cdot 2^{30}$ | $32\cdot 2^{30}$ | $32\cdot 2^{30}$ | $32\cdot 2^{30}$ | $32\cdot 2^{30}$ | $12\cdot 2^{30}$
Theorem 3 [SW22] | $32\cdot 2^{30}$ | $\boldsymbol{26\cdot 2^{30}}$ | $\boldsymbol{26\cdot 2^{30}}$ | $26\cdot 2^{30}$ | $26\cdot 2^{30}$ | $26\cdot 2^{30}$
Classical Repair Scheme | $32\cdot 2^{30}$ | $32\cdot 2^{30}$ | $32\cdot 2^{30}$ | $32\cdot 2^{30}$ | $32\cdot 2^{30}$ | $32\cdot 2^{30}$
Integer (Lower) Bound | $2$ | $1\cdot 2^{30}$ | $1.9\cdot 2^{30}$ | $2\cdot 2^{30}$ | $2\cdot 2^{30}$ | $2\cdot 2^{30}$
Fractional (Lower) Bound | $2$ | $1.6\cdot 2^{29}$ | $1.6\cdot 2^{30}$ | $1.7\cdot 2^{30}$ | $1.7\cdot 2^{30}$ | $1.7\cdot 2^{30}$
Table 2: Recovery bandwidth for Reed-Solomon code over $\textrm{GF}(2^{32})$
and $k=2^{30}$

##  6 Conclusion and open problems

We investigate the problem of efficiently computing linear combinations of
coded symbols. We characterize the evaluation process in terms of an
evaluation matrix for any $\mathbb{F}$-linear codes. For Reed-Solomon codes,
we propose explicit evaluation schemes as well as a lower bound on recovery
bandwidth. Several open questions remain, including:

  1. (A)

closing the gap between the lower bound on evaluation bandwidth and an
explicit construction;

  2. (B)

developing low-bandwidth evaluation schemes for other classes of functions,
for example, low-degree polynomials;

  3. (C)

extending the framework to other parameter regimes, for example, when $t$ is
extremely large [TYB19] or over prime fields [CT22];

  4. (D)

ensuring robustness, that is, ensuring correct evaluation in the presence of
erroneous nodes.

##  Appendix A Characterization of Evaluation Schemes using Evaluation
Matrices

In this appendix, we complete the proof of Theorem 7. In other words, we
demonstrate the necessary and sufficient conditions for the existence of low-
bandwidth evaluation schemes.

$[\Leftarrow]$ First, we prove the sufficient condition. That is, using an
evaluation matrix, we construct the functions
$g_{j}:\;\mathbb{F}\to\mathbb{B}^{b_{j}}$ for $j\in[d]$ such that
$\sum_{j\in[t]}b_{j}=b$. Hence, we obtain an
$(\boldsymbol{\kappa},\mathcal{C})$-weighted-sum evaluation scheme with
bandwidth $b$.

Now, using Condition (C1) in Definition 4, the $m$-th column
$\boldsymbol{M}[:,m]$ belongs to the dual code $\mathcal{C}^{\perp}$ for all
$m\in[t]$. This means that, for all
$\boldsymbol{c}=(c_{1},...,c_{d},c_{d+1},...,c_{\ell+d})\in\mathcal{C}$, we
have that

$\sum_{i\in[\ell+d]}c_{i}\boldsymbol{M}[i,m]=0\text{, or,
}\sum_{i\in[\ell]}c_{i}\boldsymbol{M}[i,m]=-\sum_{j\in[d]}c_{\ell+j}\boldsymbol{M}[\ell+j,m].$

Next, we multiply the equation by
$\Lambda\triangleq\prod_{i\in[\ell]}\kappa_{i}$. Then using Condition (C2), we
have that $\Lambda\boldsymbol{M}[i,m]=\kappa_{i}\boldsymbol{M}_{0}[1,m]$, and
so,

$\sum_{i\in[\ell]}\kappa_{i}c_{i}\boldsymbol{M}_{0}[m]=-\sum_{j\in[d]}\Lambda
c_{\ell+j}\boldsymbol{M}[\ell+j,m].$

Applying trace function to both sides of the equation above and utilizing its
linearity, we obtain

${\rm
Tr}\left(\left(\sum_{i\in[\ell]}\kappa_{i}c_{i}\right)\boldsymbol{M}_{0}[m]\right)=-{\rm
Tr}\left(\sum_{j\in[d]}\Lambda c_{\ell+j}\boldsymbol{M}[\ell+j,m]\right).$

For $j\in[d]$, we set $b_{j}\triangleq{\rm
rank}_{\mathbb{B}}(\boldsymbol{M}[\ell+j,:])$ and form a $\mathbb{B}$-basis
$\chi_{1}^{j},\ldots,\chi_{b_{j}}^{j}$ corresponding to the column space of
$\boldsymbol{M}[\ell+j,:]$. Then for $m\in[t]$, we can write $\Lambda
c_{\ell+j}\boldsymbol{M}[\ell+j,l]$ as a $\mathbb{B}$-linear combination of
elements in $\chi_{1}^{j},\ldots,\chi_{b_{j}}^{j}$. So, for some
$a_{j,1,m},\ldots,a_{j,b_{j},m}\in\mathbb{B}$, we have that

${\rm Tr}\Big{(}\Lambda
c_{\ell+j}\boldsymbol{M}[\ell+j,m]\Big{)}=a_{j,1,m}{\rm
Tr}\left(c_{\ell+j}\Lambda\chi_{1}^{j}\right)+\cdots+a_{j,b_{j},m}{\rm
Tr}\left(c_{\ell+j}\Lambda\chi_{b_{j}}^{j}\right).$ (27)

Now, for $j\in[d]$, we define the function

$g_{j}(x):\;\mathbb{F}\to\mathbb{B}^{b_{j}},\;x\mapsto\left({\rm
Tr}\left(x\Lambda\chi_{1}^{j}\right),\ldots,{\rm
Tr}\left(x\Lambda\chi_{b_{j}}^{j}\right)\right).$ (28)

Then we observe that for all $m\in[t]$, ${\rm Tr}(\Lambda
c_{\ell+j}\boldsymbol{M}[\ell+j,l])$ can be computed using $g_{j}(c_{\ell+j})$
and $a_{j,1,m},\ldots,a_{j,b_{j},m}$. Then using (27), we can compute ${\rm
Tr}\left(\left(\sum_{i\in[\ell]}\kappa_{i}c_{i}\right)\boldsymbol{M}_{0}[m]\right)$
for all $m\in[t]$.

Finally, from Condition (C2), we have that the rank of the matrix
$\boldsymbol{M}_{0}$ is $t$. In other words,
$\\{\boldsymbol{M}_{0}[m]:m\in[t]\\}$ forms a $\mathbb{B}$-basis. Then
Proposition 1 states there exists a trace-dual basis
$\\{\widetilde{\boldsymbol{M}_{0}}[m]:m\in[t]\\}$ and we have that

$\sum_{i\in[\ell]}\kappa_{i}c_{i}=\sum_{m\in[t]}{\rm
Tr}\left(\left(\sum_{i\in[\ell]}\kappa_{i}c_{i}\right)\boldsymbol{M}_{0}[m]\right)\widetilde{\boldsymbol{M}_{0}}[m].$

It remains to determine the evaluation bandwidth. This follows from the
definition of $g_{j}$ and Condition (C3). Specifically, since ${\rm
rank}_{\mathbb{B}}(\boldsymbol{M}[\ell+j,:])=b_{j}$ for $j\in[d]$, we have
that the evaluation bandwidth is $\sum_{j=1}^{d}b_{j}=b$.

$[\Rightarrow]$ Here, we prove the necessary condition. That is, we construct
the evaluation matrix $\boldsymbol{M}$ using the functions $g_{j}$. Let us
choose a basis $\\{u_{1},\ldots,u_{t}\\}$ of $\mathbb{F}$ over $\mathbb{B}$,
its trace-dual basis $\\{\tilde{u}_{1},\ldots,\tilde{u}_{t}\\}$ and write down
$\sum_{i\in[\ell]}\kappa_{i}c_{i}$ as a $\mathbb{B}$-linear combination of
elements of the latter one, namely

$\sum_{i\in[\ell]}\kappa_{i}c_{i}=\sum_{m=1}^{t}\zeta_{m}\tilde{u}_{m},$ (29)

where $\zeta_{m}\in\mathbb{B}$ for all $m\in[t]$. The fact that the considered
recovery scheme is $\mathbb{B}$-linear means that coefficients $\zeta_{m}$ are
$\mathbb{B}$-linear combinations of replies
$\\{g_{j}(c_{\ell+j}):\;j\in[d]\\}$. As a result, we have that

$\zeta_{m}=\sum_{j=1}^{d}\eta_{j}^{m}g_{j}(c_{\ell+j}),$

where $\eta_{j}^{m}\in\mathbb{B}$.

As all functions $g_{j}$ are $\mathbb{B}$-linear maps from $\mathbb{F}$ to
$\mathbb{B}^{b_{j}}$, we can define $g_{j}(c_{\ell+j})$ as follows

$g_{j}(c_{\ell+j})=\gamma_{1}^{j}\textrm{Tr}(\theta_{1}^{j}c_{\ell+j})+...+\gamma_{b_{j}}^{j}\textrm{Tr}(\theta_{b_{j}}^{j}c_{\ell+j}),$

where $\\{\theta_{1}^{j},\ldots,\theta_{b_{j}}^{j}\\}\in\mathbb{F}$ are
linearly independent as vectors over $\mathbb{B}$ and
$\\{\gamma_{1}^{j},\ldots,\gamma_{b_{j}}^{j}\\}\in\mathbb{B}$. Consequently,

$\displaystyle\zeta_{m}=\sum_{j=1}^{d}[\xi_{m,j,1}\textrm{Tr}(\theta_{1}^{j}c_{\ell+j})+...+\xi_{m,j,b_{j}}\textrm{Tr}(\theta_{b_{j}}^{j}c_{\ell+j})],$

where $\xi_{m,j,l}=\eta_{j}^{m}\gamma_{l}$ and $\xi_{m,j,l}\in\mathbb{B}$ for
all $l\in[t]$. Let us multiply both sides of (29) by $u_{m}$, where $m\in[t]$,
and apply trace function from $\mathbb{F}$ to $\mathbb{B}$. As a result we
have

$\textrm{Tr}\left(\sum_{i\in[\ell]}\kappa_{i}c_{i}u_{m}\right)=\zeta_{1}\textrm{Tr}(\tilde{u}_{1}u_{m})+...+\zeta_{m}\textrm{Tr}(\tilde{u}_{m}u_{m})+...+\zeta_{t}\textrm{Tr}(\tilde{u}_{t}u_{m}),$

but bases $\\{u_{1},\ldots,u_{t}\\}$ and
$\\{\tilde{u}_{1},\ldots,\tilde{u}_{t}\\}$ are trace-dual. Hence,

$\textrm{Tr}\left(\sum_{i\in[\ell]}\kappa_{i}c_{i}u_{m}\right)=\zeta_{m}=\sum_{j=1}^{d}\left(\xi_{m,j,1}\textrm{Tr}(\theta_{1}^{j}c_{\ell+j})+\cdots+\xi_{m,j,b_{j}}\textrm{Tr}(\theta_{b_{j}}^{j}c_{\ell+j})\right).$

Employing the fact that
$\\{\xi_{m,j,1},\ldots,\xi_{m,j,b_{j}}\\}\in\mathbb{B}$ we have

$\textrm{Tr}\left(\sum_{i\in[\ell]}\kappa_{i}c_{i}u_{m}\right)=\sum_{j=1}^{d}\textrm{Tr}\left((\xi_{m,j,1}\theta_{1}^{j}+...+\xi_{m,j,b_{j}}\theta_{b_{j}}^{j})c_{\ell+j}\right).$

We can define
$\mu_{m,j}=\xi_{m,j,1}\theta_{1}^{j}+\cdots+\xi_{m,j,b_{j}}\theta_{b_{j}}^{j}$,
where $\mu_{m,j}\in{\rm
span}_{\mathbb{B}}\\{\theta_{1}^{j},\ldots,\theta_{b_{j}}^{j}\\}$. Note that
we have chosen $\theta_{1}^{j},\ldots,\theta_{b_{j}}^{j}$ so that ${\rm
rank}_{\mathbb{B}}\\{\mu_{1,j},\ldots,\mu_{t,j}\\}=b_{j}$ as otherwise the
recovery scheme can be trivially improved by replacing
$\\{\theta_{1}^{j},\ldots,\theta_{b_{j}}^{j}\\}$ with basis of
$\\{\mu_{1,j},\ldots,\mu_{t,j}\\}$ over $\mathbb{B}$ that contains less than
$b_{j}$ elements. Consequently,

$\textrm{Tr}\left(\sum_{i\in[\ell]}\kappa_{i}c_{i}u_{m}\right)=\sum_{j=1}^{d}\textrm{Tr}(\mu_{m,j}c_{\ell+j}).$
(30)

Let $\\{\delta_{1},\ldots,\delta_{t}\\}$ be a basis of $\mathbb{F}$ over
$\mathbb{B}$ and $\\{\tilde{\delta}_{1},\ldots,\tilde{\delta}_{t}\\}$ be its
trace-dual basis. Due to the linearity of code $\mathcal{C}$ over
$\mathbb{F}$, (29) is also valid for codeword
$(\delta_{l}c_{1},\ldots,\delta_{l}c_{\ell+d})$. Hence for all $l\in[t]$ we
have

${\rm
Tr}\left(\left[\sum_{i\in[\ell]}\kappa_{i}c_{i}\right]u_{m}\delta_{l}\right)=\sum_{j\in[d]}{\rm
Tr}(\mu_{mj}c_{\ell+j}\delta_{l}).$

Multiplying both sides by $\tilde{\delta}_{l}$, we obtain

${\rm
Tr}\left(\left[\sum_{i\in[\ell]}\kappa_{i}c_{i}\right]u_{m}\delta_{l}\right)\tilde{\delta}_{l}=\sum_{j\in[d]}{\rm
Tr}(\mu_{mj}c_{\ell+j}\delta_{l})\tilde{\delta}_{l}.$

Taking sums over all $l\in[t]$, we have

$u_{m}\sum_{i\in[\ell]}\kappa_{i}c_{i}=\sum_{j\in[d]}\mu_{mj}c_{\ell+j}.$ (31)

According to (31), for all $m\in[t]$,
$\left(u_{m}\kappa_{1},\ldots,u_{m}\kappa_{\ell},-\mu_{m(\ell+1)},\ldots,-\mu_{m(\ell+d)}\right)$
are codewords of the dual code and we can form the columns of recovery matrix
from them. In such a case the latter has the following form

$\boldsymbol{M}=\left[\begin{matrix}\kappa_{1}u_{1}&\ldots&\kappa_{1}u_{t}\\\
\vdots&\ddots&\vdots\\\ \kappa_{\ell}u_{1}&\ldots&\kappa_{\ell}u_{t}\\\
-\mu_{1,\ell+1}&\ldots&-\mu_{t,\ell+1}\\\ \vdots&\ddots&\vdots\\\
-\mu_{1,\ell+d}&\ldots&-\mu_{t,\ell+d}\end{matrix}\right].$

It is clear that
$\frac{1}{\kappa_{1}}\boldsymbol{M}[1,:]=\cdots=\frac{1}{\kappa_{\ell}}\boldsymbol{M}[\ell,:]=[u_{1},\ldots,u_{t}]$
and has full rank over $\mathbb{B}$. Also, for $j\in[d]$, we have that ${\rm
rank}_{\mathbb{B}}\boldsymbol{M}[\ell+j,:]={\rm
rank}_{\mathbb{B}}(-\mu_{1,\ell+j},...-\mu_{t,\ell+j})=b_{j}$. Therefore, we
have $\sum_{j\in[d]}{\rm
rank}_{\mathbb{B}}\boldsymbol{M}[\ell+j,:]=\sum_{j\in[d]}b_{j}=b$.

## References

  * [BBD+22] Amit Berman, Sarit Buzaglo, Avner Dor, Yaron Shany, and Itzhak Tamo.  Repairing Reed-Solomon codes evaluated on subspaces.  IEEE Transactions on Information Theory, pages 1–12, 2022.
  * [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 Advances in Cryptology – CRYPTO 2016, pages 509–539, 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), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1–21:21, 2018.
  * [BKV+18] S. B. Balaji, M. Nikhil Krishnan, Myna Vajha, Vinayak Ramkumar, Birenjith Sasidharan, and P. Vijay Kumar.  Erasure coding for distributed storage: an overview.  Science China Information Sciences, 61(10):100301, 2018.
  * [CT22] Roni Con and Itzhak Tamo.  Nonlinear repair of Reed-Solomon codes.  IEEE Transactions on Information Theory, 68(8):5165–5177, 2022\.
  * [CV21] Ameera Chowdhury and Alexander Vardy.  Improved schemes for asymptotically optimal repair of mds codes.  IEEE Transactions on Information Theory, 67(8):5051–5068, 2021\.
  * [DD17] Iwan Duursma and Hoang Dau.  Low bandwidth repair of the RS(10,4) Reed-Solomon code.  In 2017 Information Theory and Applications Workshop (ITA), pages 1–10, 2017.
  * [DDK+21] Son Hoang Dau, Thi Xinh Dinh, Han Mao Kiah, Tran Thi Luong, and Olgica Milenkovic.  Repairing Reed-Solomon codes via subspace polynomials.  IEEE Transactions on Information Theory, 67(10):6395–6407, 2021\.
  * [DDKM18] Hoang Dau, Iwan M. Duursma, Han Mao Kiah, and Olgica Milenkovic.  Repairing Reed-Solomon codes with multiple erasures.  IEEE Transactions on Information Theory, 64(10):6567–6582, 2018\.
  * [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\.
  * [DLWX22] Jian Ding, Changlu Lin, Huaxiong Wang, and Chaoping Xing.  Communication efficient secret sharing with small share size.  IEEE Transactions on Information Theory, 68(1):659–669, 2022.
  * [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, 2017.
  * [DNNM+22] Thi Xinh Dinh, Luu Y Nhi Nguyen, Lakshmi J. Mohan, Serdar Boztas, Tran Thi Luong, and Son Hoang Dau.  Practical considerations in repairing reed-solomon codes.  In 2022 IEEE International Symposium on Information Theory (ISIT), pages 2607–2612, 2022.
  * [FIKW22] Ingerid Fosli, Yuval Ishai, Victor I. Kolobov, and Mary Wootters.  On the Download Rate of Homomorphic Secret Sharing.  In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 71:1–71:22, 2022.
  * [GW17] Venkatesan Guruswami and Mary Wootters.  Repairing Reed-Solomon codes.  IEEE Transactions on Information Theory, 63(9):5684–5698, 2017\.
  * [LBWZY21] Andreas Lenz, Rawad Bitar, Antonia Wachter-Zeh, and Eitan Yaakobi.  Function-correcting codes.  In 2021 IEEE International Symposium on Information Theory (ISIT), pages 1290–1295, 2021.
  * [LN96] Rudolf Lidl and Harald Niederreiter.  Finite Fields.  Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2nd edition, 1996.
  * [LO18] Shiqiu Liu and Frédérique Oggier.  An Overview of Coding for Distributed Storage Systems, pages 363–383.  Springer International Publishing, Cham, 2018.
  * [LWJ19] Weiqi Li, Zhiying Wang, and Hamid Jafarkhani.  On the sub-packetization size and the repair bandwidth of Reed-Solomon codes.  IEEE Transactions on Information Theory, 65(9):5484–5502, 2019\.
  * [MBW19] Jay Mardia, Burak Bartan, and Mary Wootters.  Repairing multiple failures for scalar mds codes.  IEEE Transactions on Information Theory, 65(5):2661–2672, 2019\.
  * [MDEH21] Roberto Assis Machado, Rafael G. L. D’Oliveira, Salim El Rouayheb, and Daniel Heinlein.  Field trace polynomial codes for secure distributed matrix multiplication.  In 2021 XVII International Symposium “Problems of Redundancy in Information and Control Systems” (REDUNDANCY), pages 188–193, 2021.
  * [MS77] F. J. MacWilliams and N. J. A. Sloane.  The Theory of Error Correcting Codes.  North-Holland Pub. Co., 1977.
  * [RS60] I. S. Reed and G. Solomon.  Polynomial codes over certain finite fields.  Journal of the Society for Industrial and Applied Mathematics, 8(2):300–304, 1960.
  * [RS21] Lawrence Roy and Jaspal Singh.  Large message homomorphic secret sharing from dcr and applications.  In Advances in Cryptology – CRYPTO 2021, pages 687–717, 2021.
  * [SW22] Noah Shutty and Mary Wootters.  Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data.  In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 117:1–117:19, 2022.
  * [TYB19] 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, 2019\.