Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection
Abstract
We study two problems: Local Leakage Resilience (LLR) for Shamir secret sharing, and worst-case Optimal Polynomial Intersection (OPI). Both problems concern polynomials Q(X) of degree less than k, over a prime-order finite field 𝔽p. In LLR for Shamir secret sharing, one asks how much one can learn about Q(0) given a few bits leaked from each of Q(α1), …, Q(αn), for distinct non-zero evaluation points αi ∈ 𝔽p. In OPI, one is given input list S1, …, Sn ⊂ 𝔽p, and wants to find a polynomial Q(X) of degree less than k so that Q(αi) ∈ Si for as many i as possible. Leveraging recent connection between these two problems due to (Sun, Wootters 2026), we improve the state-of-the-art for both problems. For LLR, we show that there is some constant δ> 0 so that, as long as R := k/n ≥ 1/2 − δ, Shamir secret-sharing is one-bit locally leakage resilient (meaning that one can learn only a negligible amount about Q(0)). This is the first result to break the so-called "one-half barrier" for LLR, and improves over the previous best known result, requiring R ≥ 0.668 (Kasser, 2025). For OPI, we give a quantum algorithm that finds a polynomial Q(X) that agrees with at least a SCLρ(R)−ε fraction of the lists in expectation, for every fixed ε>0, where SCLρ is the \emph{semicircle law} of (Jordan et al., 2025). This improves previous algorithmic (and existential) results of (Jo, 2026) and (Horinaga, Yamakawa, 2026). We also give further improved existential results. We also adapt the hardness result of (Yamakawa, Zhandry, 2024) to apply to OPI (rather than a folded version); over large fields, this gives an unconditional separation between the quantum and classical hardness of OPI relative to a membership oracle.
Related
- Improved Index and Intersection bounds for Min-Max Geodesics
- Cryptanalysis of a Class of Ideal Secret Sharing Schemes Based on the CRT for Polynomial Rings
- An improved bound for the intersection of two longest cycles in k-connected graphs
- An Index-Graded Virtual Intersection Polynomial for Oriented Virtual Knots
- Improved computation of polynomial roots over number fields when using complex embeddings
BibTeX
@misc{sun2026improved,
title = {{Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection}},
author = {Yihang Sun and Mary Wootters},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.12357},
eprint = {2610.12357},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.12357},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection
AU - Yihang Sun
AU - Mary Wootters
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.12357
UR - https://arxiv.org/abs/2610.12357
AB - We study two problems: Local Leakage Resilience (LLR) for Shamir secret sharing, and worst-case Optimal Polynomial Intersection (OPI). Both problems concern polynomials Q(X) of degree less than k, over a prime-order finite field 𝔽_p. In LLR for Shamir secret sharing, one asks how much one can learn about Q(0) given a few bits leaked from each of Q(α_1), …, Q(α_n), for distinct non-zero evaluation points α_i ∈ 𝔽_p. In OPI, one is given input list S_1, …, S_n ⊂ 𝔽_p, and wants to find a polynomial Q(X) of degree less than k so that Q(α_i) ∈ S_i for as many i as possible. Leveraging recent connection between these two problems due to (Sun, Wootters 2026), we improve the state-of-the-art for both problems. For LLR, we show that there is some constant δ> 0 so that, as long as R := k/n ≥ 1/2 − δ, Shamir secret-sharing is one-bit locally leakage resilient (meaning that one can learn only a negligible amount about Q(0)). This is the first result to break the so-called "one-half barrier" for LLR, and improves over the previous best known result, requiring R ≥ 0.668 (Kasser, 2025). For OPI, we give a quantum algorithm that finds a polynomial Q(X) that agrees with at least a SCL_ρ(R)−ε fraction of the lists in expectation, for every fixed ε>0, where SCL_ρ is the \emph{semicircle law} of (Jordan et al., 2025). This improves previous algorithmic (and existential) results of (Jo, 2026) and (Horinaga, Yamakawa, 2026). We also give further improved existential results. We also adapt the hardness result of (Yamakawa, Zhandry, 2024) to apply to OPI (rather than a folded version); over large fields, this gives an unconditional separation between the quantum and classical hardness of OPI relative to a membership oracle.
ER -