We study two problems: Local Leakage Resilience (LLR) for Shamir secret sharing, and worst-case Optimal Polynomial Intersection (OPI), over a prime field $\mathbb{F}_p$. For a polynomial $Q(X)$ of degree less than $k$, LLR for Shamir secret sharing asks what a few leaked bits from each of the $n$ shares $Q(α_1), \ldots, Q(α_n)$ reveal about $Q(0)$. Given (worst-case) input lists $S_1, \ldots, S_n \subset \mathbb{F}_p$, OPI seeks a polynomial $Q(X)$ so that $Q(α_i) \in S_i$ for as many $i$ as possible. Leveraging recent connections 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 Shamir secret-sharing is one-bit LLR (only a negligible amount about $Q(0)$ is learned) whenever $R := k/n \geq 1/2 - δ$. 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, 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 for all OPI instances; and when the evaluation points $α_i$ are chosen at random, for every rate $R > 0$ we show that, with high probability, for worst-case $S_i$ there exists \emph{perfect} solution. Finally, we adapt the hardness result of (Yamakawa, Zhandry, 2024) to apply to OPI (rather than a folded version); this gives an unconditional separation between the quantum and classical hardness of OPI relative to a membership oracle.
AI Summary
The paper studies local leakage resilience (LLR) of Shamir secret sharing and worst-case optimal polynomial intersection (OPI): finding a degree-$<k$ polynomial satisfying as many constraints $Q(\alpha_i)\in S_i\subseteq\mathbb F_p$ as possible. It connects both through Fourier bounds on Reed–Solomon codes and their cosets.
Over prime fields and arbitrary evaluation points, Shamir sharing is proved $b$-bit LLR for every fixed $b$ and rate $R=k/n>1/2$, and one-bit LLR for $R>1/2-\delta$ for an absolute $\delta>0$. The previous general one-bit threshold was $0.668$. For lists of density at least $\rho$, a polynomial-time quantum algorithm achieves satisfaction $\mathsf{SCL}_\rho(R)-\varepsilon$, where $\mathsf{SCL}_\rho(a)=(\sqrt{\rho(1-a)}+\sqrt{(1-\rho)a})^2$ up to $a=1-\rho$, then equals one. It finds perfect solutions when $R+\rho>1$. Stronger existential guarantees include near-expected perfect-solution counts for $R>1/2$, and, with random evaluation points and $\log p=n^{\Omega(1)}$, for every fixed positive $R,\rho$ simultaneously over adversarial lists.
The proofs combine dual-code list recovery, phase-sensitive Fourier analysis using Gowers norms to cross the half-rate barrier, and refined decoded-quantum-interferometry analysis and state preparation. A separate encoding of the folded Yamakawa–Zhandry problem gives an unconditional membership-oracle separation: quantum algorithms solve certain balanced instances perfectly, while polynomial-query classical algorithms cannot exceed $1/2+\Omega(1/\log\log n)$ satisfaction.
The quantum algorithms require coherent membership access when lists are too large to input explicitly. The separation uses constructed, vanishing-rate instances over quasipolynomial fields; it does not establish classical hardness for explicit-input OPI. Some existential guarantees lack matching efficient algorithms. Similar LLR results were obtained independently and concurrently.
No sign of AI-generated textAI use disclosed
Outside of the aforementioned contributions, AI was used only for copyediting and proof checking
Error found: The abstract omits the assumption log p=n^{Ω(1)} required by Theorem random-opi for its random-evaluation-point perfect-solution guarantee.
The abstract and formal leakage model use polynomial-degree conventions differing by one while both denote the rate by k/n, an asymptotically harmless notation mismatch.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Comments
82 pages, 3 figures; v2 adds near-optimal OPI discrepancy for random Reed-Solomon codes
We study two problems: Local Leakage Resilience (LLR) for Shamir secret sharing, and worst-case Optimal Polynomial Intersection (OPI), over a prime field Fp. For a polynomial Q(X) of degree less than k, LLR for Shamir secret sharing asks what a few leaked bits from each of the n shares Q(α1),…,Q(αn) reveal about Q(0). Given (worst-case) input lists S1,…,Sn⊂Fp, OPI seeks a polynomial Q(X) so that Q(αi)∈Si for as many i as possible. Leveraging recent connections 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 Shamir secret-sharing is one-bit LLR (only a negligible amount about Q(0) is learned) whenever R:=k/n≥1/2−δ. 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, 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 for all OPI instances; and when the evaluation points αi are chosen at random, for every rate R>0 we show that, with high probability, for worst-case Si there exists \emph{perfect} solution. Finally, we adapt the hardness result of (Yamakawa, Zhandry, 2024) to apply to OPI (rather than a folded version); this gives an unconditional separation between the quantum and classical hardness of OPI relative to a membership oracle.
The paper studies local leakage resilience (LLR) of Shamir secret sharing and worst-case optimal polynomial intersection (OPI): finding a degree-<k polynomial satisfying as many constraints Q(αi)∈Si⊆Fp as possible. It connects both through Fourier bounds on Reed–Solomon codes and their cosets.
Over prime fields and arbitrary evaluation points, Shamir sharing is proved b-bit LLR for every fixed b and rate R=k/n>1/2, and one-bit LLR for R>1/2−δ for an absolute δ>0. The previous general one-bit threshold was 0.668. For lists of density at least ρ, a polynomial-time quantum algorithm achieves satisfaction SCLρ(R)−ε, where SCLρ(a)=(ρ(1−a)+(1−ρ)a)2 up to a=1−ρ, then equals one. It finds perfect solutions when R+ρ>1. Stronger existential guarantees include near-expected perfect-solution counts for R>1/2, and, with random evaluation points and logp=nΩ(1), for every fixed positive R,ρ simultaneously over adversarial lists.
The proofs combine dual-code list recovery, phase-sensitive Fourier analysis using Gowers norms to cross the half-rate barrier, and refined decoded-quantum-interferometry analysis and state preparation. A separate encoding of the folded Yamakawa–Zhandry problem gives an unconditional membership-oracle separation: quantum algorithms solve certain balanced instances perfectly, while polynomial-query classical algorithms cannot exceed 1/2+Ω(1/loglogn) satisfaction.
The quantum algorithms require coherent membership access when lists are too large to input explicitly. The separation uses constructed, vanishing-rate instances over quasipolynomial fields; it does not establish classical hardness for explicit-input OPI. Some existential guarantees lack matching efficient algorithms. Similar LLR results were obtained independently and concurrently.
The Optimal Polynomial Intersection (OPI) problem is the following: Given sets S1,…,Sm⊆F and evaluation points a1,…,am∈F, find a polynomial Q∈F[x] of degree less than n so that Q(ai)∈Si for as many i∈{1,2,…,m} as possible. Decoded Quantum Interferometry (DQI) is a quantum algorithm that efficiently returns good solutions to the problem, even on worst-case instances (Jordan et. al., 2025). The quality of the solutions returned follows a semicircle law, which outperforms known efficient classical algorithms. But does DQI obtain the best possible solutions? That is, are there solutions better than the semicircle law for worst-case OPI instances? Surprisingly, before this work, the best existential results coincide with (and follow from) the best algorithmic results.
In this work, we show that there are better solutions for worst-case OPI instances over prime fields. In particular, DQI and the semicircle law are not optimal. For example, when the lists Si have size ρp for ρ∼1/2, our results imply the existence of a solution that asymptotically beats the semicircle law whenever n/m≥0.6225, and we show that an asymptotically perfect solution exists whenever n/m≥0.7496. Our results generalize to Max-LINSAT problems derived from any Maximum Distance Separable (MDS) code, and to any ρ∈(0,1). The key insight to our improvement is a connection to local leakage resilience of secret sharing schemes. Along the way, we recover several re-proofs of the existence of solutions achieving the semicircle law.
We initiate the study of quantum leakage resilience of unmodified Shamir secret sharing over prime fields. A well-studied leakage model for Shamir's secret sharing classically is single-bit local leakage from each share. We consider its quantum analogue where, for each party, a local leakage channel takes as input the party's share and outputs a leaked qubit. Without preshared entanglement, we show that the distinguishing advantage is 2−Ω(n) when the threshold rate t/n=τ exceeds τ⋆≈0.73339 by a fixed positive margin.
More generally, we allow disjoint entangled blocks of any fixed maximum size where there is no entanglement between different blocks or with the adversary, and each block emits at most a fixed number of qubits. Security holds when the threshold rate is high enough (sufficiently close to one). We then allow a specified set of devices to share entanglement with the adversary. We show that security holds even when a linear number of devices (αn for small α>0) share entanglement with each other and with the adversary for a large enough threshold rate.
As a complementary negative result, we also show that even classical single-bit leakage makes Shamir scheme insecure if we allow arbitrarily large entanglement between the leakage devices. A GHZ state shared by exactly t leakage devices makes even classical one-bit leakage insecure, without any entanglement with the adversary. In this attack, each participating device emits only one classical bit, and their joint parity distinguishes any chosen pair of secrets with a constant advantage. Thus, for fixed threshold rates above τ⋆, the maximum number of devices that may share arbitrary entanglement with one another and with the adversary while preserving security is linear in n up to constant factors, although the optimal support fraction remains open.
Optimal Polynomial Intersection (OPI) is a structured optimization problem for which Decoded Quantum Interferometry (DQI) attains a satisfaction guarantee governed by the semicircle law. Sun and Wootters recently showed that, for balanced OPI over prime fields, a Fourier-defined distribution Pu gives a strict worst-case improvement from limiting rate 0.6225 onward and asymptotically perfect solutions from rate 0.7496 onward, and asked whether Pu can be sampled efficiently. We answer this question for Reed--Solomon OPI parameters satisfying their exponent condition strictly below the dual Johnson radius. Under coherent membership-oracle access, we give a bounded-error polynomial-time quantum sampler for Pu. The ideal circuit samples Pu exactly conditioned on success, while a finite-precision implementation achieves any prescribed inverse-polynomial total-variation error. Consequently, every fixed limiting rate 0.6225≤r<1 admits a strict worst-case improvement over the DQI semicircle value, and every limiting rate r≥3/4 admits solutions of satisfaction 1−o(1) with high probability. The algorithm coherently sums the amplitudes of all low-weight errors in each syndrome class using deterministic complete list decoding. Complete Reed--Solomon list decoding and the Sun--Wootters denominator estimate make the list size and postselection overhead polynomial. In concurrent and independent work, Horinaga and Yamakawa obtain worst-case OPI algorithms over prime-power fields and exact satisfaction at every fixed rate strictly above 3/4.
The Optimal Polynomial Intersection (OPI) problem asks us to find a low-degree polynomial over a finite field whose values lie in prescribed subsets on as many given inputs as possible. Decoded quantum interferometry (DQI) gives a quantum algorithm for OPI in parameter regimes beyond those achieved by the best known classical heuristics. Follow-up works improve the parameter regimes, but their analyses are limited to average-case settings. Recently, Sun and Wootters showed that, even in the worst case, OPI has a solution in a larger parameter regime than the one covered by DQI. However, they left open whether one can design a quantum algorithm that solves OPI in the worst-case beyond the DQI regime.
We give such a quantum algorithm. As a byproduct, we also improve the existential bound of Sun and Wootters in certain parameter regimes. In particular, when each subset contains roughly half of the field elements, our algorithm finds a solution with satisfaction rate s=1 whenever the rate satisfies R>0.75. This matches the previous average-case bound, whereas DQI cannot achieve s=1 unless R=1. Our existential bound guarantees the existence of a solution when R>0.7158, improving over the previous threshold R>0.7495. More generally, our existential results extend to the Max-LINSAT problem with respect to arbitrary maximum distance separable (MDS) codes. The corresponding algorithmic results apply only to MDS codes whose dual admits an efficient list decoder. Our results are obtained through a novel application of a Brascamp--Lieb-type inequality in the MDS setting, which may have further applications.
Recently, Jordan et al. (Nature, 2025) introduced a novel quantum-algorithmic technique called Decoded Quantum Interferometry (DQI) for solving specific combinatorial optimization problems associated with classical codes. They presented a constraint-satisfaction problem called Optimal Polynomial Intersection (OPI) and showed that, for this problem, a DQI algorithm running in polynomial time can satisfy a larger fraction of constraints than any known polynomial-time classical algorithm.
In this work, we propose several improvements to the DQI algorithm, including sidestepping the quadratic-time Dicke state preparation. Given random access to the input, we show how these improvements result in a nearly linear-time DQI algorithm for the OPI problem. Concurrently and independently with this work, Khattar et al. (arXiv:2510:10967) also construct a nearly linear-time DQI algorithm for OPI using slightly different techniques.
In recent years, a particularly interesting line of research has focused on designing quantum algorithms for code and lattice problems inspired by Regev's reduction. The core idea is to use a decoder for a given code to find short codewords in its dual. For example, Jordan et al. demonstrated how structured codes can be used in this framework to exhibit some quantum advantage. In particular, they showed how the classical decodability of Reed-Solomon codes can be leveraged to solve the Optimal Polynomial Intersection (OPI) problem quantumly. This approach was further improved by Chailloux and Tillich using stronger soft decoders, though their analysis was restricted to a specific setting of OPI. In this work, we reconcile these two approaches. We build on a recent formulation of the reduction by Chailloux and Hermouet in the lattice-based setting, which we rewrite in the language of codes. With this reduction, we show that the results of Jordan et al. can be recovered under Bernoulli noise models, simplifying the analysis. This characterization then allows us to integrate the stronger soft decoders of Chailloux and Tillich into the OPI framework, yielding improved algorithms.