Private Repair of a Single Erasure in Reed-Solomon Codes
Stanislav Kruglik, Han Mao Kiah, Son Hoang Dau, Eitan Yaakobi · 2024
We investigate the problem of privately recovering a single erasure for Reed-Solomon codes with low communication bandwidths. For an$[n,k]_{\mathbb{F}_{q^{\ell}}}$code with$n-k\geq q^{m}+t-1$, we construct a repair scheme that allows a client to recover an arbitrary codeword symbol without leaking its index to any set of$t$colluding helper nodes at a repair bandwidth of$(n-1)(\ell-m)$sub-symbols in$\mathbb{F}_{q}$. When$t=1$, this reduces to the bandwidth of existing repair schemes based on subspace polynomials. We prove the optimality of the proposed scheme when$n=q^{\ell}$under a reasonable assumption about the schemes being used. Our private repair scheme can also be transformed into a private retrieval scheme for data encoded by Reed-Solomon codes.