论文标题
明确的低带宽评估方案，用于芦苇 - 固体编码符号的加权总和
Explicit Low-Bandwidth Evaluation Schemes for Weighted Sums of Reed-Solomon-Coded Symbols
论文作者
论文摘要
由分布式存储，分布式计算和同构秘密共享中的应用程序的激励，我们研究了用于计算编码符号的线性组合的沟通效率方案。具体而言，我们设计了低频带的方案，该方案评估了codeWord $ \ pmb {c} \ in \ mathbb {f}^n $中的$ \ ell $编码符号的加权总和，当我们可以访问$ \ pmb {c} $中的其余组件的$ d $时。 正式地，假设$ \ mathbb {f} $是$ \ mathbb {b} $的字段扩展名$ t $。令$ \ pmb {c} $为尺寸$ k $的芦苇 - 固体代码中的代码字，我们的任务是计算$ \ ell $编码符号的加权总和。在本文中，对于一些$ s <t $，我们提供了一个明确的方案，可以通过$ \ mathbb {b} $中的$ d（t-s）$ subsymbols从$ d $ nodes中下载$ d（t-s）$ subsymbols，每当$ d $ nodes中，每当$ d \ geq \ geq \ ge \ ell | \ ell | \ ell | \ ell | \ elrbb {b} |^s- \ ell+ell+ell+k $。在许多情况下，我们的计划表现优于文献中的先前计划。 此外，我们提供了一般线性代码的评估方案的表征。然后，在芦苇 - 固体代码的特殊情况下，我们使用此表征来得出评估带宽的下限。
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 $\pmb{c}\in\mathbb{F}^n$, when we are given access to $d$ of the remaining components in $\pmb{c}$. Formally, suppose that $\mathbb{F}$ is a field extension of $\mathbb{B}$ of degree $t$. Let $\pmb{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.
