Repairing Reed-Solomon Codes over Prime Fields via Exponential Sums
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929234124996608 |
|---|---|
| author | Con, Roni Shutty, Noah Tamo, Itzhak Wootters, Mary |
| author_facet | Con, Roni Shutty, Noah Tamo, Itzhak Wootters, Mary |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_02358 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Repairing Reed-Solomon Codes over Prime Fields via Exponential Sums Con, Roni Shutty, Noah Tamo, Itzhak Wootters, Mary Information Theory 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. |
| title | Repairing Reed-Solomon Codes over Prime Fields via Exponential Sums |
| topic | Information Theory |
| url | https://arxiv.org/abs/2402.02358 |