Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection
New bounds break Shamir secret sharing's one-half local-leakage barrier and improve optimal polynomial intersection.
The paper improves local leakage resilience for Shamir secret sharing and worst-case optimal polynomial intersection over prime-order fields. It shows a constant delta exists such that when the rate R equals k/n is at least one-half minus delta, Shamir sharing is one-bit locally leakage resilient, the first result past the one-half barrier and better than the prior R at least 0.668 bound. For polynomial intersection it gives a quantum algorithm that, in expectation, matches at least the semicircle-law fraction minus epsilon of the input lists. It also adapts the Yamakawa-Zhandry hardness result to OPI, yielding an unconditional quantum-classical separation relative to a membership oracle over large fields.
- Proves one-bit local leakage resilience when rate R is at least one-half minus delta.
- Improves the prior Shamir threshold of R at least 0.668.
- Quantum algorithm approaches semicircle-law agreement for polynomial intersection.
- Adapts Yamakawa-Zhandry hardness to separate quantum and classical OPI.
From the original article
1 min read at arxiv.orgWe 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 $\mathbb{F}_p$.
By Yihang Sun · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.