Private Repair of a Single Erasure in Reed-Solomon Codes

Abstract

We investigate the problem of privately recovering a single erasure for Reed-Solomon codes with low communication bandwidths. For an $[n,k{]}_{q^{\ell }}$ code with $n-k\ge 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.

Full version of the paper accepted for the 2024 IEEE International Symposium on Information Theory (ISIT)