License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.117
URN: urn:nbn:de:0030-drops-157130
URL: https://drops.dagstuhl.de/opus/volltexte/2022/15713/
Go to the corresponding LIPIcs Volume Portal

Shutty, Noah ; Wootters, Mary

Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data

pdf-format:
LIPIcs-ITCS-2022-117.pdf (0.8 MB)

Abstract

We study the problem of efficiently computing on encoded data. More specifically, we study the question of low-bandwidth computation of functions F:F^k → F of some data đ± ∈ F^k, given access to an encoding 𝐜 ∈ Fⁿ of đ± under an error correcting code. In our model - relevant in distributed storage, distributed computation and secret sharing - each symbol of 𝐜 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(đ±). 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 Δ > 0 and let 𝒞: F^k → Fⁿ be a full-length Reed-Solomon code of rate 1 - Δ over a field F with constant characteristic. For any Îł ∈ [0, Δ), our scheme can compute any linear function F(đ±) given access to any (1 - Îł)-fraction of the symbols of 𝒞(đ±), with download bandwidth O(n/(Δ - Îł)) bits. In contrast, the naive scheme that involves reconstructing the data đ± and then computing F(đ±) uses Θ(n log n) bits. Our scheme has applications in distributed storage, coded computation, and homomorphic secret sharing.

BibTeX - Entry

@InProceedings{shutty_et_al:LIPIcs.ITCS.2022.117,
  author =	{Shutty, Noah and Wootters, Mary},
  title =	{{Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{117:1--117:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15713},
  URN =		{urn:nbn:de:0030-drops-157130},
  doi =		{10.4230/LIPIcs.ITCS.2022.117},
  annote =	{Keywords: Reed-Solomon Codes, Regenerating Codes, Coded Computation}
}

Keywords: Reed-Solomon Codes, Regenerating Codes, Coded Computation
Collection: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Issue Date: 2022
Date of publication: 25.01.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI