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

AI summary

Overview

Research area: Quantum algorithms, coding theory, and cryptography — specifically local leakage resilience of secret sharing and the Optimal Polynomial Intersection problem.

Technical level: Advanced. The paper relies on Fourier analysis over finite fields, list-decoding and list-recovery of Reed–Solomon codes, Gowers norms, and quantum algorithm design. The high-level conclusions are accessible, but the proofs require coding-theory background.

Scope: This paper improves the rate threshold for one-bit local leakage resilience of Shamir secret sharing past the “one-half barrier” and gives improved quantum-algorithmic and existential results for worst-case Optimal Polynomial Intersection, using a shared Fourier-analytic reduction to list-decoding of Reed–Solomon codes.

What This Paper Is About

The paper studies two problems about low-degree polynomials over a prime field: Local Leakage Resilience (LLR) for Shamir secret sharing, and worst-case Optimal Polynomial Intersection (OPI). In LLR, a secret is encoded as (Q(0)) for a polynomial (Q) of degree less than (k), parties receive evaluations (Q(\alpha_i)), and the question is how much an adversary can learn about the secret from a few leaked bits from each share. In OPI, one is given lists (S_1,\dots,S_n\subset\mathbb{F}_p) and wants a degree-less-than-(k) polynomial satisfying (Q(\alpha_i)\in S_i) for as many indices as possible. The paper exploits a recent connection between the two problems to improve the best-known results for both.

Key Contributions

1. Breaking the one-half barrier for LLR. The paper proves that Shamir secret sharing over a prime field is one-bit locally leakage resilient whenever the rate (R=k/n) satisfies (R>1/2-\delta) for some absolute constant (\delta>0), and is (b)-bit locally leakage resilient for every fixed (b) and every fixed (R>1/2). This improves on the previous best bound (R>0.668) due to Kasser.

2. A quantum algorithm for worst-case OPI reaching the double semicircle law. For every rate (R), list density (\rho), and (\varepsilon>0), a (\operatorname{poly}(n,\log p))-time quantum algorithm finds a solution with satisfaction ratio at least (\mathsf{SCL}_\rho(R)-\varepsilon), and when (R+\rho>1) it finds a perfect solution satisfying every constraint.

3. New existential results for OPI. The paper establishes near-optimal OPI discrepancy for Reed–Solomon codes when (R>1/2), when (R>1/2-\delta) and (\rho\ge 1/2-\delta), or when (R+\rho>1). It also proves an existential bound (V_\rho(R)=1-(1-2\rho)(1-2R)) that exceeds the double semicircle law for (R\in(\rho,1/2]).

4. A quantum-versus-classical separation for OPI. The paper adapts the Yamakawa–Zhandry hardness result from folded Reed–Solomon codes to ordinary OPI, giving an unconditional separation between quantum and classical hardness relative to a membership oracle over large fields.

Main Findings

• LLR threshold (Theorem 1.3): Every Shamir secret sharing scheme with rate (R) over a prime field is (b)-bit locally leakage resilient for every fixed (b) and every fixed (R>1/2); it is one-bit locally leakage resilient whenever (R>1/2-\delta) for some absolute constant (\delta>0). The value of (\delta) is not reported explicitly.

• Worst-case leakage: The LLR result applies to arbitrary leakage functions, not only balanced ones. The paper also shows that the balanced case is the hardest, in the sense that a sufficient rate threshold proved for the balanced case holds for arbitrary biases. The previous balanced-case result of [20] gave (R^*\le 0.58) (reported as (0.579) for balanced one-bit leakages in the technical discussion).

• Quantum OPI algorithm (Theorem 1.8): A quantum algorithm with (\operatorname{poly}(n,\log p)) running time, given coherent membership-oracle access to lists with (|S_i|\ge \rho p), outputs with high probability a polynomial with satisfaction ratio at least (\mathsf{SCL}_\rho(R)-\varepsilon). If (R+\rho>1), it outputs a polynomial satisfying all constraints.

• Near-optimal OPI discrepancy (Theorem 1.10): Every Reed–Solomon code of rate (R) over a prime field has near-optimal OPI discrepancy for every instance with (|S_i|\ge \rho p), provided at least one of the following holds: (R>1/2); (R>1/2-\delta) and (\rho\ge 1/2-\delta); or (R+\rho>1). In these regimes a perfect solution exists for sufficiently large (n) and constant (R,\rho>0).

• Existential bound beyond the double semicircle law (Theorem 1.11): For fixed (\rho\in(0,1/2)), every Reed–Solomon code of fixed rate (R\in(\rho,1/2]) over a prime field with (p\ge n) admits a solution with satisfaction ratio at least (V_\rho(R)-\varepsilon), where (V_\rho(R)=1-(1-2\rho)(1-2R)). The improvement over the double semicircle law is [ V_\rho(R)-\mathsf{SCL}_\rho(R)=\bigl(\sqrt{\rho(1-R)}-\sqrt{(1-\rho)R}\bigr)^2>0. ]

• Classical hardness (Theorem 1.12): There is a random ensemble of balanced OPI instances of length (n) with rate (1/\operatorname{polylog}(n)) over prime fields with quasipolynomial (p=\exp(\operatorname{polylog}(n))). A polynomial-time quantum algorithm finds a perfect solution with all but negligible probability, while every randomized classical algorithm making polynomially many membership-oracle queries has negligible probability of outputting a solution with satisfaction ratio (1/2+\Omega(1/\log\log n)). The failure probabilities are (e^{-\Omega((\log n)^2)}), and by tuning parameters one can obtain (e^{-\Omega(n^c)}) for a constant (c>0) at the cost of lower rate and classical satisfaction ratio control.

• OPI is at least as hard as LLR (Theorem 1.13): If every coset (v+C) has near-optimal OPI discrepancy for every (v\in\mathbb{F}p^n), then the leakage transcript distributions (L_v) and (L{v'}) are close in total variation for every (v,v'). LLR is thus a restriction of near-optimal OPI discrepancy to constant-shift cosets (s\mathbf{1}+C). A converse does not hold and can fail by up to an exponential factor, even for fixed-rate

Authors’ 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 $\mathbb{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), \ldots, Q(α_n)$, for distinct non-zero evaluation points $α_i \in \mathbb{F}_p$. In OPI, one is given input list $S_1, \ldots, S_n \subset \mathbb{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 \geq 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 \geq 0.668$ (Kasser, 2025). For OPI, we give a quantum algorithm that finds a polynomial $Q(X)$ that agrees with at least a $\mathsf{SCL}_ρ(R)-\varepsilon$ fraction of the lists in expectation, for every fixed $\varepsilon>0$, where $\mathsf{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.