Repairing Reed-Solomon Codes over Prime Fields via Exponential Sums
<|reference_start|>Repairing Reed-Solomon Codes over Prime Fields via Exponential Sums: This paper presents two repair schemes for low-rate Reed-Solomon (RS) codes over prime fields that can repair any node by downloading a constant number of bits from each surviving node. The total bandwidth resulting from these schemes is greater than that incurred during trivial repair; however, this is particularly relevant in the context of leakage-resilient secret sharing. In that framework, our results provide attacks showing that $k$-out-of-$n$ Shamir's Secret Sharing over prime fields for small $k$ is not leakage-resilient, even when the parties leak only a constant number of bits. To the best of our knowledge, these are the first such attacks.   Our results are derived from a novel connection between exponential sums and the repair of RS codes. Specifically, we establish that non-trivial bounds on certain exponential sums imply the existence of explicit nonlinear repair schemes for RS codes over prime fields.<|reference_end|>
@article{con2024repairing,
    title={Repairing Reed-Solomon Codes over Prime Fields via Exponential Sums},
    author={Roni Con, Noah Shutty, Itzhak Tamo, Mary Wootters},
    journal={arXiv preprint arXiv:2402.02358},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.02358},
    primaryClass={cs.IT math.IT}
}