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

• The paper considers LLR for Shamir secret sharing and OPI.Source: §1 · p. 3
• The two problems were connected by [SW26].Source: §1 · p. 3
• The paper improves LLR rate thresholds and obtains improved existential and algorithmic results for OPI.Source: §1 · p. 3

1.1 Local Leakage Resilience

• In Shamir sharing, the secret is the polynomial’s value at zero; parties receive evaluations at distinct nonzero points, and LLR asks whether local share leakage preserves its security.Source: §1.1 · p. 3
• The preceding best one-bit LLR threshold was R* ≤ 0.668, while earlier work identified R* = 1/2 as a natural barrier.Source: §1.1 · p. 3
• Every fixed b-bit leakage function is resilient when R > 1/2.Source: §1.1 · p. 4
• R > 1/2 − δ suffices for one-bit LLR, the first result to break the one-half barrier, improving the prior R > 0.668 threshold.Source: §1.1 · p. 4
• The result applies to arbitrary leakage functions, and the sufficient rate threshold for the balanced case also holds for arbitrary biases.Source: §1.1 · p. 4

1.2 Optimal Polynomial Intersection

• OPI asks for a degree-less-than-k polynomial maximizing the fraction of evaluation points α_i where Q(α_i) lies in S_i.The paper motivates discrepancy by comparing the number of codewords in the product of the lists with the expected count for random lists.Source: §1.2 · p. 4
• SCLρ(R) is the satisfaction ratio achieved by a quantum algorithm for worst-case OPI, with a perfect solution when R + ρ > 1.The algorithm runs in polynomial time in n and log p; for balanced lists, the results also give efficient perfect solutions for R > 1/2.Source: §1.2 · pp. 5–6
• Near-optimal OPI discrepancy guarantees perfect solutions when R > 1/2 and ρ ≥ 1/2 − δ, or when R + ρ > 1.For constant positive R and ρ and sufficiently large n, these conditions imply existence of a perfect solution.Source: §1.2 · p. 6
• For ρ < R ≤ 1/2, every sufficiently large instance has a solution with satisfaction at least Vρ(R) − ε, improving on SCLρ(R).This existential guarantee applies to Reed–Solomon codes over prime fields with p ≥ n.Source: §1.2 · p. 6
• For balanced instances of rate 1/polylog(n) over quasipolynomial-size prime fields, quantum algorithms find perfect solutions while randomized classical polynomial-query algorithms have negligible probability of reaching satisfaction 1/2 + Ω(1/log log n).The separation is relative to membership oracles for the input lists.Source: §1.2 · pp. 8–9

1.3 The relationship between LLR and OPI

• Similar Fourier proxies bound OPI discrepancy and the distance between LLR transcript distributions, connecting the two problems [SW26].The paper formalizes this connection and develops it beyond the earlier use of LLR ideas for OPI.Source: §1.3 · p. 9
• If every constant-shift coset s1 + C has near-optimal OPI discrepancy for the leakage-defined lists, then C is one-bit locally leakage resilient.The condition must hold for all secrets s and all leakage transcripts z.Source: §1.3 · p. 9
• The implication has no converse: for fixed-rate GRS codes, OPI can be harder than LLR by up to an exponential factor.The paper notes that a converse to the OPI-to-LLR implication can fail by this amount.Source: §1.3 · p. 9
• LLR is a restriction of near-optimal OPI discrepancy to constant-shift cosets, so improvements to that discrepancy imply improvements for Shamir sharing.The formal relationship also applies when near-optimal discrepancy holds for every coset v + C.Source: §1.3 · p. 9

Step 1: Define Fourier Proxies

• Shared Fourier proxies bound OPI discrepancy and LLR transcript distance; the paper also proves that OPI is harder than LLR, including at the proxy level.For LLR, the proxy is recentered and renormalized to handle arbitrary biases ρ_i.Source: §1.4 · p. 10, Step 1: Define Fourier Proxies · p. 12

1.4 Technical Overview

• Above rate 1/2, both problems reduce to dual list-recovery; weighted Fourier thresholding supplies a reusable bound for LLR and OPI proxies.For Shamir sharing, list-recovery of the dual generalized Reed–Solomon code yields the LLR result; the weighted-sum bound also supports later steps.Source: §1.4 · p. 10, Step 2: Above rate 1/2, LLR and OPI… · p. 13
• When ρ + R > 1, truncation extends the framework to exact perfect OPI solutions and an efficient algorithm for finding them.The overview says near-perfect solutions already exist in this regime, while truncation enables the exact-solution result.Source: §1.4 · p. 10
• Two scalar encodings transform the folded Reed–Solomon hard instance of Yamakawa–Zhandry into an unfolded instance, with either sparse lists at arbitrary target rate or balanced lists at vanishing target rate.The balanced-list encoding uses a consistency argument.Source: §1.4 · p. 11
• Below rate 1/2, retaining Fourier phases and using Gowers norms exploits phase cancellations to control LLR and OPI proxies.The balanced-case argument uses U3 norms; arbitrary-bias LLR and arbitrary-density OPI extensions use additional techniques.Source: Step 3: Crossing the rate-1/2 barrier · pp. 13–14

Step 4: Partial OPI satisfaction

• An efficient quantum algorithm finds OPI solutions with expected satisfaction ratio about SCL_ρ(R), while existential guarantees improve beyond that law for ρ < R ≤ 1/2.The algorithmic result combines efficient preparation of the DQI state with list-recovery bounds; the improved existential guarantee is non-algorithmic.Source: Step 4: Partial OPI satisfaction · pp. 14–15
• For ρ < R ≤ 1/2, puncturing and conditioning yield the existential satisfaction guarantee V_ρ(R), which is non-algorithmic.The method punctures to t coordinates; optimizing ℓ and t gives V_ρ(R).Source: Step 4: Partial OPI satisfaction · p. 15
• When ρ + R > 1, the authors establish near-optimal OPI discrepancy, implying a perfect solution, and show how to find one efficiently.For the existential result, truncating H to Hℓ gives a good proxy on the dense instance’s lists and restricts the needed shells to t ≤ min{n, 2ℓ + 1} ≤ 2k − Ω(n).Source: Step 5: OPI when ρ + R > 1 · p. 16
• Measuring |φℓ⟩ for ℓ ∼ (1 − ρ)n gives each perfect solution a lower-bounded sampling probability, so polynomially many repetitions find one.The perfect states are abundant by the preceding existential argument.Source: Step 5: OPI when ρ + R > 1 · p. 16

Step 6: Quantum Advantage of OPI

• Building on Yamakawa-Zhandry, scalar-level encoding reduces folded-instance solving to unfolded OPI, preserving quantum perfect solving and classical difficulty.A single large-field scalar encodes all source coordinates; one list simulates the source oracles, while the other n − 1 lists encode perfect solving.Source: Step 6: Quantum Advantage of OPI · pp. 16–17
• The scalar-level construction permits arbitrary target Reed–Solomon rate but leaves the duplicated list sparse; balanced parity tests remove sparsity at vanishing rate by enforcing consistency through code dimension.The sparse list arises because a random source message passes all m independent constraints with probability 2^-m.Source: Step 6: Quantum Advantage of OPI · pp. 16–17

1.5.1 Local Leakage Resilience for Shamir’s Scheme

• Worst-case 1-bit LLR thresholds improved from R > 0.907 to 0.668, while balanced leakage required only R > 0.58.Intermediate worst-case thresholds were 0.8675, 0.85, 0.78, and 0.69.Source: §1.5.1 · p. 17
• Near-half LLR results also existed for sufficiently small leakage-function classes with random evaluation points, while other work restricted leakage to physical bits [MNPCW+21].The paper focuses instead on worst-case families of leakage functions.Source: §1.5.1 · p. 17, §1.5.2 · p. 17

1.5.2 Optimal Polynomial Intersection

• OPI relates to Reed–Solomon list-recovery [BCDZ25] [BCP+26] [Jer26] and proposed cryptographic hardness assumptions [NP99,BN00,NP06]; classical lattice attacks broke one such assumption [BN00].Those lattice attacks do not seem to work in the OPI parameter regime.Source: §1.5.2 · pp. 17–18
• For polynomial field sizes, prior quantum algorithms reached SCLρ(R/2), while translated worst-case lists supported guarantees under R > 0.75 [Cha25].The translated-list model starts with worst-case lists and shifts each by a random field element.Source: §1.5.2 · p. 18
• [SW26] established a worst-case existential guarantee SCLρ(R/2+δ), implying asymptotically perfect solutions for R ≥ 0.749, but not an algorithmic result.Their work also identified the Fourier-proxy connection between OPI and LLR.Source: §1.5.2 · p. 18
• [Jo26] made the [SW26] bounds algorithmic when R/2+δ < αJ(R), including balanced-list perfect solutions for R ≥ 3/4; [HY26] guaranteed perfect solutions for R ≥ 0.715.[HY26] was concurrent with and also improved existential results.Source: §1.5.2 · p. 18
• Earlier work approached the double semicircle law for folded OPI [KGFJ+26], whereas this paper studies scalar OPI.For folded OPI over very large fields, quantum algorithms solve instances that require super-polynomially many classical membership-oracle queries [KGFJ+26].Source: §1.5.2 · p. 18

LLR threshold

• The correct Shamir LLR threshold remains open: the paper shows it can be below 1/2, while conjectures it can be an arbitrarily small constant.The authors note that this still leaves a long way to go.Source: §1.6 · p. 18

OPI satisfaction

• For OPI, the optimal satisfaction guarantee s* is unknown in some parameter regimes; the paper proves s* ≥ Vρ, while Theorem 1.10(2) suggests a possibly stronger bound.In some regimes, the paper has shown s* = 1.Source: §1.6 · p. 19

Quantum algorithms

• Whether the gap between existential OPI solutions and the largest satisfaction ratio attainable by a quantum algorithm can be closed remains open.The question concerns parameter regimes where solutions beyond current quantum algorithmic reach have been shown to exist.Source: §1.6 · p. 19

Classical hardness

• The paper’s classical–quantum hardness separation for OPI holds relative to membership oracles when the field is very large; whether a similar separation holds for polynomial-size fields remains open.The authors also ask whether such a result could rely on standard cryptographic assumptions.Source: §1.6 · p. 19

Research contributions

• Before recent Reed–Solomon list-decoding and list-recovery breakthroughs, the authors developed the OPI, LLR, and dual-list-recovery connections and applied Steps 1–4 to random Reed–Solomon codes.ChatGPT 5.6-Sol was consulted on numerical-threshold techniques, including Brascamp–Lieb inequalities and improvements to the MRRW linear-programming bound.Source: §1.7 · p. 19
• After those breakthroughs, the numerical techniques and distinction between random and arbitrary Reed–Solomon codes became redundant; ChatGPT 6-Astra supplied the truncation idea and arbitrary-bias extension described here.The passage identifies the truncation idea as Step 5 of Section 1.4 and the extension as Theorem 1.3(3) in Section A.Source: §1.7 · p. 19
• For the OPI hardness result, the authors adapted and constructed a sparse ensemble; ChatGPT 6-Astra then produced a balanced-ensemble version and Theorem 1.12, which the authors further simplified.The passage says the balanced-ensemble idea was prompted by distributing oracle checks.Source: §1.7 · p. 19

Other uses

• Beyond those contributions, AI was used for copyediting, proof checking, and TikZ code for Figures 1–3; the authors wrote all proofs and accept responsibility for errors.Source: §1.7 · p. 19

2.1 Notation and Conventions

• The section fixes asymptotic-comparison conventions, natural logarithms, and entropy domains in [0,1], with endpoint continuity and empty-set optimization conventions.Subscripts indicate parameters on which implicit constants may depend.Source: §2.1 · p. 20

2.2 Coding Theory

• RS and GRS codes are MDS; GRS duals are [n, n-k] GRS codes of distance k+1, and list recovery counts codewords matching bounded coordinate lists on at least (1−δ)n positions.List decoding is the singleton-list case; puncturing an MDS code to at least k coordinates preserves dimension k.Source: §2.2 · p. 20

2.3 Fourier Analytic Tools

• For fixed τ in (0, 1/2), the U3-gap lemma gives ∥f∥U3 ≤ q < 1, while the MDS von Neumann inequality bounds its average by ∏_{j∈J}∥Lj∥U3.The U3 bound applies when the minority probability is bounded away from 0; the inequality also allows affine shifts in its coordinate maps.Source: §2.3 · pp. 22–24

2.4 Computation Model and Subsampling

• For existential satisfaction, enlarging lists preserves solutions, while uniform relative-discrepancy bounds for lists of size t transfer without loss to lists of size at least t.The discrepancy transfer uses independent uniformly random t-subsets of the input lists.Source: §2.4 · p. 25
• A poly(n, log p, ρ^-1)-time quantum algorithm for lists of density ρ extends to lists of density at least ρ, preserving its satisfaction ratio with high probability.The reduction applies when the original algorithm succeeds with inverse-polynomial probability on every equal-density instance.Source: §2.4 · p. 25
• Rather than enumerate T_i, the algorithm samples and stores (a_i,b_i,h_i), simulates membership queries with polynomial-time overhead, and achieves satisfaction ratio at least s with probability at least σ/2.It boosts this to high probability with polynomially many repetitions, since σ is at least inverse polynomial.Source: §2.4 · p. 27
• The algorithm samples and stores (a_i, b_i, h_i), simulates membership oracles for the subsampled lists, and amplifies success by polynomially many repetitions.It evaluates each candidate on the original lists and returns the best; the overhead is polynomial in n, log p, ρ^-1, σ^-1, and Q.Source: §2.4 · pp. 27–28

3 Fourier Proxies and Thresholding

• The Fourier proxies use centered functions with mean zero and L2 norm 1, whose nonzero Fourier coefficients are bounded in terms of the coordinate densities.The section presents exact centered proxies and positive, phase-forgotten relaxations for arbitrary coordinate densities.Source: §3 · p. 28

3.1 The OPI Discrepancy Proxies

• The OPI discrepancy subsection derives a translated OPI proxy and also uses its positive relaxation, which forgets the phase term.The exact and positive OPI proxies had also been used in [SW26] [HY26].Source: §3.1 · pp. 28–29

3.2 The One-Bit LLR Proxies

• Every Shamir scheme with fixed rate R > RKK(τ) is one-bit locally leakage resilient when each leakage density is at least τ, under the stated prime-field and growth conditions.The proof obtains exponentially small total-variation distance between transcripts for distinct secrets.Source: §3.2 · p. 31
• At τ = 1/2, RKK(τ) = 0.579..., matching; the required rate decreases for τ > 1/2, improving on for more biased leakage.The bias-aware centering avoids a reduction from balanced to unbalanced leakage.Source: §3.2 · p. 31, Figure 3 · p. 32

3.3 Implications Between OPI and LLR

• If every secret-shifted code coset has near-optimal OPI discrepancy for the leakage-preimage lists, then the code is one-bit LLR.Source: §3.3 · p. 32
• In an MDS-code example, transcript distance and the LLR proxy can be superexponentially small even while worst-case OPI discrepancy is superexponentially large.The gap arises because LLR averages over transcripts, whereas uniform OPI discrepancy requires relative control on every transcript, including exponentially rare ones.Source: §3.3 · p. 33

4 Local Leakage Resilience

• Every fixed b-bit leakage is resilient for R > 1/2, and one-bit leakage is resilient for R > 1/2 − δ for an absolute δ > 0.The latter breaks the one-half barrier; the proof gives exponentially small leakage error.Source: §4 · p. 34, §4.1 · p. 34

4.1 Many-bit LLR Above Rate 1/2

• List recovery of the dual code certifies the leakage tests, allowing the test criterion to turn list-recovery bounds into leakage resilience.For the above-half result, the proof obtains list recovery with list size n^O_R,b(1) and then exponentially small leakage error.Source: §4.1 · p. 34

4.2 Weighted Fourier Thresholding

• Weighted Fourier thresholding controls the relevant sums when 2k − t = Ω(n), but applying it through t = n requires R > 1/2.The thresholding argument combines bounded Fourier weights, list recovery, and the dual code’s MDS structure.Source: §4.2 · pp. 35–36

4.3 One-bit LLR Below Rate 1/2

• For one-bit leakage, the proof extends resilience to R ≥ 1/2 − δ; balance is needed only for the large-support estimate, while the low-support estimate allows arbitrary biases.The transcript distributions have exponentially small total variation distance, and the arbitrary-bias extension is established separately.Source: §4.3 · pp. 38–39

5 Near-Optimal OPI Discrepancy

• Near-optimal OPI discrepancy holds when R > 1/2 − δ and ρ ≥ 1/2 − δ, or when R + ρ > 1.For R > 1/2, the result also applies to lists of any fixed positive density.Source: §5 · p. 39, §5.1 · p. 40

5.1 OPI Above and Near Rate 1/2

• For rates R ≥ 1/2 − δ, the balanced OPI case has near-optimal discrepancy, with the proof extending this to fixed densities ρ ≥ 1/2 − δ.Above rate 1/2, the argument uses weighted Fourier thresholding; near 1/2, it splits supports into small and large cases.Source: §5.1 · pp. 39–41

5.2 Recap of the Satisfaction Expansion in [SW26]

• The satisfaction expansion framework yields expected satisfaction ratio SCL_ρ(α) + o(1) when measuring the normalized DQI state under its stated sufficient condition.The framework expands products of the q_j functions back into q_t terms to evaluate expected satisfaction.Source: §5.2 · p. 42

5.3 OPI with Rate R > 1 −ρ

• When R + ρ > 1, truncating the construction yields near-optimal OPI discrepancy, and the theorem implies existence of a perfect solution for sufficiently large n.The truncation is designed to preserve comparable mass on the code while concentrating mass on perfect solutions.Source: §5.3 · pp. 44, 46

6.2 Improved Semicircle law

• For lists of size at least ρp, a quantum algorithm runs in polynomial time and, with probability 1−o(1), outputs a polynomial satisfying at least SCLρ(R) − ε of the constraints.Source: §6.2 · p. 49
• For ρ < 1/2 and R ∈ (ρ, 1/2], every Reed–Solomon instance over p ≥ n with |S_i| ≥ ρp has a polynomial satisfying at least Vρ(R) − ε of constraints.Source: §6.2 · p. 50
• The existential bound punctures coordinates T, conditions a DQI state on satisfying T, and optimizes t and ℓ subject to t + 2ℓ ≤ 2k − Ω(n).Conditioning charges the coordinates in T once, keeping support degree t + 2ℓ even when t + ℓ > k.Source: §6.2 · pp. 50, 52
• Directly preparing the conditioned state is inefficient: it requires dual-code list decoding through radius t + ℓ, beyond R, where list sizes are exponentially large.Source: §6.2 · p. 52

6.3 Perfect Solution at Capacity

• When R + ρ > 1, the same algorithm finds a polynomial satisfying every constraint with high probability in polynomial time.The procedure makes polynomially many independent attempts and verifies each output exactly.Source: §6.3 · pp. 52–53
• Measuring a state with amplitudes H_l, for (1 − ρ)n + Ω(n) ≤ l ≤ k − Ω(n), attains a perfect solution with high probability.The state can be prepared efficiently by adapting the proof of Theorem 6.1 to use the coefficients defining H_l.Source: §6.3 · p. 53
• The proof uses coefficients from the original DQI state so Theorem 6.1 applies in its stated form, for simplicity.Using coefficients defining H_l instead gives an alternative proof of Theorem 1.8(2).Source: §6.3 · p. 53

7 Quantum Advantage for OPI Relative to a Membership Oracle

• Both encodings require super-polynomial p and membership oracles; their tailored simulations enable perfect search where Section 6 guarantees do not cover vanishing-density or vanishing-rate ensembles.This contrasts with earlier results that can use polynomial-size p and avoid membership oracles.Source: §7 · p. 54

7.1 Recap of the Source Ensemble in [YZ24]

• The reduction starts from the Yamakawa–Zhandry source ensemble, where a uniform polynomial-time quantum algorithm finds a perfect source message with probability 1 − e^-Ω(m).The source ensemble is based on the YZ random-oracle search problem.Source: §7.1 · pp. 54–55, §7 · p. 54

7.2 The Sparse Target OPI Ensemble

• For arbitrary-rate OPI codes, the sparse encoding yields quantum perfect solutions with probability 1 − e^-Ω(n), while classical polynomial-query algorithms exceed one constraint with probability at most e^-Ω(n).Some input lists are exponentially sparse, with |S_i| = 2^-Θ(n)p.Source: §7 · p. 54, §7.2 · p. 56

7.3 The Balanced Target OPI Ensemble

• With balanced lists, quantum algorithms find perfect OPI solutions with all but negligible probability, while classical polynomial-query algorithms negligibly often exceed 1/2 + Ω(1/log log n).The ensemble has rate 1/polylog(n) over prime fields of quasipolynomial size.Source: §7.3 · p. 57
• The balanced construction spreads source-perfectness across parity tests, with random setup enforcing that any high-satisfaction polynomial is a constant encoding an extreme-satisfaction source message.A constant polynomial encoding a perfect source message has perfect target satisfaction.Source: §7.3 · pp. 57–58
• A polynomial-time quantum algorithm finds a degree-<k polynomial with satisfaction 1 with probability 1−e^-Ω(m), while classical polynomial-query algorithms exceed 1/2+ε with probability at most e^-Ω(m).Here ε = Θ(1/log log n); the theorem’s parameter line gives log p = Θ((log n)^4 log log n).Source: §7.3 · pp. 60–62
• The quantum algorithm applies [YZ24] to the Yamakawa–Zhandry source ensemble transformed into OPI, rather than generically applying DQI algorithms, which give only 1/2+o(1) when the code rate vanishes.The passage also notes that the original DQI algorithm [JSW+25] could be adapted to the folded transformed ensemble.Source: §7.3 · p. 62
• For any constants ε>0 and c>0, an alternative parameterization has p=exp(n^Θ(1)), rate R≫n^-c, classical ceiling 1/2+ε, and error e^-Ω(n^(1/t)) for t>2/c.The setup takes H=1 and N=(m…); the passage gives this parameterization for sufficiently large fixed even t.Source: §7.3 · p. 62

A Arbitrary Bias One-bit LLR Below Rate 1/2

• LLR averages deviations over transcripts, whereas uniform OPI discrepancy requires relative control on every transcript, including exponentially rare ones.An all-one transcript in the example has probability p^-k under one translate and zero under the other, but probability p^-n under the reference distribution.Source: A Arbitrary Bias One-bit LLR Below… · p. 66
• The L1(ν) proxy retains a density factor that helps with biased leakages, unlike the L2(ν) proxy that may fail to be small when leakage bias is extreme.The strongly biased-coordinate bound combines this proxy with a Brascamp–Lieb inequality proved in [HY26].Source: A Arbitrary Bias One-bit LLR Below… · p. 66
• For some absolute δ > 0, one-bit leakage bounds hold uniformly for generalized Reed-Solomon codes over prime fields with p ≥ n and rate R ≥ 1/2 − δ.The proof concludes with an e^-Ω(n) bound, uniformly over leakage tuples and translates.Source: A Arbitrary Bias One-bit LLR Below… · pp. 67, 69
• The proof splits leakage supports at m = ⌊(2 − δ)k⌋, handling small supports with the prior local bounds and large supports according to how many coordinates are strongly biased.When many coordinates are strongly biased, the proof uses an L1(ν) bound rather than paying the full supremum norm of the leakage functions.Source: A Arbitrary Bias One-bit LLR Below… · pp. 66–68

B Near-balanced OPI Discrepancy Below Rate 1/2

• The proof splits supports at m = ⌊(2 − δ)k⌋, retaining the small-support estimate and treating large supports with weighted functions close to balanced sign functions.For large supports, it applies the U3 bounds to selected coordinates and controls the resulting contribution by choosing δ sufficiently small.Source: B Near-balanced OPI Discrepancy Below… · pp. 69–70
• A small constant density perturbation suffices for the near-balanced OPI argument, and combining its two estimates proves the lemma.The large-support contribution is e^-Ω(n) for sufficiently small δ.Source: B Near-balanced OPI Discrepancy Below… · pp. 69–70
• For some absolute δ > 0, the discrepancy bound holds uniformly for generalized Reed-Solomon codes with R ≥ 1/2 − δ over prime fields p ≥ n, when all lists have common density ρ ≥ 1/2 − δ.The proof extends the bound to lists with individual densities at least 1/2 − δ by sampling subsets of a common density and applying Proposition 2.11.Source: B Near-balanced OPI Discrepancy Below… · pp. 69–70