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

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 $\mathrm{\ell }$ coded symbols in a codeword $c\in {\mathbb{F}}^n$, when we are given access to $d$ of the remaining components in $c$. Formally, suppose that $\mathbb{F}$ is a field extension of $\mathbb{B}$ of degree $t$. Let $c$ be a codeword in a Reed-Solomon code of dimension $k$ and our task is to compute the weighted sum of $\mathrm{\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\ge \mathrm{\ell }\mathrm{\mid }\mathbb{B}{\mathrm{\mid }}^s-\mathrm{\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.