⚛️ quantum physics

Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection

This paper breaks the long-standing "one-half barrier" for Local Leakage Resilience in Shamir secret sharing and presents improved quantum algorithms and hardness results for the Worst-Case Optimal Polynomial Intersection problem by leveraging a recent connection between the two.

Original authors: Yihang Sun, Mary Wootters

Published 2026-10-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yihang Sun, Mary Wootters

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of digital security, keeping a secret safe often involves breaking it into pieces. Imagine a treasure chest that can only be opened if enough people bring their unique keys to the table. This is the essence of a secret sharing scheme, a mathematical method used to protect sensitive information like encryption keys or passwords. The most famous version of this, known as Shamir's secret sharing, works by turning a secret into a hidden pattern, or a curve, and then handing out different points along that curve to various people. As long as a specific number of people combine their points, they can reconstruct the original curve and reveal the secret. If fewer people try, the secret remains completely hidden, like a puzzle with missing pieces.

However, a new threat has emerged in the form of "local leakage." In the real world, computers are not perfect vaults; they can be tricked into leaking tiny, seemingly harmless fragments of data. An attacker might not get the whole key, but perhaps they can steal just one or two bits of information from each person's share. For years, mathematicians wondered if this tiny leakage could eventually add up to reveal the whole secret. They suspected there was a tipping point, a specific ratio of information held by the participants versus the total secret, below which the system would inevitably collapse. For a long time, the best mathematical proofs suggested that as long as the participants held more than two-thirds of the necessary information, the system was safe. But a persistent barrier remained: no one could prove the system was secure if the participants held less than half the information, a limit that felt like an unbreakable wall in the math.

A team of researchers has now pushed through that wall, proving that Shamir's secret sharing is far more resilient than previously thought. They demonstrated that even when the participants hold significantly less than half the total information required to reconstruct the secret, the system remains secure against one-bit leaks. This means that even if an attacker manages to steal a single bit of data from every single participant, the secret itself remains safe, provided the participants hold just a tiny bit more than half the necessary information. This result shatters the long-standing "one-half barrier" that had limited our understanding of these security systems for years.

The path to this discovery involved tackling a second, seemingly unrelated puzzle called the "Optimal Polynomial Intersection." This problem asks a different question: given a set of lists of numbers, can you find a single, simple curve that passes through at least one number from each list? While this sounds like a game of pattern matching, it is deeply connected to the security of the secret sharing scheme. The researchers realized that solving this curve-finding problem efficiently was the key to understanding the security of the secret sharing. They found that if you can prove a certain type of curve exists that fits the data, you can also prove the secret is safe from leakage.

To solve these problems, the team developed a new mathematical framework that treats these security questions as problems of decoding and recovering information. They leveraged recent breakthroughs in the field of error-correcting codes, which are the mathematical tools used to fix corrupted data in everything from space probes to QR codes. By applying these advanced tools, they were able to show that the "noise" created by the leaked bits is not enough to break the secret. They proved that for a wide range of scenarios, the amount of information an attacker can glean is so small that it is effectively zero, mathematically speaking.

The researchers also explored the power of quantum computers in this arena. They showed that while classical computers struggle to find the perfect curve that satisfies all the conditions in the "Optimal Polynomial Intersection" problem, a quantum computer can find a solution that satisfies almost all of them, and in some cases, all of them. This creates a clear separation between what classical machines can do and what quantum machines can achieve. Specifically, they constructed scenarios where a quantum algorithm could find a perfect solution almost instantly, while any classical algorithm would need an impossible amount of time to find even a decent approximation. This highlights a fundamental difference in how these two types of computers process information, suggesting that the future of cryptography may depend on understanding these quantum advantages.

The work does not just offer a theoretical improvement; it provides a concrete roadmap for building more secure systems. By breaking the one-half barrier, the researchers have shown that we can design secret sharing schemes that are secure even with fewer participants or less redundancy than previously believed possible. This is crucial for real-world applications where resources are limited, or where the cost of storing extra data is high. The findings confirm that the mathematical foundations of our digital security are stronger than we thought, capable of withstanding attacks that were once considered potentially devastating.

Ultimately, this research bridges the gap between abstract mathematics and practical security. It takes a complex problem about leaking bits and turns it into a solvable puzzle about curves and lists. By proving that the secret remains safe even when the pieces are few and the leaks are small, the team has reinforced the trust we place in digital systems. Their work suggests that the tools we use to protect our data are more robust than the barriers we thought existed, offering a new level of confidence in the face of evolving threats. The results stand as a testament to the power of combining different areas of mathematics to solve problems that seemed unsolvable, pushing the boundaries of what we know about keeping secrets safe in a digital age.

Technical Summary: Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection

1. Problem Statement

This paper addresses two distinct but interconnected problems concerning polynomials $Q(X)$ of degree less than $k$ over a prime-order finite field $\mathbb{F}_p$ :

Local Leakage Resilience (LLR) for Shamir Secret Sharing: The problem asks how much information an adversary can learn about the secret $Q(0)$ given a limited number of bits (specifically one bit) leaked from each share $Q(\alpha_i)$ . The goal is to determine the minimum rate $R = k/n$ required to guarantee that the secret remains secure (i.e., the total variation distance between transcript distributions for different secrets is negligible). Prior to this work, the best known bound required $R \geq 0.668$ , and a "barrier" at $R = 1/2$ was suspected to be insurmountable for worst-case leakage functions.
Worst-Case Optimal Polynomial Intersection (OPI): Given input lists $S_1, \dots, S_n \subset \mathbb{F}_p$ and evaluation points $\alpha_i$ , the goal is to find a polynomial $Q(X)$ of degree $< k$ that satisfies $Q(\alpha_i) \in S_i$ for as many indices $i$ as possible. The problem investigates the existence of such polynomials (existential results) and the efficiency of finding them (algorithmic results), particularly in the context of quantum algorithms. Previous work established that quantum algorithms could achieve a satisfaction ratio related to the "semicircle law" $SCL_\rho(R/2)$ , while classical algorithms were limited to lower ratios.

2. Methodology and Technical Framework

The authors develop a unified Fourier-analytic framework that reduces both LLR and OPI to the problem of list-decoding and list-recovery of the dual code (specifically, Generalized Reed-Solomon codes).

Key Technical Components:

Fourier Proxies: The authors define "Fourier proxies" to bound the quantities of interest. For OPI, they bound the discrepancy between the actual intersection size and the expected size for random lists. For LLR, they bound the total variation distance between transcript distributions. These proxies are expressed as sums over the dual code $C^\perp$ involving Fourier coefficients of the leakage functions or input sets.
Weighted Fourier Thresholding (Lemma 1.15): A central technical contribution is a lemma that bounds weighted sums over the dual code. By leveraging recent breakthroughs in the list-recovery of Reed-Solomon codes (Brakensiek et al., 2026; Jeronimo, 2026; Dao et al., 2026), the authors show that these sums are exponentially small when the rate $R > 1/2$ .
Crossing the $1/2$ Barrier: To handle rates $R \leq 1/2$ , the authors cannot rely solely on "phase-forgotten" proxies (which ignore the complex phases of Fourier coefficients). Instead, they utilize Gowers norms (specifically the $U^3$ norm) and the generalized von Neumann inequality to exploit phase cancellations in the original Fourier sums. This allows them to prove resilience and discrepancy bounds even when $R$ is slightly below $1/2$ .
Quantum Algorithms (DQI): For algorithmic results, the paper utilizes the Decoded Quantum Interferometry (DQI) framework. The authors improve the analysis of the quantum state $|\phi_\ell\rangle$ proposed in previous work. By combining the improved existential bounds on OPI discrepancy with efficient list-decoding algorithms for the dual code, they demonstrate how to efficiently prepare quantum states that yield high-satisfaction solutions.
Hardness Separation: To establish a quantum advantage, the authors adapt the hardness results of Yamakawa and Zhandry (2024) regarding folded Reed-Solomon codes. They construct two types of OPI ensembles (sparse and balanced) that encode the Yamakawa-Zhandry source problem, proving that while quantum algorithms can solve these instances efficiently, classical algorithms require super-polynomial queries.

3. Key Contributions and Results

A. Local Leakage Resilience (LLR)

The paper breaks the long-standing "one-half barrier" for Shamir secret sharing:

Theorem 1.3: The authors prove that Shamir secret sharing is one-bit locally leakage resilient for any rate $R > 1/2 - \delta$ (for some absolute constant $\delta > 0$ ).
This improves upon the previous best result requiring $R \geq 0.668$ (Kasser, 2025).
The result holds for arbitrary leakage functions (worst-case), not just balanced ones. The authors further show that the balanced case is the hardest, implying their threshold applies generally.
For any fixed number of leaked bits $b$ , the scheme is resilient for all $R > 1/2$ .

B. Optimal Polynomial Intersection (OPI)

The paper provides significant improvements in both existential and algorithmic guarantees:

Near-Optimal Discrepancy (Theorem 1.10): The authors prove that Reed-Solomon codes have near-optimal OPI discrepancy (implying the existence of perfect solutions) under three conditions:
1. $R > 1/2$ .
2. $R > 1/2 - \delta$ and input density $\rho \geq 1/2 - \delta$ .
3. $R + \rho > 1$ .
Quantum Algorithm (Theorem 1.8): They present a quantum algorithm that finds a solution with satisfaction ratio at least $SCL_\rho(R) - \epsilon$ $S C L_{ρ} (R) - ϵ$ (the "double semicircle law"), improving over previous bounds of $SCL_\rho(R/2)$ $S C L_{ρ} (R /2)$ .
- Crucially, if $R + \rho > 1$ , the algorithm finds a perfect solution (satisfying all constraints) with high probability.
Existential Improvement (Theorem 1.11): For rates $R \in (\rho, 1/2]$ , the authors prove the existence of solutions with satisfaction ratio $V_\rho(R) = 1 - (1-2\rho)(1-2R)$ , which strictly exceeds the double semicircle law guarantee. This result is existential and does not currently have an efficient algorithmic counterpart.

C. Quantum Advantage

Theorem 1.12: The paper establishes an unconditional separation between quantum and classical hardness for OPI relative to a membership oracle.
They construct a random ensemble of balanced OPI instances over quasipolynomial fields where a polynomial-time quantum algorithm finds a perfect solution, while any classical algorithm making polynomially many queries has negligible probability of finding a solution with satisfaction ratio better than $1/2 + \Omega(1/\log \log n)$ .

4. Significance and Claims

The paper claims to be the first to break the $1/2$ barrier for worst-case local leakage resilience in Shamir secret sharing, a threshold that had been a major open problem. By unifying LLR and OPI through a Fourier-analytic lens and leveraging recent breakthroughs in Reed-Solomon list-recovery, the authors achieve:

Tighter Security Bounds: Lowering the required rate for secure secret sharing against local leakage.
Improved Quantum Algorithms: Pushing the achievable satisfaction ratio for OPI from $R/2$ to $R$ (the double semicircle law) and enabling perfect solutions in high-density regimes.
Hardness Separations: Providing a concrete example where quantum algorithms offer a super-polynomial advantage over classical algorithms for a natural algebraic problem (OPI) relative to membership oracles, extending the scope of Yamakawa-Zhandry's results from folded codes to scalar codes.

The authors emphasize that their techniques rely on the "common Fourier-analytic framework" reducing these problems to dual list-recovery, allowing them to import recent combinatorial breakthroughs to achieve these improvements. They explicitly state that the existential improvements beyond the double semicircle law (Theorem 1.11) are not currently known to be efficiently computable.