Explicit Low-Bandwidth Evaluation Schemes for Weighted Sums of Reed-Solomon-Coded Symbols
Han Mao Kiah, Wilton Kim, Stanislav Kruglik, San Ling, Huaxiong Wang · IEEE Transactions on Information Theory · 2024
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 ℓ coded symbols in a codewordc∈ Fn, when we are given access todof the remaining components inc. Formally, suppose that F is a field extension of B of degreet. Letcbe a codeword in a Reed-Solomon code of dimensionkand our task is to compute the weighted sum of ℓ coded symbols. In this paper, for somest, we provide an explicit scheme that performs this task by downloadingd(t-s) sub-symbols in B fromdavailable nodes, wheneverd≥ ℓ|B|s-ℓ +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.