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

arXiv:2610.12357 · quant-ph, cs.CR, cs.DM, cs.IT, math.IT · Submitted 2026-10-08 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection".

Mira: Detailed Research Summary:

Kai: First, who's behind it and why it matters.

Title and authors: Kai: So what is the actual story of the paper "Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection"? It’s about how this link between LLR and OPI allows them to push past previous limits for both problems at the same time.

Mira: They introduce two main tools, which are these Fourier proxies called FOPI for intersection and FLLR for leakage resilience. They use the dual list recovery of Reed–Solomon codes as their main engine to establish these bounds.

Lev: So in plain terms, what does that coding theory stuff actually achieve here? Is it just a complicated way to prove something we already knew about error correction?

Kai: It’s more than that. This framework lets them prove better thresholds for LLR for Shamir sharing when the rate R is above one-half. And on the OPI side, they provide new algorithmic guarantees showing a quantum algorithm can find a polynomial satisfying at least a fraction SCL rho(R) - epsilon of the input lists in expectation.

Mira: And they also showed that for certain conditions, specifically when R + rho > one the algorithm guarantees finding a solution Q that satisfies every single constraint with high probability.

Lev: That sounds like a strong guarantee on the intersection side. But what about the limitations? What stops this from being a perfect solver for all instances of OPI?

Kai: The paper itself points out some things, Lev. They establish quantitative bounds for OPI discrepancy depending on R and rho. For instance, they show near-optimal OPI discrepancy is strictly harder than one-bit LLR. That means any future improvement in solving intersection problems will automatically improve LLR for Shamir sharing.

Mira: It really shows how tight the relationship is between these two fields, using those Fourier proxies and dual list recovery to give us concrete numbers on when things are feasible and what the limits are when they aren't.

Lev: So, it’s about using existing coding theory techniques to get better performance metrics for both problems at once, even though the setup is different.

The paper's summary: Kai: Let’s look specifically at what improvements the authors claim in this paper. They are focused on pushing past the existing barriers in both LLR and OPI.

Mira: On the Local Leakage Resilience side, they broke what they called the "one-half barrier." They proved that Shamir secret sharing is one-bit resilient whenever R = k/n at least one/two - delta, where delta is a fixed positive constant, which beats previous best known results like requiring R at least zero point six six eight.

Lev: That improvement, moving the threshold from that higher number down to something close to one-half, that makes a difference in terms of practical scheme design for secret sharing systems, right?

Kai: It does. And on the OPI side, they have these quantum algorithmic guarantees. They show a quantum algorithm can find a polynomial satisfying at least SCL rho(R) - epsilon of the input lists in expectation.

Mira: And they also showed that for specific conditions, like when R + rho > one the algorithm guarantees finding a solution Q that satisfies every single constraint with high probability.

Lev: That’s a strong guarantee on the intersection side. But what about the limitations? What stops this from being a perfect solver for all instances of OPI?

Kai: The paper itself mentions that they establish an informal relationship between the Fourier proxies, saying that sqrt FLLR(v, v') is bounded by a maximum of FOPI(u). This suggests a direct implication: near-optimal OPI discrepancy in OPI is strictly harder than one-bit LLR.

Mira: It’s a tight relationship between the two fields, mediated by those Fourier proxies and dual list recovery. The work gives us concrete numbers on when things are feasible and what the limits are when they aren't.

Lev: To put it simply, this paper shows how to use existing coding theory techniques to get better performance metrics for both problems at once.

The paper's improvements: Kai: So to wrap up, the paper "Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection" is essentially using a Fourier analytic bridge to simultaneously improve both LLR for secret sharing and the worst-case optimal polynomial intersection.

Mira: The main implication is that we now have much tighter quantitative bounds on how much information leaks in secret sharing, pushing past the one-half barrier, and we have new quantum algorithmic results for OPI that give us stronger existential guarantees.

Lev: For hardware realization, these results suggest a pathway to designing more resilient cryptographic primitives based on these new resilience thresholds for LLR when you operate above one/two - delta.

Kai: And on the OPI side, the work establishes a direct link: near-optimal discrepancy in OPI is strictly harder than one-bit LLR. This means any future improvement in solving OPI will automatically improve LLR for Shamir sharing.

Mira: It’s a tight relationship between the two fields, mediated by those Fourier proxies and dual list recovery. The work gives us concrete numbers on when things are feasible and what the limits are when they aren't.

Lev: To put it simply, this paper shows how to use existing coding theory techniques to get better performance metrics for both problems at once.

Kai: That’s the essence of what Sun and Wootters did here with "Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection." We’re going to take a quick break.

Conclusion: Kai: So to wrap up, Sun and Wootters have shown how linking Local Leakage Resilience for Shamir Secret Sharing to Worst-Case Optimal Polynomial Intersection lets them improve both areas at once using a common Fourier analytic framework.

Mira: The main implication is that we get much tighter quantitative bounds on what information leaks in secret sharing, pushing past the one-half barrier, and they also have new quantum algorithmic results for OPI that give us stronger existential guarantees.

Lev: For hardware realization, these results suggest a pathway to designing more resilient cryptographic primitives based on those new resilience thresholds for LLR when you operate above one/two - delta.

Kai: And on the OPI side, the work establishes a direct link: near-optimal discrepancy in OPI is strictly harder than one-bit LLR. This means any future improvement in solving OPI will automatically improve LLR for Shamir sharing.

Mira: It’s a tight relationship between these two fields, mediated by those Fourier proxies and dual list recovery. The work gives us concrete numbers on when things are feasible and what the limits are when they aren't.

Lev: To put it simply, this paper shows how to use existing coding theory techniques to get better performance metrics for both problems at once.

Kai: That’s the essence of what Sun and Wootters did here with "Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection." We're going to take a quick break.

Stanford University

quant-ph, cs.CR, cs.DM, cs.IT, math.IT

Submitted: 2026-10-08

Updated: 2026-10-08

Comments: 70 pages, 3 figures

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: Detailed Research Summary: Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection This research paper presents a significant advancement in the

Key concepts

Local Leakage Resilience (LLR)
This measures how much information about a secret polynomial's value at zero can be gained when only small leaks occur from evaluations at other points. The paper shows that Shamir sharing is one-bit resilient if the rate is above a specific threshold.
Optimal Polynomial Intersection (OPI)
OPI seeks to find a polynomial whose evaluations at given points fall into specified input lists, maximizing satisfied constraints. The work provides quantum algorithms that can find near-optimal solutions efficiently for certain conditions on the problem's parameters.
Fourier Proxies
These are mathematical tools, FOPI and FLLR, used to approximate the hard OPI and LLR problems. By bounding these proxies using dual list recovery of Reed–Solomon codes, the authors establish exponential decay bounds that drive their main results.

Terminology

Summary

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

This research paper presents a significant advancement in the field of cryptographic primitives by establishing deep connections between two seemingly disparate problems: Local Leakage Resilience (LLR) for Shamir secret sharing schemes and worst-case Optimal Polynomial Intersection (OPI). The authors leverage a novel, common Fourier-analytic framework to simultaneously improve the state-of-the-art results for both problems, effectively breaking established barriers in their respective areas.

Core Problems and Motivation

The paper focuses on two central challenges concerning polynomials Q(X) of degree less than k over a prime field F p:

  1. Local Leakage Resilience (LLR) for Shamir Secret Sharing: This problem investigates how much information about the secret polynomial, specifically its value at zero (Q(0)), can be inferred when only a few bits are leaked from evaluations of Q at distinct, non-zero points alpha i in F p.

  2. Worst-Case Optimal Polynomial Intersection (OPI): This problem asks for the construction of a polynomial Q(X) of degree less than k such that its evaluations at a given set of points alpha i fall into specified input lists S i, maximizing the number of satisfied constraints.

The motivation stems from recent findings (Sun, Wootters 2026) suggesting a strong link between these two problems, which the authors exploit to achieve joint improvements.

Key Technical Framework: The Fourier-Analytic Bridge

The central innovation is the development of a common Fourier-analytic framework that reduces both OPI and LLR to the problem of list-decoding and list-recovery of a relevant dual code. This framework utilizes two key tools:

  1. Fourier Proxies:

  • FOPI(v) for OPI problems.

  • FLLR(v, v') for LLR problems. These proxies are bounded by positive relaxations of the respective problems (F + OPI and F + LLR).

  1. Dual List-Recovery: The framework relies heavily on leveraging recent breakthroughs in the list-decoding and list-recovery of Reed–Solomon codes (Brakensiek et al., 2026; Jeronimo, 2026; Dao, Kominers, Thaler, 2026) to establish bounds for both LLR and OPI when the rate R exceeds 1/2.

  2. Weighted Fourier Thresholding: A crucial mechanism is Lemma 1.15, which bounds the Fourier proxies by relating them to weighted sums over the dual code. This lemma is instrumental in establishing exponential decay for these proxies when codes possess good list-recovery properties, a result that underpins the core improvements.

Main Results and Breakthroughs

The paper yields several landmark results across both problem domains:

  1. Improvements in Local Leakage Resilience (LLR)

The authors successfully break the long-standing one-half barrier for LLR.

  • Theorem 1.3 (LLR Threshold): They prove that every Shamir secret sharing scheme with rate R is one- b-bit locally leakage resilient for any fixed b and any fixed R > 1/2. Crucially, they establish a more refined threshold: Shamir sharing is one-bit LLR whenever the rate R = k/n at least 1/2 - delta, where delta is an absolute positive constant. This surpasses previous best results that required rates as high as R at least 0.668 (Kasser, 2025).
  1. Quantum Algorithms for Optimal Polynomial Intersection (OPI)

The authors provide powerful quantum algorithmic guarantees for finding near-optimal solutions to OPI:

  • Theorem 1.8 (Quantum Algorithms): They present a quantum algorithm that finds a polynomial Q(X) satisfying at least a fraction SCL rho(R) - epsilon of the input lists in expectation, for any fixed epsilon > 0.

  • The proof relies on Lemma 6.2, which shows that measuring the DQI state phi yields an expected satisfaction ratio of SCL rho(alpha) + o(1).

  • For instances where R + rho > 1, the algorithm guarantees finding a solution Q that satisfies every constraint (s(Q)=1) with high probability.

  • The complexity is polynomial in (n, p) running time.

  1. Near-Optimal OPI Discrepancy and Hardness

The work establishes strong quantitative bounds for OPI discrepancy and its relationship to LLR:

  • Theorem 1.10 (Near-Optimal Discrepancy): They provide conditions under which a Reed–Solomon code achieves near-optimal OPI discrepancy, depending on the rate R and list density rho. The condition for achieving this near-optimality is met if at least one of three criteria holds: R > 1/2, R > 1/2 - delta and rho at least 1/2 - delta, or R + rho > 1.

  • Theorem 3.6 (Hardness Separation): The analysis demonstrates that the Fourier proxy bounds imply that near-optimal OPI discrepancy is strictly harder than one-bit LLR. This establishes a direct implication: any future improvement in near-optimal OPI discrepancy will necessarily yield improvements in LLR for Shamir sharing.

  • Theorem 1.13 (Informal Hardness): They show an informal relationship between the Fourier proxies (FLLR and FOPI) and the OPI problem, suggesting that sqrt FLLR(v, v') is bounded by a maximum of FOPI(u).

  • Theorem 1.12 (Classical vs. Quantum Hardness): They establish an unconditional separation between the classical and quantum hardness of OPI relative to a membership oracle.

Summary of Methodology Flow

The paper follows a rigorous six-step approach:

  1. Fourier Proxies Definition: Defining FOPI(v) and FLLR(v, v').

  2. Rate > 1/2 Results: Proving results above the 1/2 barrier using dual list-decoding and recovery of Reed–Solomon codes.

  3. Crossing the Barrier: Developing techniques to operate effectively at and beyond the R=1/2 threshold (Step 3).

  4. Near-Optimal Solutions: Proving near-optimal OPI solutions using weighted Fourier thresholding (Step 4 and part of Step 5).

  5. Classical Hardness Analysis: Analyzing the classical hardness of OPI relative to a membership oracle (Step 6).

In conclusion, this paper is a high-impact contribution that uses sophisticated Fourier analysis and established coding theory techniques to simultaneously achieve significant quantitative improvements in both LLR for Shamir sharing and the algorithmic guarantees for worst-case polynomial intersection. The central theme is the powerful duality between these two problems mediated by dual list recovery.

Improvements for AI systems

  1. Improved Local Leakage Resilience for Shamir Secret Sharing: The system can now guarantee that "one-bit LLR whenever R > 1/2 − δ, for some absolute constant δ > 0," which is an improvement over previous results requiring a much higher rate like R ≥ 0.668.

  2. Enhanced Optimal Polynomial Intersection (OPI) Solver: The system can now find a polynomial Q(X) that agrees with at least a SCLρ(R/2 − ε fraction of the lists in expectation, improving upon previous algorithmic results and existential bounds.

  3. Quantum Advantage for OPI Relative to Membership Oracle: The system can solve the folded OPI problem perfectly with all but negligible probability relative to a membership oracle, which is essential for breaking the classical hardness barrier in certain parameter regimes.

  4. Near-Optimal OPI Discrepancy Guarantee: For any fixed rate R and density ρ, the system can find a polynomial Q with satisfaction ratio at least SCLρ(R) − ε, providing a stronger existential guarantee than previously known algorithmic results.

  5. Arbitrary Bias Handling in OPI: The system can achieve near-optimal OPI discrepancy even when input lists have unequal densities ρi ≥ ρ, by using algorithmic subsampling to reduce the general case to the case where ∣Si∣ all have the same density.

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 F 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 in F p. In OPI, one is given input list S 1,, S n F p, and wants to find a polynomial Q(X) of degree less than k so that Q(α i) in 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 at least 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 at least 0.668 (Kasser, 2025). For OPI, we give a quantum algorithm that finds a polynomial Q(X) that agrees with at least a ρ(R)-epsilon fraction of the lists in expectation, for every fixed epsilon>0, where ρ is the 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.

Sources

Related papers