arXiv CS open access

Local Leakage Resilience of Shamir Secret Sharing: Below Half Threshold Rate

Hai H. Nguyen · arxiv_cs

arXiv CS · Papers

We study the local leakage resilience of Shamir secret sharing, where an adversary leaks a bounded number of bits from every share. For $n$ parties and reconstruction threshold $k$ over a prime field $\mathbb{F}_p$ with $p>n$, we prove the following. (1) There is an absolute constant $c_{\mathr

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Local Leakage Resilience of Shamir Secret Sharing: Below Half Threshold Rate

arXiv:2610.17711v1 [cs.CR] 13 Oct 2026

Hai H. Nguyen∗

Abstract We study the local leakage resilience of Shamir secret sharing, where an adversary leaks a bounded number of bits from every share. For n parties and reconstruction threshold k over a prime field Fp with p > n, we prove the following. • There is an absolute constant cbh < 1/2 such that, for k ≥ cbh n, Shamir sharing is resilient to arbitrary one-bit leakage from every share. The best previous threshold was 0.668n. δ • For every fixed 0 < δ < 1/2 and k ≥ (1/2 + δ)n, Shamir sharing is resilient to 24 log2 n bits of arbitrary local leakage per share. By a recent attack, this number of bits is optimal up to a constant factor depending on δ. • For every fixed threshold rate c > 0 and k ≥ cn, Shamir sharing is resilient to quadratic-residue leakage and to almost all local leakage functions of up to ηc log2 p bits, for a constant ηc > 0. All three results follow from one analytic framework, which we develop for generalized Reed–Solomon codes: local leakage from a uniform codeword is statistically close to the same leakage from independent uniform field elements. The framework expresses the leakage distance as the norm of a function on the leakage outputs. The Efron–Stein decomposition splits this function into orthogonal components indexed by supports of dual codewords. Two tools bound the components: list recovery of the dual code, which is ordinary list decoding for one-bit leakage, and a generalized von Neumann inequality for MDS systems of linear forms that retains linearly many Gowers norms. The first tool gives the result above half, the second gives the constant-rate result, and applying both to different ranges of supports in the same decomposition gives the result below half.

∗

hai.h.nguyen@nus.edu.sg

Contents 1 Introduction 1.1 Our contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Technical overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 1 4 8

2 Preliminaries 2.1 Generalized Reed–Solomon codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Shamir secret sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Local leakage resilience . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Fourier analysis and Gowers norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 List decoding and list recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10 10 11 11 12 13

3 An orthogonal decomposition of the leakage distance 3.1 Efron–Stein decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 The leakage distance as a norm on the output space . . . . . . . . . . . . . . . . . . 3.3 The orthogonal components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 One-bit leakage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13 14 15 16 17

4 Dual-code list recovery and resilience above half 18 4.1 Bounding the leakage components . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2 Applying list recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5 Structured leakage at constant-rate thresholds 5.1 A product bound for Gowers norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 From Gowers norms to leakage resilience . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Quadratic-residue leakage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Almost all logarithmic-bit leakage functions . . . . . . . . . . . . . . . . . . . . . . . 5.5 Field size for square-root thresholds . . . . . . . . . . . . . . . . . . . . . . . . . . .

22 23 25 25 26 27

6 Leakage resilience below half 6.1 List recovery for small supports . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Iterated Cauchy–Schwarz for large supports . . . . . . . . . . . . . . . . . . . . . . . 6.3 Combining the estimates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28 28 30 32

A List recovery with growing input lists

B An alternative list-recovery calculation from DKT

Introduction

Shamir secret sharing [Sha79] is a fundamental cryptographic primitive with many applications. In an (n, k)-Shamir scheme, a secret is encoded in n evaluations, called shares, of a random polynomial of degree below k whose constant coefficient is the secret. Any k shares determine the secret, and any fewer reveal nothing about it. The algebraic structure also allows efficient computation on shared secrets, which makes the scheme a central building block of secure multiparty computation (MPC) [BOGW88, CCD88]. Classical MPC protocols tolerate passive corruption of fewer than half the parties, or active corruption of fewer than one third, with reconstruction thresholds near n/2 and n/3 respectively. What happens if, instead of learning a few shares in full, an adversary learns a little about every share? The question is motivated by side-channel attacks, which extract information from physical implementations through observations such as running time and power consumption [Koc96, KJJ99]. Benhamouda, Degwekar, Ishai, and Rabin [BDIR18] formalized locally leakage-resilient secret sharing.1 In this model the adversary obtains a bounded number of bits from each share through a function of its choice, and local leakage resilience requires the joint leakage to be statistically independent of the secret. The guarantee is strong because the leakage functions are arbitrary: even one-bit leakage permits any Boolean function of each share, not merely a bit of its representation. Local leakage can be surprisingly powerful. For suitable parameters over binary extension fields, Reed–Solomon repair algorithms [GW16] even recover the entire secret from one bit of leakage per share. Over prime fields, Benhamouda et al. [BDIR18] proved resilience to arbitrary one-bit local leakage when k ≥ 0.907n, and substantial effort has gone into lowering this threshold: independent improvements gave 0.8675n [MPCSW21] and 0.85n [BDIR21], followed by 0.78n [MNPCW22], 0.69n [KK23], and 0.668n [Kas25].2 Below half, resilience is known only for restricted leakage classes: physical-bit leakage with high probability over randomly chosen evaluation points in sufficiently large prime fields [MNPC+ 21], quadratic-residue and almost all one-bit local leakage [Ngu24], and sufficiently unbalanced leakage [KK23]. Previous guarantees against arbitrary one-bit local leakage all require threshold rates strictly above half. Benhamouda et al. [BDIR18, BDIR21] conjectured that Shamir sharing over prime fields is resilient to arbitrary one-bit local leakage at every positive constant rate.3 Despite the subsequent improvements, this conjecture remained open even at rate half. There is also a technical obstacle. Maji et al. [MPCSW21] showed that the bound obtained by summing Fourier magnitudes in earlier analyses cannot establish resilience below rate half, already for quadratic-residue leakage.4 Summary of our results. We prove that (n, k)-Shamir sharing is resilient whenever k ≥ cbh n, for an absolute constant cbh < 1/2, establishing the conjecture in a range that extends below half. We also obtain logarithmic-bit leakage resilience above half (by any fixed constant), and guarantees against restricted leakage families at every positive constant rate.

1.1

Our contributions

We first introduce notation. Consider (n, k)-Shamir sharing with n parties, reconstruction threshold k, and distinct nonzero evaluation points α = (α1 , . . . , αn ) over a prime field Fp , where p > n. To share a secret s ∈ Fp , this scheme samples a uniformly random polynomial P ∈ Fp [X] of degree less than k such that P (0) = s and gives party i the share P (αi ). An m-bit local leakage function is a 1

The notion also appears implicitly in the work of Goyal and Kumar [GK18]. The last two assume a field of size 2o(n) . 3 Their conjecture applies more generally to secret-sharing schemes based on MDS codes. 4 For a share x ∈ Fp , this one-bit leakage outputs 1 if x = y 2 for some y ∈ Fp , and 0 otherwise. 2

tuple of maps τ = (τ1 , τ2 , . . . , τn ), where τi : Fp → {0, 1}m . For x = (x1 , . . . , xn ) ∈ Fnp , write τ (x) := (τ1 (x1 ), . . . , τn (xn )).

The leakage distribution induced by τ on secret s is the distribution of (τ1 (P (α1 )), . . . , τn (P (αn )) , where P is sampled as above. The scheme is ε-resilient to m-bit local leakage if, for every such m-bit local leakage function, the leakage distributions of any two secrets have statistical distance at most ε. We call k/n the threshold rate and m/ log2 p the leakage rate, the fraction of each share’s bit length revealed by the leakage. All following results hold for every choice of evaluation points and all sufficiently large n, with constants and the required lower bound on n depending only on the fixed parameters. In particular, there is no upper bound on p. Below half.

Our first result crosses the 1/2 rate for one-bit local leakage.

Theorem 1 (Below half). There is an absolute constant cbh < 1/2 such that every (n, k)-Shamir scheme with k ≥ cbh n is exp(−Ω(n))-resilient to one-bit local leakage. The previous best bound for arbitrary one-bit leakage was 0.668n, under the field-size restriction p = 2o(n) [Kas25]. Our theorem crosses half without this restriction.5 In particular, the theorem covers k = ⌈n/2⌉, the reconstruction threshold at the classical n/2 passive-corruption bound in MPC. The proof gives the explicit, unoptimized constant cbh = 1/2 − 10−14 (Corollary 6). The full BDIR conjecture remains open, in particular at threshold rate 1/3. At smaller thresholds, Nielsen and Simkin [NS20] give an inefficient one-bit leakage attack when k is of order n/ log p, which is n/ log n when p = poly(n). Closing this gap remains an open problem. Asymptotically optimal leakage above half. Progress on the reconstruction threshold has concentrated on one-bit leakage. A second basic question is how many bits per share Shamir sharing withstands. We show that, at every threshold rate above half, the answer is logarithmic in n: for polynomial-size fields p = poly(n), this is a constant fraction of each share’s bit length. Theorem 2 (Logarithmic leakage above half). Fix 0 < δ < 1/2. Any (n, k)-Shamir sharing with k ≥ (1/2 + δ)n is exp(−Ωδ (n1−δ/12 ))-resilient to ⌊(δ/24) log2 n⌋-bit local leakage. Previous guarantees of a constant leakage rate required a threshold rate tending to one. Benhamouda et al. [BDIR21, Corollary 4.13] obtain it for n < p ≤ 2n and k > n − n1/4 . Our threshold rate stays fixed above half, and the field may be arbitrarily large. The number of leaked bits is tight up to a constant factor depending on δ. Boudgoust and Simkin [BS26] give an efficient attack using log2 k + O(1) bits per share over arbitrary finite fields. The proof reduces m-bit leakage resilience to list recovery of the dual code with input lists of size 2m − 1; for one bit this is ordinary list decoding. Letting m grow requires the dependence of the list size on the input-list size, which we extract from the proofs of Jeronimo [Jer26] and of Dao, Kominers, and Thaler (DKT) [DKT26] in Sections A and B. The criterion of Maji, Paskin-Cherniavsky, Suad, and Wang [MPCSW21, Technical Lemma 1] is also a list-recovery condition on the dual code, and combined with the same bound it yields Theorem 2 for every fixed m. Its parameters, however, degrade doubly exponentially in m: its input lists have size 2m T 2 with T = 2Θ(m/σ) and σ = O(4−m ), because the underlying ℓ1 bound sums over all 2mn leakage outputs. This direct application gives only O(log log n) bits. 5

This allows a λ-bit prime p with n = O(λ), a common parameter regime in MPC.

Restricted leakage families at every constant threshold rate. Our third result concerns every positive constant threshold rate, including below half, for two restricted leakage families: quadratic-residue leakage, where party i reveals whether ai P (αi ) + bi is a square, for arbitrary ai ∈ F∗p and bi ∈ Fp ; and almost all tuples of local leakage functions revealing Θ(log p) bits per share. Theorem 3 (Structured leakage at constant threshold rate). Fix 0 < c < 1. There are constants ηc , ac , bc > 0 such that any (n, k)-Shamir sharing with k ≥ cn is 1. exp(−ac n log p)-resilient to quadratic-residue leakage (with arbitrary affine shifts), and √ 2. for every integer 1 ≤ m ≤ ηc log2 p, exp(−ac n log p)-resilient to all but an exp(−bc p) fraction of m-bit local leakage functions. Nguyen [Ngu24] proved resilience to quadratic-residue and random one-bit leakage using higherorder Fourier analysis, but the bounds require a field size exponential in n at constant threshold rate. Unlike Theorem 2, the leakage rate in part 2 stays constant for every prime p > n, not only polynomial-size fields, and below half. For superpolynomial-size fields, this separates worst-case from average-case leakage: the attack of Boudgoust and Simkin [BS26] limits the worst-case leakage rate to O(log k/ log p) = o(1). √ At smaller thresholds, quadratic-residue leakage can be insecure: for n = p − 1 and k = O( n), Kopparty’s algorithm for recovering a polynomial from noisy quadratic-character values [Kop26] yields an attack with the same shifted quadratic-residue leakage (Section 5.5). From Shamir sharing to codes. For distinct evaluation points α ∈ Fnp and nonzero multipliers v ∈ (F∗p )n , the generalized Reed–Solomon code of dimension d is GRSα,v (n, d) = (vi Q(αi ))ni=1 : Q ∈ Fp [X], deg Q < d .

The shares of the zero secret in an (n, k)-Shamir sharing are uniform on C0 = GRSα,α (n, k − 1), and the shares of secret s are uniform on the translate s1 + C0 , where 1 = (1, . . . , 1). Call a linear code C ⊆ Fnp ε-resilient to m-bit local leakage if, under every tuple of m-bit leakage maps, a uniform codeword and a vector of n independent uniform field elements have leakage distributions within statistical distance ε. We prove all three results in this code form (Theorems 6 to 8), as a pseudorandomness property of GRS codes under local leakage, and the guarantees for Shamir sharing follow: for arbitrary m-bit local leakage, resilience of the code implies resilience of the scheme with twice the error, and conversely with error larger by a factor O(n) (Lemma 1). Technical Highlights. We develop an analytical framework in which all three theorems are proved. It combines the Efron–Stein orthogonal decomposition over the product space of leakage outputs with Fourier analysis over the uniform measure on the inputs. Its key feature is flexibility: the framework organizes the leakage analysis into orthogonal components, and each component can be analyzed either through its L2 -norm using linear Fourier analysis, or through its L1 -norm using higher-order Fourier analysis. Previous analyses each took a single route. Benhamouda et al. [BDIR18, BDIR21] and their successors [MNPC+ 21, MPCSW21] bound an ℓ1 sum of Fourier magnitudes over the dual code; Klein and Komargodski [KK23, Kas25] bound an ℓ2 quantity obtained from Pinsker’s inequality; Nguyen [Ngu24] bounds Gowers norms of the leakage functions. The framework brings these analytic approaches together, allowing different estimates on different components. Their combination within the same decomposition is what crosses half.

Concurrent and independent work. Sun and Wootters [SW26a] independently prove one-bit local leakage resilience of Shamir sharing at a constant threshold rate below half, obtaining the same qualitative guarantee as Theorem 1. They also prove resilience to any fixed number of leaked bits per share above half. The approaches share an important feature: both use list recovery of the dual code for small supports and Gowers-norm estimates for large supports. Our work additionally establishes logarithmic-bit resilience above half and the restricted-leakage guarantees at every positive constant threshold rate (Theorems 2 and 3). Sun and Wootters also obtain existential and quantum-algorithmic results for worst-case optimal polynomial intersection, which we do not study here.

1.2

Technical overview

By the reduction described above (Lemma 1), it suffices to prove the code form of our results: local leakage cannot distinguish a uniform codeword from independent uniform field elements. Fix a GRS code C = GRSα,v (n, k − 1) and leakage maps τi : Fp → {0, 1}m . Let U C and U Fnp be uniformly distributed on C and Fnp , respectively. The goal is to show that the statistical distance between τ (U C ) and τ (U Fnp ), which is called leakage distance, is small. The framework. Under independent uniform inputs, the leakage outputs are independent. Thus Q τ (U Fnp ) has a product distribution ν = i νi , where νi is the distribution of τi (UFp ). This allows us to use Fourier analysis on general product spaces ([O’D14, Chapter 8]). In particular, the Efron–Stein decomposition is a standard way to group a Fourier expansion into orthogonal components indexed by coordinate sets, without choosing an explicit basis. We first express the leakage distance as a norm under ν, then apply this decomposition and use the code’s linear structure to identify the components. Section 3 develops this approach in the following steps. Step 1: Write the leakage distance as a norm. For each leakage output b = (b1 , b2 , . . . , bn ), we compare its probability under leakage from a uniform codeword with ν(b). To express this ratio, start with the corresponding ratio on the inputs: fC (x) =

Pr[U C = x] pn = 1[x ∈ C], Pr[U Fnp = x] |C|

whose mean under uniform input is one. Leakage forgets which input produced b, so the output ratio is the average of this input ratio over all compatible inputs. This naturally gives the Markov operator (Definition 11) (Tf )(b) = E f (U Fnp ) τ (U Fnp ) = b . Its one-coordinate version is (Ti f )(b) = E[f (UFp ) | τi (UFp ) = b], and independence gives T = Thus, we have (Lemma 5) Pr[τ (U C ) = b] (TfC )(b) = . ν(b)

i Ti .

The leakage distance is therefore the average deviation of this ratio from one: SD τ (U C ), τ (U Fnp ) = 21 Eb∼ν (TfC )(b) − 1 = 12 ∥TfC − 1∥1,ν .

Thus we need to bound how far TfC is from the constant function 1, averaging over the product distribution ν. Here and below, we only consider outputs with ν(b) > 0. Step 2: Separate the contributions of different coordinate sets. The Efron–Stein decomposition separates a function on a product space into orthogonal components indexed by coordinate sets 4

A ⊆ [n] (Definition 10). A component depends only on A and disappears when any coordinate in A is averaged out: it records an interaction requiring all those coordinates. Apply this decomposition to TfC under the leakage distribution ν. Its constant component (A = ∅) is one, so TfC − 1 is the sum of its nonconstant components. To identify them, we can instead decompose fC under the uniform distribution on Fnp and then apply T. Because leakage acts separately on each coordinate, the two operations commute (Lemma 4): (TfC )=A = T(fC=A ),

TfC − 1 =

T(fC=A ).

∅̸=A⊆[n]

For all distinct coordinate sets A and B, the corresponding output components are orthogonal under ν. We can therefore analyze the dependence on each coordinate set separately. Step 3: Identify the components using the dual code. To make these components explicit, use the linear structure of the code. Fourier characters detect its linear constraints: the character Q χy (x) = i χyi (xi ), where χa (x) = exp(2πiax/p), is identically one on C when y ∈ C ⊥ , and otherwise averages to zero over C. Thus the Fourier coefficients of fC are one on C ⊥ and zero elsewhere. Grouping these characters by their nonzero coordinates gives exactly the Efron–Stein components (Lemmas 2 and 3): X fC=A = χy . y∈C ⊥ : supp(y)=A

Since C ⊥ has minimum distance k, all components with 0 < |A| < k vanish. We therefore only need to bound components with |A| ≥ k. Step 4: Choose how to bound the components. The two tools below provide different kinds of estimates: list recovery bounds squared L2 norms, while Gowers norms bound L1 norms. We need not choose one tool for every support. Using ∥ · ∥1,ν ≤ ∥ · ∥2,ν and orthogonality, we can bound a group of components by the square root of the sum of their squared L2 norms. For the others, the triangle inequality lets us add individual L1 bounds. Choosing a cutoff k − 1 ≤ r0 ≤ n gives (Proposition 1)

SD τ (U C ), τ (U Fnp ) ≤

1/2 1 X 1 X + ∥T(fC=A )∥22,ν ∥T(fC=A )∥1,ν . 2 k≤|A|≤r 2 |A|>r 0

Above half we take r0 = n, using only the first part. For the restricted leakage families we take r0 = k − 1, using only the second. Below half we choose an intermediate cutoff close to n and combine both tools. Above half: L2 norms and list recovery of the dual code. Here we take r0 = n and then bound the sum of squared component norms. The first question is how the leakage acts on a component, which is a sum of characters χy over dual words with support A. Applying T to every coordinate loses the orthogonality among them, but applying it to only k − 1 coordinates I ⊆ A does not: two dual words with support A that agree outside I differ on at most k − 1 coordinates, hence coincide, so their characters on A \ I are distinct and still orthogonal; and applying the remaining Ti afterwards can only shrink an L2 norm by the contraction property of Markov operators. This gives (Lemma 8) X Y ∥T(fC=A )∥22,ν ≤ ∥Ti χyi ∥22,νi . y∈C ⊥ : supp(y)=A i∈I

So each dual word is charged k − 1 one-coordinate factors ∥Ti χa ∥22,νi . There are two facts about them (Lemma 9). Their sum over a ̸= 0 is at most Q − 1, where Q = 2m . And each is at most ηQ < 1. 5

Now comes the counting problem: a sum over all dual words with support A, summed over A, of products of k − 1 factors. Spending all k − 1 factors on decay leaves a bare count of dual words, which is p n−k+1 and useless. The trick is to split the factors. Keep j of them, bound the other k − 1 − j by ηQ , and look at the sum that remains. It is linear in the weights wi (a) = ∥Ti χa ∥22,νi of each coordinate separately, with nonnegative coefficients, under the constraints wi (a) ∈ [0, 1] and P a̸=0 wi (a) ≤ Q − 1. Such a sum is maximized at an extreme point, which puts weight one on Q − 1 frequencies and zero elsewhere (Lemma 10). After this replacement the sum counts dual words that agree with lists Vi ⊆ F∗p of size Q − 1 on at least j coordinates (Lemma 11). This count is bounded by the list size at radius n − j, in the notation ListC ⊥ (R, ℓ) (Definition 9): X

∥T(fC=A )∥22,ν ≤ ηQk−1−j ListC ⊥ (n − j, Q − 1).

|A|≥k

The lists live on Fourier frequencies. For one bit they are singletons and this is list decoding. The dual of a GRS code is a GRS code, so either of the list-recovery results of Jeronimo and DKT [Jer26, DKT26] makes ListC ⊥ (R, ℓ) polynomial in n for fixed input-list size ℓ and fixed gap ζ > 0, at radius R ≤ k − 1 − ζn (Theorem 4). With j = n − R there are at least 2R − n factors left R−n/2 p for decay, and the bound is 12 ηQ ListC ⊥ (R, Q − 1) (Theorem 5). This also says exactly where the argument stops: it needs R > n/2 with R < k, hence k > n/2. Below half no choice of j ≤ k − 1 reaches a radius covered by this polynomial-list bound. Above 1/2 + δ, a linear number of decay factors remain, so their product absorbs the polynomial list size. Increasing the leakage alphabet has two costs: the local decay becomes weaker, and the list-recovery bound becomes larger. The same linear number of factors can absorb both costs as long as the logarithm of the list bound stays smaller than the decay exponent. Keeping the dependence on Q explicit in these proofs (Sections A and B) allows Q to grow to nδ/24 , giving the logarithmic leakage in Theorem 2. Every constant threshold rate: L1 norms and iterated Cauchy–Schwarz. For the restricted families, we take r0 = k − 1 and bound each component in L1 . By a simple calculation, the L1 norm of each component is a sum of absolute values of averages (Lemma 6), each of the following form: "

ΛΨ (f ) = Ez

# Y

fi (Li (z)) .

i∈A

Here z ∈ Fk−1 is the vector of independently and uniformly chosen polynomial coefficients, and p Li (z) is the i-th coordinate of the resulting codeword. We write Ψ = (Li )i∈A , where |A| ≥ k. The functions fi are bounded by one and determined by the leakage maps and outputs (see Section 5.1). Such averages arise naturally in additive combinatorics. For indicator functions, they give normalized counts of configurations described by linear forms, such as arithmetic progressions [TV06, GT10]. Repeated applications of Cauchy–Schwarz bound these averages in terms of Gowers norms [Gow01, GT10]. Nguyen [Ngu24] uses the scalar generalized von Neumann inequality to bound such averages. For a suitable Gowers order t, it gives |ΛΨ (f )| ≤ min ∥fi ∥U t . i∈A

This retains only one small factor to compensate for exponentially many averages, leading to the large field sizes in that analysis. Nguyen [Ngu24, Remark 1] conjectured that a better understanding of this inequality for the linear forms of MDS codes and the leakage functions arising here could lead to smaller-field bounds. 6

We observe that Manners’s formulation [Man21] allows us to retain a product of Gowers norms. The idea is to group several independent forms into one vector-valued map. The Gowers norm of the corresponding product function then factors into the individual Gowers norms. The coordinate forms of a GRS code are MDS: any k − 1 of them are independent. This structure gives, at every constant threshold rate c > 0, a constant Gowers order t and a set J ⊆ A such that |ΛΨ (f )| ≤

∥fi ∥U t ,

|J| = Ωc (n).

i∈J

See Lemma 12 and Corollary 3. The key saving comes from multiplying linearly many factors: even when the retained Gowers norms are close to one, a fixed gap below one gives exp(−Ω(n)) decay for each average. This will be crucial for the result below half, where the norms need not decrease with p. For quadratic-residue leakage and almost all local leakage maps, the local Gowers norms are at most p−Ωc (1) , by character-sum estimates and concentration, respectively (Sections 5.3 and 5.4). The product bound therefore gives the stronger exp(−Ωc (n log p)) decay. This absorbs the sum over supports and leakage outputs even when the number of leaked bits is a sufficiently small constant multiple of log p. Hence p > n suffices, giving Theorem 3; the parameter calculation is in Proposition 3. Why not arbitrary leakage at every constant rate? For arbitrary one-bit leakage, the Gowers norms need not be small enough for the resulting exponential decay to outweigh the exponentially many terms. This becomes more restrictive at smaller threshold rates, where the bound retains fewer Gowers-norm factors. Below half: both tools, and a uniform bound for one bit. We combine the two tools to handle arbitrary one-bit leakage below half, choosing a cutoff r0 close to n, using L2 bounds for the smaller supports and L1 bounds for the larger ones. Smaller supports. The dual words contributing to these components have many zero coordinates. These zeros provide additional agreements with the list {0} when applying list decoding. Fewer agreements must therefore come from the Fourier factors, leaving more factors available to provide decay. A modification of the earlier counting argument uses these extra agreements and bounds all supports of a given size together (Lemma 14 and Corollary 5). The resulting estimate makes their total squared L2 contribution exponentially small for supports that omit a fixed fraction of the coordinates, at threshold rates sufficiently close to half (Lemma 15). Larger supports. These supports have too few zero coordinates for the counting argument, so we turn to the linear-form averages. For one-bit leakage, the L1 norm of each component is the absolute value of a single such average (Lemma 7). Its factors fi are obtained by representing each leaked bit as ±1 and subtracting its mean under uniform input. Using Fourier symmetry and the fact that these functions take at most two values, we prove that ∥fi ∥U 3 ≤ κ0 < 1 for an absolute constant κ0 (Lemma 16). The product bound retains linearly many such factors even for full support at rate half (Corollary 3). The Gowers-norm bound controls only some of the factors in the average. The other factors are bounded by their maximum absolute values, which can be as large as two. Multiplying these bounds can therefore offset the saving from the Gowers norms. When the total squared bias is small, this loss is controlled; otherwise, the smaller variances give exponential decay by Cauchy–Schwarz and MDS independence, following a principle similar to that in [KK23, Section 6]. Together, these 7

estimates make each large-support contribution exponentially small, uniformly over the leakage maps (Lemma 17). Taking the cutoff sufficiently close to n makes the number of remaining supports small enough for this decay to survive summation (Proposition 4). Putting it together. At the limiting parameters of rate half and zero decoding gap, both estimates leave a strict exponential margin. By continuity, this margin survives at a fixed rate slightly below half and a small positive decoding gap, with both ranges of supports still covered. The list-decoding theorem is used only at that positive gap. This proves Theorem 1; Section 6.3 gives the parameter choices.

1.3

Related work

New constructions of leakage-resilient secret sharing. Following [GK18, BDIR18], a line of work has developed secret-sharing schemes designed to withstand local leakage. General compilers support arbitrary monotone access structures while providing strong leakage guarantees with controlled share-size overhead [SV19, ADN+ 19]. Other constructions address adaptive leakage involving bounded groups of colluding parties [KMS19, CGG+ 20], or improve share sizes [CKOS22]. Such constructions need not preserve the algebraic structure of the underlying scheme, including linearity, which is important in applications such as MPC. In contrast, our work establishes leakage resilience of Shamir scheme. Local leakage resilience of existing linear schemes. Shamir and additive secret sharing are the most common linear schemes widely used in applications. For additive n-out-of-n sharing over prime fields, Maji et al. [MNPC+ 22] give a tight analysis of the parity-of-parity attack, establishing an optimal lower bound on the number of shares needed for resilience to one-bit leakage. Koga and Abe [KA26] obtain tight one-bit leakage bounds and further bounds for larger output alphabets. Attacks on local leakage resilience. Nielsen and Simkin present one-bit attacks at sublinear thresholds of order n/ log n [NS20]; Hoffmann and Simkin develop robust attacks that can tolerate noise in a constant fraction of the leakage outputs [HS23]. Other attacks exploit particular leakage functions or prime-field repair procedures [Ngu24, CSTW24]. Boudgoust and Simkin give a perfectly correct attack on schemes with linear reconstruction using log2 k + O(1) leaked bits per share over arbitrary finite fields [BS26]. The shifted quadratic-residue attack from [Kop26] is discussed in Section 5. None of these statements establishes impossibility at threshold rate half for exactly one-bit leakage. Our logarithmic-bit guarantee against arbitrary maps is above half; the below-half result concerns one bit and does not cover the full sublinear-threshold range. Physical-bit, Hamming-weight, and noisy leakage. Physical-bit leakage reveals selected bits in a fixed binary representation of each share, rather than the output of an arbitrary bounded-output function. Over prime fields, Maji et al. [MNPC+ 21] prove resilience to multiple physical bits per share for every reconstruction threshold k ≥ 2, using random evaluation points and sufficiently large fields. Subsequent work studies physical-bit leakage over extension fields [MNPCY24, Ngu25]. Hwang et al. [HMNY25] characterize secure evaluation points for n-out-of-n Shamir sharing over prime fields, while Venkitesh [Ven26] provides partial derandomization in certain extension-field regimes. For public-coefficient inner-product masking, Faust et al. [FMM+ 26] establish physical-bit leakage guarantees over Mersenne prime fields. Hamming-weight leakage reveals the number of ones in a share’s binary representation. It has been analyzed for inner-product masking over binary extension fields [BHMY26] and for additive

sharing over cyclic groups whose moduli are close to powers of two [BHM+ 26a, BHM+ 26b]. Noisyleakage models instead constrain the leakage channel through a noise assumption rather than its output length [PR13, DDF14, FMM+ 24, JMB26, GM26]. These results exploit the prescribed leakage function, the representation of shares, or the noise; they do not give resilience to arbitrary local leakage. List decoding of Reed–Solomon codes. Sudan’s interpolation algorithm and its extension by Guruswami and Sudan established the classical algorithmic approach and the Johnson-radius benchmark [Sud97, GS99]. Progress beyond that benchmark includes random puncturing, generalized Singleton bounds, and improved large-error-radius and list-recovery guarantees [RW14, ST20, FKS22, GLS+ 24]. For a code of rate R, the large-alphabet capacity target is an error fraction 1 − R − ζ, for any fixed gap ζ > 0. Brakensiek, Gopi, and Makam proved that generic Reed–Solomon codes reach this target over sufficiently large fields [BGM23]; [AGG+ 25] reduced the field-size requirement for random evaluation points to a sufficiently large constant times the block length. These guarantees concern generic or random codes, not every evaluation tuple. The recent results of [BCP+ 26, Jer26] reach capacity for arbitrarily fixed evaluation points over prime fields. The former supplies a new interpolation-based algorithmic approach; Jeronimo’s theorem gives the field-independent list bound ncζ,ℓ for every fixed input-list size ℓ, every prime p ≥ n, and sufficiently large n. Dao, Kominers, and Thaler [DKT26, Theorem G.2] also obtain list-recovery guarantees for fixed evaluation points, providing another route to the field-independent bound used here. We use ℓ = 1 for ordinary list decoding and ℓ = 2m − 1 for m-bit leakage. For growing m, we keep the dependence on ℓ explicit in Jeronimo’s proof and in DKT’s finite estimates (Sections A and B). The field-independent bound matters because our security bound must not deteriorate when p grows. Coordinate scaling extends these guarantees to generalized Reed–Solomon dual codes. Random linear codes provide a different route to capacity for list decoding [GHSZ02, GHK11, LW21] and list recovery [LS25, DMRR25, GG26]; folded Reed–Solomon codes also achieve listrecovery capacity [GR08]. For fixed alphabets, list-decoding capacity is expressed using the appropriate entropy function and should not be identified with the large-alphabet limit 1 − R. Our transfer applies coding guarantees to the dual code: the same statement uses ordinary list decoding for one-bit outputs and list recovery with input lists of size 2m − 1 for m-bit outputs. This is not direct recovery of shares from the leakage. A preimage of a bit can contain Θ(p) symbols; the lists in the transfer instead arise by replacing the Fourier weights ∥Ti χa ∥22 by list indicators in a weighted counting bound. Repairing Reed–Solomon codes. Repair bandwidth measures the amount of data downloaded to recover an erased symbol and is a central parameter in distributed storage [DGW+ 10]. For Reed–Solomon codes, Guruswami and Wootters [GW16] develop bandwidth-efficient linear repair schemes, and Tamo, Ye, and Barg [TYB17] achieve the cut-set bound over suitable large extension fields. Over prime fields, Con, Shutty, Tamo, and Wootters [CSTW24] use exponential sums to construct nonlinear repair procedures for low-rate Reed–Solomon codes that download only a constant number of bits from each helper. These results connect repair to local leakage: viewing the secret as an erased evaluation, a repair procedure yields a reconstruction attack whenever each helper’s message fits the permitted leakage budget. Discrepancy, zero-error list recovery, and OPI. The survey of Resch and Venkitesh [RV25] discusses the relation between local leakage and zero-error list recovery above capacity. Doron et

al. [DLM+ 26] prove near-expected codeword counts for random linear codes and derive local leakage resilience for ramp sharing with arbitrary positive linear reconstruction thresholds and a sublinear threshold gap. Their polynomial field sizes are smaller than the block length, and their codes and privacy/reconstruction tradeoff differ from the GRS threshold setting here. This prior connection is distinct from the dual-code transfer in Section 4. Sun and Wootters [SW26b] connect Fourier estimates for local leakage to worst-case optimal polynomial intersection (OPI) and obtain improvements over the semicircle satisfaction guarantee. Horinaga and Yamakawa [HY26] improve both existential and quantum-algorithmic bounds; Jo [Jo26] gives a quantum sampler based on complete list decoding. Organization. Section 2 gives the preliminaries and the Shamir reduction. Section 3 develops the orthogonal decomposition of the leakage distance. Section 4 proves the list-recovery transfer and logarithmic-bit leakage resilience above half. Section 5 uses the product bound for Gowers norms to establish the restricted-leakage results at every constant threshold rate. Section 6 combines the two tools to go below half. Section A gives the quantitative list-recovery bound used for logarithmic-bit leakage; Section B gives an alternative derivation from DKT.

Preliminaries

Throughout, p is an odd prime and Fp the field with p elements; the main theorems take p > n. Logarithms are natural unless a base is shown. Vectors are written in bold. Write [n] = {1, . . . , n}, supp(y) = {i : yi ̸= 0}, wt(y) = | supp(y)|, and dH (x, y) = wt(x − y). The binary entropy is h(t) = −t log t − (1 − t) log(1 − t), with h(0) = h(1) = 0. For a finite set S, US denotes the uniform distribution on S; a uniform random vector is written U S . Definition 1 (Statistical distance). For distributions P, Q on a finite set Ω, the statistical distance between them is defined as 1X SD(P, Q) = |P (x) − Q(x)|. 2 x∈Ω

2.1

Generalized Reed–Solomon codes

Definition 2 (Linear codes and Reed–Solomon codes). A linear code C of length n over Fp is a subspace of Fnp ; its elements are codewords. Its parameters [n, k, d]p are its length, dimension, and minimum Hamming distance between distinct codewords. Its rate is k/n. Its dual is C ⊥ = {y ∈ P Fnp : i xi yi = 0 for every x ∈ C}. For distinct evaluation points α ∈ Fnp , 1 ≤ k ≤ n, and multipliers v ∈ (F∗p )n , the generalized Reed–Solomon code of length n and dimension k is GRSα,v (n, k) = {(vi Q(αi ))ni=1 : deg Q < k}. Taking v = 1 gives an Reed–Solomon code. A code of dimension k is maximum-distance-separable (MDS) if its minimum distance is n − k + 1, or equivalently if projection onto any k coordinates is a bijection onto Fkp . GRS codes are MDS, and their duals are GRS codes on the same evaluation points: for C = GRSα,v (n, k − 1) with 2 ≤ k ≤ n, C ⊥ is a GRS code of dimension n − k + 1 and minimum distance k. Rescaling coordinate i by vi−1 yields an ordinary Reed–Solomon code of the same dimension and preserves Hamming distances. 10

2.2

Shamir secret sharing

Definition 3 (Shamir secret sharing). Let α ∈ (F∗p )n have distinct coordinates. The (n, k, α)-Shamir scheme with n parties and reconstruction threshold k is defined as follows. 1. Sharing: to share s ∈ Fp , shareα (s) samples Z1 , . . . , Zk−1 independent and uniform in Fp , forms P j P (X) = s + k−1 j=1 Zj X , and gives party i the share P (αi ). 2. Reconstruction: any k shares determine s by Lagrange interpolation. The shares of the zero secret are uniform on C0 = GRSα,α (n, k − 1), and the shares of secret s are uniform on s1 + C0 . For every secret, any k − 1 shares are independent uniform field elements, so they reveal nothing about the secret.

2.3

Local leakage resilience

Definition 4 (m-bit local leakage). For a positive integer m, an m-bit local leakage function is a tuple τ = (τ1 , . . . , τn ) of maps τi : Fp → {0, 1}m . For x ∈ Fnp write τ (x) = (τ1 (x1 ), . . . , τn (xn )). Definition 5 (Leakage resilience of a code). A linear code C ⊆ Fnp is ε-resilient to m-bit local leakage if SD τ (U C ), τ (U Fnp ) ≤ ε for every m-bit local leakage function τ . We call this statistical distance the leakage distance. Thus local leakage cannot distinguish a uniform codeword from a vector of independent uniform field elements. Definition 6 (Leakage resilience of Shamir sharing). The (n, k, α)-Shamir scheme is ε-resilient to m-bit local leakage if SD τ (shareα (s)), τ (shareα (s′ )) ≤ ε for every m-bit local leakage function τ and all secrets s, s′ ∈ Fp . When no error bound is stated, resilience means that the leakage distance is negligible in n, namely smaller than every inverse polynomial for sufficiently large n. Remark 1 (Code monotonicity). Translations can be absorbed into the leakage maps, and statistical distance is convex in its first argument [BDIR18, BDIR21]. Hence if C ⊆ Fnp is ε-resilient to m-bit local leakage, the same bound against U Fnp holds for every mixture of uniform distributions on translates of C; in particular, every linear code containing C is ε-resilient. Remark 2 (Threshold monotonicity). Increasing the reconstruction threshold preserves leakage resilience [BDIR18, BDIR21]: if the (n, k, α)-Shamir scheme is ε-resilient to m-bit local leakage, so is the (n, k ′ , α)-scheme for every k ≤ k ′ ≤ n. Lemma 1 (Equivalence of code and Shamir leakage resilience). Let α ∈ (F∗p )n have distinct coordinates, let v ∈ (F∗p )n , and let 2 ≤ k ≤ n. Resilience to m-bit local leakage of GRSα,v (n, k − 1) and of the (n, k, α)-Shamir scheme are equivalent up to a linear factor in the error. More precisely, code error ε gives Shamir error at most 2ε, and Shamir error ε gives code error at most (n − k + 1)ε. Proof. Code to Shamir is the reduction of [BDIR18, BDIR21]. Coordinate scalings by nonzero elements can be absorbed into the leakage maps, so we may take C0 = GRSα,α (n, k − 1). If C0 is ε-resilient, applying its guarantee to the maps x 7→ τi (x + s) gives SD τ (shareα (s)), τ (U Fnp ) ≤ ε for every secret s, and the triangle inequality gives Shamir error at most 2ε. For the zero-secret code C0 , this direction holds for any leakage class closed under coordinatewise translations. For arbitrary multipliers, closure under nonzero coordinate scalings is also needed.

Conversely, suppose the Shamir scheme is ε-resilient at threshold k, hence at every larger threshold by Remark 2. For k − 1 ≤ r < n and multipliers v, put C = GRSα,v (n, r) and C ′ = GRSα,w (n, r + 1) with wi = vi /αi . At threshold r + 1, multiplying a sharing of zero coordinatewise by w gives U C , and doing the same to a sharing of a uniform secret gives U C ′ , since all r + 1 coefficients are then independent and uniform. Hence, with σi (x) = τi (wi x) and sharings at threshold r + 1, convexity gives 1 X SD τ (U C ), τ (U C ′ ) ≤ SD σ(shareα (0)), σ(shareα (s)) ≤ ε. p s∈F p

Starting with the given multipliers v, these steps form the nested chain GRSα,v (n, k − 1) ⊆ GRSα,v/α (n, k) ⊆ · · · ⊆ GRSα,v/α n−k+1 (n, n) = Fnp , where division and powers of the multipliers are coordinatewise. The triangle inequality over the n − k + 1 steps gives code error at most (n − k + 1)ε.

2.4

Fourier analysis and Gowers norms

For f : Fp → C, write ∥f ∥q = (Ex |f (x)|q )1/q for 1 ≤ q < ∞ and ∥f ∥∞ = maxx |f (x)|. Definition 7 (Fourier transform). Let ep (t) = exp(2πit/p) and χa (x) = ep (ax) for a ∈ Fp ; the index a is a frequency. The normalized Fourier transform is fb(a) = Ex [f (x)χa (x)]. For vectors, P χy (x) = ep ( i yi xi ) and fb(y) = Ex∈Fnp [f (x)χy (x)]. Orthogonality of the characters gives Fourier inversion and Parseval’s identity: X

f (x) =

∥f ∥22 =

fb(a)χa (x),

a∈Fp

Averages over a linear code. (fi : Fp → C)i∈A , write

|fb(a)|2 .

a∈Fp

For a linear code C ⊆ Fnp , a set A ⊆ [n], and functions f A = ΓC (f A ) = EX∼UC

fi (Xi ) ,

i∈A

with ΓC (f ∅ ) = 1. We use the Poisson summation formula for a linear code [BDIR21, Lemma 4.16]. Lemma 2 (Dual-code formula). Let C ⊆ Fnp be a linear code. For every x ∈ Fnp , X pn 1[x ∈ C] = χy (x). |C| ⊥ y∈C

The identity follows from Fourier inversion and EX∼UC [χy (X)] = 1[y ∈ C ⊥ ]. Definition 8 (Gowers norms). For a positive integer t and f : Fp → C, t

∥f ∥2U t = Ex,h1 ,...,ht ∈Fp

C |ω| f (x + ω · h) ,

ω∈{0,1}t

where h = (h1 , . . . , ht ), C denotes complex conjugation, |ω| = ω1 + · · · + ωt , and the t + 1 averaging variables are independent and uniform. The same definition applies to functions on any finite abelian group, in particular on FJp for a finite set J. 12

The conjugations make these averages real and nonnegative; the U 2 and U 3 norms average products of four and eight translated values. For t ≥ 2, ∥·∥U t is a norm, and |Ef | = ∥f ∥U 1 ≤ P 4 b ∥f ∥U 2 ≤ · · · ≤ ∥f ∥∞ [TV06]. Fourier orthogonality gives ∥f ∥4U 2 = a∈Fp |f (a)| , and with ∆h f (x) = f (x + h)f (x) the definition gives ∥f ∥8U 3 = Eh ∥∆h f ∥4U 2 .

2.5

List decoding and list recovery

Definition 9 (List size). For a code D ⊆ Fnp , an integer radius 0 ≤ R ≤ n, and an input-list size ℓ ≥ 1, ListD (R, ℓ) = max {y ∈ D : |{i : yi ∈ Si }| ≥ n − R} . S1 ,...,Sn ⊆Fp |Si |≤ℓ

Write ListD (R) = ListD (R, 1). Thus ListD (R, ℓ) ≤ L means that every choice of input lists admits at most L codewords agreeing with them in at least n − R coordinates (list recovery). For ℓ = 1, ListD (R) = maxy∈Fnp |{v ∈ D : dH (v, y) ≤ R}| (list decoding). We use only these counting bounds, not decoding algorithms. We use a field-size-independent list-recovery bound supplied by Jeronimo [Jer26, Theorem 1.1], building on the decoding method of Brakensiek et al. [BCP+ 26], and also by Dao, Kominers, and Thaler [DKT26, Theorem G.2]. For growing leakage alphabets, we need the dependence on the input-list size explicit. The following quantitative form is derived from Jeronimo’s proof in Section A and from DKT’s finite estimates in Section B. Theorem 4 (Reed–Solomon list recovery, derived from [Jer26, DKT26]). Fix 0 < ζ < 1. There is a constant cζ ≥ 1 such that, for every integer ℓ ≥ 1, every n ≥ cζ ℓ9/ζ , every prime p > n, and every integer 1 ≤ h ≤ (1 − ζ)n, 3/ζ

ListGRSα,v (n,h) ⌊n − h − ζn⌋ , ℓ ≤ ncζ ℓ

The exponent is independent of p, so there is no upper bound on the field size; the gap ζ is fixed, while ℓ may grow subject to the length condition. The statement for ordinary Reed–Solomon codes gives the GRS version by replacing each input list Si with vi−1 Si , which preserves list sizes and agreement counts. For C = GRSα,v (n, k − 1) with 2 ≤ k ≤ n, the dual has dimension n − k + 1, which is at most (1 − ζ)n when k − 1 ≥ ζn, and the radius in the theorem is then exactly ⌊k − 1 − ζn⌋. Hence, whenever k − 1 ≥ ζn and n ≥ cζ ℓ9/ζ , 3/ζ

ListC ⊥ ⌊k − 1 − ζn⌋ , ℓ ≤ ncζ ℓ

Taking ℓ = 1 gives the corresponding list-decoding bound. All later estimates are uniform in the leakage maps, so no union bound over maps is needed. For comparison, [BCP+ 26, Corollary 5.1] gives list size pO(1) at fixed rate and gap when p ≥ Cn, which also suffices for our arguments when log p = o(n); Theorem 4 removes this upper restriction and allows every prime p > n.

An orthogonal decomposition of the leakage distance

This section writes the leakage distance as a norm of one function of the outputs and decomposes that function into orthogonal components indexed by sets of coordinates; Section 3.4 specializes to one-bit leakage. 13

3.1

Efron–Stein decomposition

Throughout this subsection, Ω = ni=1 Ωi is a product of finite sets and µ = ni=1 µi is a product probability measure on Ω in which every µi has full support. For f, g : Ω → C write ⟨f, g⟩µ = Eµ [f g] and ∥f ∥q,µ = (Eµ |f |q )1/q for 1 ≤ q < ∞; we omit the measure when it is clear from context. Q

Definition 10 (Efron–Stein decomposition [O’D14, Chapter 8]). Every f : Ω → C has a unique expansion X f= f =A A⊆[n]

in which f =A depends only on the coordinates in A and Exi ∼µi [f =A (x)] = 0 for every i ∈ A and every fixing of the other coordinates. The components are pairwise orthogonal in L2 (Ω, µ); in particular X f =∅ = Eµ [f ] and ∥f ∥22,µ = ∥f =A ∥22,µ . A⊆[n]

Concretely, choose for each i an orthonormal basis of L2 (Ωi , µi ) that contains the constant function 1. Their products, one factor per coordinate, form an orthonormal basis of L2 (Ω, µ), and f =A is the part of the expansion of f whose factors are nonconstant at exactly the coordinates in A [O’D14, Chapter 8]. Equivalently, let Eiµ average coordinate i according to µi , leaving the others fixed. Then Y Y f =A = (Id − Eiµ ) Eiµ f. i∈A

i∈A /

On Fnp with the uniform measure and the character basis this reads as follows [O’D14, Proposition 8.36]; see also [KMN22, Proposition 7]. Lemma 3 (Fourier form of the components). For every f : Fnp → C and A ⊆ [n], under the uniform measure on Fnp , X f =A = fb(y) χy . y∈Fn p : supp(y)=A

Leakage enters through conditional expectation. Definition 11 (Markov operator [KMN22, Section 4.4]). Let (X, Y ) be a pair of random variables on finite sets Ω × Ω′ with marginal distributions µ and ν. Its Markov operator T : L2 (Ω, µ) → L2 (Ω′ , ν) is (Tf )(y) = E[f (X) | Y = y], y ∈ supp(ν). The operator T is linear, T1 = 1, and Eν [Tf ] = Eµ [f ]. If (Xi , Yi )i∈[n] are independent pairs with Markov operators Ti , then the Markov operator of X = (Xi )i and Y = (Yi )i is the tensor N Q Q product T = i Ti : for f (x) = i fi (xi ) one has (Tf )(y) = i (Ti fi )(yi ). We use two standard properties [KMN22, Proposition 5]. Lemma 4 (Markov operators and components). Let T be the Markov operator of a pair (X, Y ) with marginal distributions µ, ν. 1. ∥Tf ∥2,ν ≤ ∥f ∥2,µ for every f ∈ L2 (Ω, µ). 2. If (X, Y ) is a product of independent pairs as above, then (Tf )=A = T(f =A ) for every f and every A ⊆ [n], where the components of f are taken under µ and those of Tf under ν.

Proof. Conditional Jensen gives ∥Tf ∥22,ν = EY E[f (X) | Y ]

≤ EY E[|f (X)|2 | Y ] = ∥f ∥22,µ .

For independent coordinate pairs, averaging coordinate i before or after applying its Markov operator gives the same constant: TEiµ = Eiν T. Applying this identity to the product formula for the components above gives T(f =A ) =

(Id − Eiν )

i∈A

3.2

Eiν Tf = (Tf )=A .

i∈A /

The leakage distance as a norm on the output space

Fix a linear code C ⊆ Fnp and local maps τi : Fp → Bi into finite sets; m-bit leakage is the case Bi = {0, 1}m . Replacing each Bi by the image τi (Fp ), we may assume that every output symbol occurs, so that νi (b) = Pr[τi (UFp ) = b] > 0

for all b ∈ Bi ,

ν(b) =

n Y

νi (bi ).

i=1

Thus ν is the reference leakage distribution, namely the distribution of τ (U Fnp ). Let Ti be the Markov operator of Definition 11 for the pair UFp , τi (UFp ) , and T the one for U Fnp , τ (U Fnp ) ; N the pairs are independent, so T = i Ti . Norms of functions on the inputs are taken under the uniform measure, and norms of functions on the outputs under ν, or under νi for a function of one coordinate. The object we decompose is the normalized indicator fC : Fnp → R, fC (x) =

pn Pr[U C = x] = 1[x ∈ C], Pr[U Fnp = x] |C|

the likelihood ratio of the two input distributions. Its conditional mean given the leakage is the likelihood ratio of the two leakage distributions. Lemma 5 (Leakage probabilities and statistical distance). For every b ∈ Pr[τ (U C ) = b] = ν(b) (TfC )(b),

i Bi ,

Pr[τ (U Fnp ) = b] = ν(b).

Consequently,

SD τ (U C ), τ (U Fnp ) =

1 ∥TfC − 1∥1,ν . 2

Proof. Write U = U Fnp . Since Pr[U C = x] = p−n fC (x), Pr[τ (U C ) = b] =

p−n fC (x) = Pr[τ (U ) = b] E fC (U ) τ (U ) = b .

x : τ (x)=b

The second factor is (TfC )(b) by definition, and the first is ν(b) because the coordinates of τ (U ) are independent with distributions νi . Substituting both identities into the definition of statistical P distance gives 12 b ν(b) |(TfC )(b) − 1|.

3.3

The orthogonal components

For the rest of this section we assume that C ⊥ has minimum distance at least k. This is the only property of C used below; for C = GRSα,v (n, k − 1) it holds because C ⊥ is a GRS code of dimension n − k + 1. Since T is a product Markov operator, Lemma 4 gives (TfC )=A = T(fC=A ), so it remains to identify the input components. By Lemma 2, fbC (y) = 1[y ∈ C ⊥ ] for every y ∈ Fnp , and Lemma 3 then gives X X fC=A = fbC (y) χy = χy . (1) y∈Fn p : supp(y)=A

y∈C ⊥ : supp(y)=A

In particular fC=∅ = 1, and fC=A = 0 whenever 1 ≤ |A| < k, because every nonzero dual word has weight at least k. Since T1 = 1, X

TfC − 1 =

T(fC=A ),

A⊆[n] : |A|≥k

and the summands are pairwise orthogonal in L2 (ν), being the components of TfC under ν (Lemma 4 and Definition 10). List decoding of C ⊥ controls squared L2 norms of components, which add across supports by orthogonality (Sections 4 and 6); Gowers-norm estimates control L1 norms one support at a time (Sections 5 and 6). The next proposition allows any cutoff between the two regimes, and Corollary 1 records the extreme cutoffs. Proposition 1 (Splitting the leakage distance). For every integer r0 with k − 1 ≤ r0 ≤ n,

SD τ (U C ), τ (U Fnp ) ≤

1/2 1 X 1 X ∥T(fC=A )∥22 + ∥T(fC=A )∥1 . 2 k≤|A|≤r 2 |A|>r 0

Proof. Split the decomposition of TfC − 1 at |A| = r0 and apply the triangle inequality in L1 (ν) to the two parts. For the supports of size at most r0 , Cauchy–Schwarz gives ∥ · ∥1 ≤ ∥ · ∥2 , and by orthogonality the squared L2 norm of the sum is the sum of the squared norms. For the larger supports, the triangle inequality bounds the L1 norm of the sum by the sum of the L1 norms. Lemma 5 supplies the factor 12 . The extreme cutoffs r0 = n and r0 = k − 1 give the following. Corollary 1 (The two extreme cutoffs). The following bounds hold.

SD τ (U C ), τ (U Fnp ) ≤

1/2 1 X 1 X ∥T(fC=A )∥22 and SD τ (U C ), τ (U Fnp ) ≤ ∥T(fC=A )∥1 . 2 |A|≥k 2 |A|≥k

The large-support bound has an exact form for arbitrary output alphabets in terms of centered output indicators. Lemma 6 (Output-indicator form of the components). For i ∈ [n] and b ∈ Bi , let fi,b (x) = 1[τi (x) = b] − νi (b). These functions have mean zero and ∥fi,b ∥∞ ≤ 1. For every A ⊆ [n], " X

∥T(fC=A )∥1,ν = bA ∈

Q i∈A

EX∼UC Bi

# Y i∈A

fi,bi (Xi )

Proof. Expanding the product formula in Section 3.1 gives (TfC )=A =

(−1)|A\S|

S⊆A

Eiν TfC .

i∈S /

Each term averages all output coordinates outside S. By Lemma 5, each marginal of TfC is the corresponding marginal leakage probability divided by its reference probability. Hence (TfC=A )(bA ) =

(−1)|A\S|

S⊆A

= EX∼UC

Pr[τ S (U C ) = bS ] Q i∈S νi (bi )

Y 1[τi (Xi ) = bi ]

i∈A

νi (bi )

−1

EX∼UC [

i∈A fi,bi (Xi )]

i∈A νi (bi )

Taking the L1 (ν) norm cancels the denominator and proves the identity. No lower bound on the positive probabilities νi (b) is needed; unused output symbols have fi,b = 0 and may also be included in the sum.

3.4

One-bit leakage

Now let τi : Fp → {0, 1}. Each L2 (νi ) is then spanned by 1 and one centered function, so every output component is a scalar multiple of a single product function; the scalar is an average over the code of centered leakage functions. Put θi = Ex [τi (x)]. If τi is nonconstant, so that 0 < θi < 1, define τi (x) − θi gi (x) = p , θi (1 − θi )

fi (x) = 2 τi (x) − θi ;

if τi is constant, put gi = fi = 0. Both functions have mean zero, ∥gi ∥2 ≤ 1 with equality for nonconstant τi , and ∥fi ∥∞ ≤ 2. Write g A = (gi )i∈A and f A = (fi )i∈A , and recall that Q ΓC (hA ) = EX∼UC i∈A hi (Xi ) for functions hi : Fp → C. Lemma 7 (Norms of the binary components). For every A ⊆ [n], ∥T(fC=A )∥22 = |ΓC (g A )|2

and

∥T(fC=A )∥1 = |ΓC (f A )|.

Both sides vanish when 1 ≤ |A| < k, and when A contains a coordinate whose map is constant. Moreover, ∥Ti χa ∥22 = |gbi (a)|2 for every i and every a ̸= 0. Proof. If τi is constant, then L2 (νi ) consists of the constant functions, so every output component with i ∈ A vanishes, as do ΓC (g A ) and ΓC (f A ) by the convention gi = fi = 0; also Ti χa = Ex [χa (x)] = 0 = gbi (a) for a ̸= 0. We mayptherefore assume that every τi is nonconstant. Q For an output bit put ϕi (b) = (b−θi )/ θi (1 − θi ), so that gi = ϕi ◦τi , and let ϕA (b) = i∈A ϕi (bi ). The functions 1, ϕi form an orthonormal basis of L2 (νi ), so the product basis of Section 3.1 contains exactly one function nonconstant precisely on A, namely ϕA , and the component of TfC on A is ⟨TfC , ϕA ⟩ν ϕA . By Lemma 5, ν(b)(TfC )(b) = Pr[τ (X) = b] for X ∼ UC , so

⟨TfC , ϕA ⟩ν = EX∼UC ϕA (τ (X)) = ΓC (g A ). Together with (TfC )=A = T(fC=A ) this gives T(fC=A ) = ΓC (g A ) ϕp A , and ∥ϕA ∥2,ν = 1 proves the first identity. For the second, independence under ν and Eνi |ϕi | = 2 θi (1 − θi ) give ∥T(fC=A )∥1,ν = |ΓC (g A )|

Y q

2 θi (1 − θi ) = |ΓC (f A )|,

i∈A

since fi = 2 θi (1 − θi ) gi . Vanishing for 1 ≤ |A| < k is (1) together with the dual-distance assumption. Finally, for a = ̸ 0 the function Ti χa has mean zero and is therefore a multiple of ϕi , with coefficient ⟨Ti χa , ϕi ⟩νi = Ex [χa (x)gi (x)] = gbi (−a). Since gi is real, |gbi (−a)| = |gbi (a)|. Substituting the lemma into Proposition 1 gives the form of the decomposition used for one-bit leakage. Proposition 2 (Splitting small and large supports). For every integer r0 with k − 1 ≤ r0 ≤ n,

SD τ (U C ), τ (U Fnp ) ≤

1/2 1 X 1 X + |ΓC (g A )|2 |ΓC (f A )|. 2 k≤|A|≤r 2 |A|>r 0

(2)

By Lemma 7, supports containing a constant-map coordinate contribute nothing to (2); this is how constant maps are handled from now on.

Dual-code list recovery and resilience above half

This section proves that list recovery of C ⊥ with input lists of size Q − 1 implies resilience to leakage with Q output symbols per coordinate; for one-bit leakage the hypothesis is ordinary list decoding. Lemma 8 bounds each component of Section 3 by a weighted count of dual codewords, Lemma 11 replaces the weights by list indicators, and Theorem 6 follows at the end. Theorem 5 (List recovery implies leakage resilience). For every integer Q ≥ 2 there is a constant 0 < ηQ ≤ 1 − 1/(16Q2 ), with η2 = 1/2, such that the following holds. Let p ≥ 16Q be prime, let C ⊆ Fnp be a linear code, and let R be an integer with n/2 < R < n such that every nonzero word of C ⊥ has weight at least R + 1. Then for every tuple of local maps τi : Fp → Bi with |Bi | ≤ Q,

SD τ (U C ), τ (U Fnp ) ≤

1 R−n/2 q η ListC ⊥ (R, Q − 1). 2 Q

For Q = 2 the conclusion holds for every odd prime p. The constant ηQ is given explicitly in Lemma 9. The theorem uses only the dual distance of C; no MDS property is needed. Throughout this section, C ⊆ Fnp is a linear code whose dual has minimum distance at least k, and fC , T, Ti , ν, νi are as in Section 3 for local maps τi : Fp → Bi in which every output symbol occurs. We write qi = |Bi | and assume qi ≤ Q for a fixed integer Q ≥ 2.

4.1

Bounding the leakage components

We apply the leakage on only k − 1 coordinates of a support. The dual distance ensures that the remaining coordinates distinguish the contributing dual words, so their characters stay orthogonal; applying the leakage on those coordinates afterwards can only decrease the L2 norm. Lemma 8 (Bounding a leakage component). Let A ⊆ [n] have size at least k, and let J ⊆ A have size |A| − k + 1. Then X Y ∥T(fC=A )∥22 ≤ ∥Ti χyi ∥22 . y∈C ⊥ : supp(y)=A i∈A\J

Proof. Put I = A \ J, so |I| = k − 1, and write νI = i∈I νi . Since fC=A depends only on the N N coordinates in A, we may regard T as TI ⊗ TJ with TI = i∈I Ti and TJ = i∈J Ti . First, fix bI and apply Lemma 4(1) to xJ 7→ (TI fC=A )(xJ , bI ); averaging over bI ∼ νI gives Q

∥T(fC=A )∥22 ≤ TI (fC=A ) 2 , where the norm on the right is under νI on the outputs of I and the uniform measure on xJ ∈ FJp . Second, expanding fC=A by (1) and applying TI factor by factor, X

(TI fC=A )(xJ , bI ) =

χyJ (xJ )

y∈C ⊥ : supp(y)=A

(Ti χyi )(bi ).

i∈I

Two dual words in the sum that agree on J differ on at most |I| = k − 1 coordinates, hence coincide by the dual-distance assumption. The characters χyJ are therefore distinct, and Parseval in xJ gives 2

TI (fC=A ) 2 = EbI ∼νI

|(Ti χyi )(bi )|2 =

y∈C ⊥ : supp(y)=A i∈I

∥Ti χyi ∥22 ,

y∈C ⊥ : supp(y)=A i∈I

by independence of the outputs under νI . The bound leaves k − 1 factors of the form ∥Ti χa ∥22 . We need two facts about them: their sum over nonzero frequencies is at most Q − 1, which will let us replace the weights by lists of size Q − 1; and each is at most ηQ < 1, which supplies the decay. Lemma 9 (Fourier weight after leakage). For every i and every a ∈ Fp , with norms of Ti χa taken under νi , X

∥Ti χa ∥2,νi = ∥Ti χ−a ∥2,νi ≤ 1,

Ti χ0 = 1,

∥Ti χa ∥22,νi = qi − 1.

a̸=0

If p ≥ 16Q, or if Q = 2 and p is odd, then for every a ̸= 0, ∥Ti χa ∥22 ≤ ηQ := min

nQ − 1

, cos2

π o 1 ≤1− . 8Q 16Q2

In particular η2 = 1/2. Proof. Let Si,b = {x ∈ Fp : τi (x) = b}, so νi (b) = |Si,b |/p and (Ti χa )(b) = 1d Si,b (−a)/νi (b). Hence ∥Ti χa ∥22 =

2 X |1d Si,b (a)| b∈Bi

νi (b)

∥Ti χa ∥22 =

a∈Fp

X ∥1Si,b ∥22 b∈Bi

νi (b)

= qi ,

by Parseval. Removing the zero frequency, where Ti χ0 = 1, gives the sum over a = ̸ 0. The symmetry follows from χ−a = χa , and ∥Ti χa ∥2 ≤ 1 from |χa | = 1. For odd p, the frequencies a and −a are P distinct when a = ̸ 0, so 2∥Ti χa ∥22 ≤ a′ ̸=0 ∥Ti χa′ ∥22 ≤ Q − 1. This is the first term of the minimum, and for Q = 2 it is the whole bound. Now suppose p ≥ 16Q and fix a = ̸ 0. Write zb = (Ti χa )(b) = |zb |eiϕb , with ϕb arbitrary when zb = 0. Since |zb | ≤ 1, ∥Ti χa ∥22 =

X b

νi (b)|zb |2 ≤

νi (b)|zb | =

1 X Re e−iϕτi (x) χa (x) . p x∈F p

The values χa (x) are the p equally spaced points of the unit circle. Around each of the at most Q angles ϕb take the arc of angular radius π/(4Q); each arc contains at most p/(4Q) + 1 of the points, so their union contains at most p/4 + Q ≤ 3p/8 since p ≥ 16Q. Thus at least half the points lie outside every arc, where the real part above is at most cos(π/(4Q)); elsewhere it is at most one. Hence 1 + cos(π/(4Q)) π ∥Ti χa ∥22 ≤ = cos2 . 2 8Q Finally, sin u ≥ 2u/π for 0 ≤ u ≤ π/2 gives sin2 (π/(8Q)) ≥ 1/(16Q2 ). From now on we assume p ≥ 16Q, or Q = 2 and p odd. Note that ηQ < 1 bounds individual characters, not every function of mean zero: a function of τi (x) alone is fixed by Ti , which is why Lemma 8 first reduces to a sum of products of character norms.

4.2

Applying list recovery

We keep j of the k − 1 factors in Lemma 8 and bound the rest by ηQ . An extremal argument then replaces the retained weights by indicators of input lists, so the sum counts dual words with at least j agreements. Lemma 10 (Replacing weights by list indicators). Let Ω be a finite set and 2 ≤ Q ≤ |Ω| + 1 an integer. Let P (w1 , . . . , wn ) be a nonnegative linear combination of terms of the form Y

wi (ai ),

S ⊆ [n],

ai ∈ Ω.

i∈S

For all functions wi : Ω → [0, 1] with a∈Ω wi (a) ≤ Q − 1, there are sets Vi ⊆ Ω of size Q − 1 such that P (w1 , . . . , wn ) ≤ P (1V1 , . . . , 1Vn ). P

Proof. Fix all weights except wi . Each term contains at most one factor from coordinate i, so P P P has the form c0 + a∈Ω ca wi (a) with all ca ≥ 0. Subject to 0 ≤ wi (a) ≤ 1 and a wi (a) ≤ Q − 1, this is maximized by putting weight one on the Q − 1 largest coefficients and zero elsewhere; let Vi be the set of those Q − 1 indices. Replacing wi by 1Vi does not decrease P . Repeating for each coordinate in turn gives the claim. Lemma 11 (A list-recovery bound for the components). For every integer 1 ≤ j < k with j ≤ n, ∥T(fC=A )∥22 ≤ ηQk−1−j ListC ⊥ (n − j, Q − 1).

X A⊆[n] : |A|≥k

Proof. Let A range over supports of size at least k. For each such A fix IA ⊆ A with |IA | = k − 1 and JA ⊆ IA with |JA | = j. Apply Lemma 8 with J = A \ IA . Every word with support A is nonzero at each coordinate of A, so Lemma 9 bounds each of the k − 1 − j factors indexed by IA \ JA by ηQ : P

X A

∥T(fC=A )∥22 ≤

∥Ti χyi ∥22 ≤ ηQk−1−j

A y∈C ⊥ : supp(y)=A i∈IA

∥Ti χyi ∥22 .

A y∈C ⊥ : supp(y)=A i∈JA

Regard the last double sum as a function P of the weights wi (a) = ∥Ti χa ∥22 , a ∈ F∗p : it is a sum Q of monomials i∈JA wi (yi ), one for each dual word, each with coefficient one. Lemma 10 applies to P with Ω = F∗p , since Q − 1 ≤ p − 1 and Lemma 9 gives the constraints on the weights. This 20

yields lists Vi ⊆ F∗p of size Q − 1 with P (w) ≤ P (1V1 , . . . , 1Vn ). With indicator weights, a monomial equals one exactly when its dual word agrees with the lists on all j coordinates of JA , and each dual word occurs once because its support determines A. With input lists Si = Vi for every i, each counted word therefore has at least j agreements, so P (1V1 , . . . , 1Vn ) =

1[yi ∈ Vi ] ≤ ListC ⊥ (n − j, Q − 1),

A y∈C ⊥ : supp(y)=A i∈JA

which proves the lemma. Proof of Theorem 5. Set k = R + 1 and j = n − R. Then 1 ≤ j < k, k − 1 − j = 2R − n, and n − j = R. Corollary 1 and Lemma 11 give

SD τ (U C ), τ (U Fnp ) ≤

1/2 1 R−n/2 q 1 X ListC ⊥ (R, Q − 1). ∥T(fC=A )∥22 ≤ ηQ 2 |A|≥k 2

Corollary 2 (List decoding implies one-bit leakage resilience). Let p be an odd prime, C ⊆ Fnp a linear code, and R an integer with n/2 < R < n such that every nonzero word of C ⊥ has weight at least R + 1. Then, for every tuple of one-bit maps,

SD τ (U C ), τ (U Fnp ) ≤

1 n/2−R q 2 ListC ⊥ (R). 2

Proof. Take Q = 2 in Theorem 5; then η2 = 1/2 and ListC ⊥ (R, 1) = ListC ⊥ (R). We now derive the above-half result for GRS codes from the transfer and Theorem 4. Theorem 6 (Logarithmic leakage above half). Fix 0 < δ < 1/2. There are constants cδ > 0 and n0 (δ) such that, for n ≥ n0 (δ) and every prime p > n, every GRS code over Fp of length n and rate at least 1/2 + δ is exp(−cδ n1−δ/12 )-resilient to ⌊(δ/24) log2 n⌋-bit local leakage. Proof of Theorem 6. Fix an integer 1 ≤ m ≤ (δ/24) log2 n. Write C = GRSα,v (n, k − 1); the fullspace code is immediate, so assume k − 1 < n. We prove the code estimate under the slightly weaker condition k ≥ (1/2 + δ)n, which covers both codes of rate at least 1/2 + δ and the zero-secret codes of the Shamir schemes in the theorem. Throughout, n is sufficiently large depending only on δ. Put Q = 2m ≤ nδ/24 and R = ⌊k − 1 − (δ/2)n⌋. Since k ≥ (1/2 + δ)n, we have R − n/2 ≥ δn/2 − 2 ≥ δn/4; also R < k and p > n ≥ 16Q. The dual code has dimension n − k + 1 and minimum distance k ≥ R + 1, so Theorem 5 applies. We use the specialization of Theorem 4 to dual GRS codes stated after it, with gap δ/2 and input-list size Q − 1: its hypotheses hold since k − 1 ≥ δn/2 and cδ/2 (Q − 1)18/δ ≤ cδ/2 n3/4 ≤ n, and its radius is exactly R. Consequently log ListC ⊥ (R, Q − 1) ≤ cδ/2 Q6/δ log n ≤ cδ/2 n1/4 log n. With ηQ ≤ 1 − 1/(16Q2 ), the transfer gives

SD τ (U C ), τ (U Fnp ) ≤

cδ/2 1/4 δn 1 δn 1 exp − + n log n ≤ exp − , 2 64Q2 2 2 128Q2

where the last step holds for all sufficiently large n, because Q2 ≤ nδ/12 and δ/12 + 1/4 < 1 give cδ/2 Q2 n1/4 log n ≤ δn/64. For Shamir sharing, apply Lemma 1 to the zero-secret code; its factor two cancels the prefactor 1/2. Thus cδ = δ/128 suffices in both cases, and 22m ≤ nδ/12 gives the stated bound. 21

Structured leakage at constant-rate thresholds

This section introduces the second tool, an iterated Cauchy–Schwarz inequality of generalized von Neumann type tailored to MDS systems of linear forms (Lemma 12 and Corollary 3). It bounds an average of a product of functions along the forms of a GRS code by a product of Gowers norms, and for an MDS system it retains linearly many such norms at every constant rate. We apply it on its own, through the L1 bound of Proposition 1 with r0 = k − 1, to prove Theorem 7: resilience to quadratic-residue leakage and to almost all Θc (log2 p)-bit local leakage functions at every positive constant rate. Section 6 combines the same inequality with the list-decoding estimates of Section 4. Nguyen [Ngu24] relates leakage security to Gowers norms and bounds these norms for quadraticresidue and random leakage, but retains a single Gowers-norm factor, so the bounds need an exponentially large field at constant rate. The MDS von Neumann inequality supplies linearly many factors from the same local estimates, which allows fields of size just above n. Recall that τQR (x) = 1 if x is a square in Fp , including zero, and τQR (x) = 0 otherwise. Theorem 7 (Structured leakage at constant rate). Fix 0 < c < 1. There are constants ηc , ac , bc > 0 and n0 (c) such that, for n ≥ n0 (c) and every prime p > n, the following hold for GRS codes C = GRSα,v (n, k − 1) with k ≥ cn. 1. For τi (x) = τQR (ai x + bi ), where ai ∈ F∗p and bi ∈ Fp ,

SD τ (U C ), τ (U Fnp ) ≤ exp(−ac n log p). √ 2. For every integer 1 ≤ m ≤ ηc log2 p, all but an exp(−bc p) fraction of tuples τ = (τi : Fp → {0, 1}m )i∈[n] satisfy SD τ (U C ), τ (U Fnp ) ≤ exp(−ac n log p) simultaneously for every such code C. Both conclusions hold for (n, k)-Shamir sharing between every pair of secrets, with the same error bounds. The product bound for Gowers norms, together with standard concentration estimates (Lemma 13), gives resilience to almost all local leakage functions in part 2. This does not assert resilience to every local leakage function as in Definition 5. Remark 3 (Affine changes of the leakage input). Replacing f (x) by f (ax + b) with a = ̸ 0 changes no Gowers norm: substitute x 7→ ax + b and ht 7→ aht in the definition. This gives the affine form of quadratic-residue leakage in Theorem 7, and likewise every tuple of random maps that satisfies the Gowers-norm event below remains successful after coordinatewise affine changes of input. The changes may depend on the public parameters but are fixed before the codeword is sampled. For Shamir sharing with k ≥ cn, Lemma 1 applied to C0 = GRSα,α (n, k − 1), together with the translation closure in Remark 3, gives the code bounds with an extra factor two; we choose the constant ac below small enough to absorb it. Section 5.2 turns a uniform bound on the local Gowers norms into a leakage bound with explicit finite parameters; Sections 5.3 and 5.4 supply the local bounds for the two classes; Section 5.5 extracts a sufficient field size at square-root thresholds, where the attack discussed at the end of that subsection shows that some field-size condition is needed.

5.1

A product bound for Gowers norms

Iterated Cauchy–Schwarz is a standard tool in additive combinatorics and higher-order Fourier analysis [Gow01, TV06, GT10]. We use the following consequence of Manners’s generalized von Neumann inequality for vector-valued linear maps [Man21, Section 3.1]. Grouping several forms into one map gives a product of Gowers norms. We include a self-contained proof of the form used below. Fix a prime p, integers k ≥ 2 and r ≥ 1, and write V = Fk−1 p . Definition 12 (Linear forms and systems of forms). A linear form on V is a map L(z) = k−1 a=1 ca za , with c ∈ Fk−1 . A system of linear forms is an ordered tuple (L , . . . , L ). A subfamily is independent 1 r p if its coefficient vectors are linearly independent over Fp . The system is MDS (maximum-distanceseparable) if every subfamily of at most k − 1 forms is independent. An affine-linear form is a map ψ = b + L, with b ∈ Fp and L linear. For a system Ψ = (ψi )ri=1 , where ψi = bi + Li , independence and the MDS property always refer to the linear parts Li . P

Definition 13 (Average along a system of forms). For functions f = (f1 , . . . , fr ), with fi : Fp → C, define " # ΛΨ (f ) = Ez∈V

r Y

fi (ψi (z)) .

i=1 j−1 For C = GRSα,v (n, k − 1), the forms Li (z) = vi k−1 give a uniform codeword when z j=1 zj αi is uniform in V . They form an MDS system by the Vandermonde determinant. More generally, independent linear parts give independent uniform evaluations, even after adding constants. We use ⊔ for a disjoint union and regard the empty family as independent.

Lemma 12 (A product of Gowers norms). Let Ψ = (bi + Li )ri=1 be a system on V , and let fi : Fp → C. Suppose [r] = J ⊔ I1 ⊔ · · · ⊔ It , with t ≥ 2, and the linear parts indexed by Ia ∪ J are independent for every a. Then |ΛΨ (f )| ≤

∥fj ∥U t

j∈J

∥fi ∥∞ .

i∈[r]\J

Proof. The claim is immediate if J = ∅ or some fi is zero. By homogeneity, assume ∥fi ∥∞ ≤ 1 for every i ∈ / J. Replacing fi (x) by fi (bi + x), which preserves both norms, reduces to linear forms. Group the forms in J into one map and their functions into one function, and do the same for each Ia : Y LJ (z) = (Lj (z))j∈J , F (x) = fj (xj ), x ∈ FJp ; j∈J

LIa (z) = (Li (z))i∈Ia , Ga (y) =

fi (yi ),

y ∈ FIpa .

i∈Ia

Then ∥Ga ∥∞ ≤ 1 and ΛΨ (f ) = Ez [F (LJ z) a=1 Ga (LIa z)]. Put Ka = ker LIa = i∈Ia ker Li , with Ka = V if Ia = ∅. Independence of the forms indexed by Ia ∪ J says that (LJ , LIa ) : V → FJp × FIpa is surjective; hence LJ (Ka ) = FJp for every a, LJ (V ) = FJp . T

For 0 ≤ s ≤ t, let hu , h′u be independent and uniform in Ku for u ≤ s, independent of the uniform z ∈ V . Write h = (hu )u≤s and h′ = (h′u )u≤s for these collections. For ω ∈ {0, 1}s , write P (1) ′ u) hω = u≤s h(ω , where h(0) u u = hu and hu = hu . Define Λs = Ez,h,h′

C |ω| F LJ (z + hω )

Y a>s

ω∈{0,1}s

Ga LIa (z + hω )

so that Λ0 = ΛΨ (f ). We claim that |Λs |2 ≤ Λs+1 for 0 ≤ s < t, where Λs+1 ≥ 0. Indeed, write the integrand of Λs as Y C |ω| Gs+1 LIs+1 (z + hω ) · Φ(z, h, h′ ), ω

where Φ collects the factors involving F and Ga for a > s + 1. Translating z by an independent uniform hs+1 ∈ Ks+1 preserves its distribution and leaves the Gs+1 factors unchanged. Their product has modulus at most one, so Cauchy–Schwarz in (z, h, h′ ) gives 2

|Λs |2 ≤ Ez,h,h′ Ehs+1 [Φ(z + hs+1 , h, h′ )] h

= Ez,h,h′ ,hs+1 ,h′s+1 Φ(z + hs+1 , h, h′ )Φ(z + h′s+1 , h, h′ ) = Λs+1 . The last integrand is exactly that of Λs+1 : the new coordinate ωs+1 selects hs+1 or h′s+1 and contributes one conjugation. Iterating gives t

|ΛΨ (f )|2 ≤ Λt = Ez,h,h′

C |ω| F LJ (z + hω ) .

ω∈{0,1}t

Put du = h′u − hu , so that z + hω = z + u hu + u ωu du , and set x = LJ (z + u hu ) and y u = LJ (du ). Surjectivity of LJ makes x uniform on FJp and independent of (h, h′ ). Each du is uniform on Ku , so LJ (Ku ) = FJp makes y u uniform on FJp , and all these variables are independent. Therefore P

Λt = Ex,y1 ,...,yt ∈FJp

C |ω| F x +

Y ω∈{0,1}t

t X

ωu y u

= ∥F ∥2U t (FJp ) .

u=1

Finally, the definition of the Gowers norm factors over coordinates:  2t U t (FJ p)

∥F ∥

= Ex,h1 ,...,ht ∈FJp 

C |ω| fj xj +

ω∈{0,1}t j∈J

t X

!

ωu hu,j  =

u=1

∥fj ∥2U t .

j∈J

Taking 2t -th roots and restoring the original scaling proves the claim. For an MDS system, the lemma’s independence conditions reduce to |Ia | + |J| ≤ k − 1. This is the only use of the MDS property in the following corollary. Corollary 3 (Number of U t factors). Let Ψ be an MDS system, let r ≥ k and t ≥ 2, and define t(k − 1) − r qt (r, k) = . t−1

If qt (r, k) ≥ 1, then, for every J ⊆ [r] of size qt (r, k), |ΛΨ (f )| ≤

∥fj ∥U t

j∈J

∥fi ∥∞ .

i∈[r]\J

Proof. Put q = qt (r, k). Since r ≥ k, we have q ≤ k−2 < r. The definition of q gives r−q ≤ t(k−1−q). Thus we can partition the indices outside J into t groups Ia , each of size at most k − 1 − q. Every Ia ∪ J has size at most k − 1, so Lemma 12 applies. If the functions are bounded by one and their U t norms are at most ρ < 1, this gives ρqt (r,k) . For structured leakage, we allow t to grow with n. In Section 6, we will reuse the bound with t = 3 for the below-half theorem. 24

5.2

From Gowers norms to leakage resilience

Let τi : Fp → {0, 1}m , and put fi,b (x) = 1[τi (x) = b] − νi (b), as in Lemma 6. The L1 bound of Proposition 1 with r0 = k − 1 reduces the leakage distance to averages of products of these functions. Proposition 3 (Finite-parameter leakage bound). Let C be an [n, k − 1, n − k + 2]p MDS code, and let t ≥ 2 be an integer with qt (n, k) ≥ 1. If ∥fi,b ∥U t ≤ ρ ≤ 1 for all i ∈ [n] and b ∈ {0, 1}m , then 1 SD τ (U C ), τ (U Fnp ) ≤ (1 + 2m )n ρqt (n,k) . 2

For one-bit maps, if the functions fi = 2(τi − Ex [τi (x)]) satisfy ∥fi ∥U t ≤ ρ ≤ 1, the distance is at most 3n ρqt (n,k) . Proof. The dual of C has minimum distance k, so Proposition 1 and Lemma 6 give 1 X SD τ (U C ), τ (U Fnp ) ≤ 2 |A|≥k

" X

EX∼UC

bA ∈({0,1}m )A

# Y

fi,bi (Xi )

i∈A

Fix A with |A| = r ≥ k. The coordinate forms of a linear parametrization of C, restricted to A, form an MDS system, since any k − 1 of them are independent, and ∥fi,bi ∥∞ ≤ 1. Since qt (r, k) ≥ qt (n, k), Corollary 3 bounds each average by ρqt (r,k) ≤ ρqt (n,k) . Hence n X 1 n mr 1 SD τ (U C ), τ (U Fnp ) ≤ ρqt (n,k) 2 ≤ (1 + 2m )n ρqt (n,k) . 2 r 2 r=k

For one-bit maps, fi,1 = fi /2 and fi,0 = −fi /2, so the first bound gives 12 3n (ρ/2)qt (n,k) ≤ 3n ρqt (n,k) , which completes the proof. At constant rate, fix an integer t ≥ 2 with tc > 1 and put β = (tc − 1)/(t − 1) > 0. For k ≥ cn, the number of retained Gowers factors satisfies

qt (n, k) =

t(k − 1) − n t ≥ βn − − 1 ≥ βn − 3. t−1 t−1

(3)

Thus local norms of size p−Ωc (1) give exp(−Ωc (n log p)) leakage distance even when m is a sufficiently small constant times log2 p.

5.3

Quadratic-residue leakage

Let χ : Fp → {−1, 0, 1} be the quadratic character, with χ(0) = 0. The character-sum estimate t √ of [Ngu24, Lemma 2] gives ∥χ∥2U t ≤ 2t / p. For τ = τQR we have 2Ex [τ (x)] = 1+1/p, so the centered function is f = χ+1{0} −1/p. The Gowers product of 1{0} is one exactly when x = h1 = · · · = ht = 0, so 1{0}

= p−(t+1)/2 , and the triangle inequality gives 2t 1/2t 1 t t+1 ∥f ∥U t ≤ √ + p−(t+1)/2 + ≤ 4p−1/2 . p p

The same bound holds if the output at zero is changed to 0, where the centered function is χ − 1{0} + 1/p.

Proof of Theorem 7, part 1. Fix t and β as in (3), and write q = qt (n, k). For n sufficiently large, t+1 q ≥ 1 and 4p−1/2 ≤ 1 for every p > n, and the affine changes of input preserve the local bound by Remark 3. Proposition 3 bounds the distance by t+1

3n 4p−1/2

= exp n log 3 + q log 4 −

log p . t+1

Since βn − 3 ≤ q ≤ n and p > n, the exponent is at most −a1 n log p with a1 = β/2t+3 , for n sufficiently large depending only on c. The bound is uniform over the code and the affine changes of input.

5.4

Almost all logarithmic-bit leakage functions

For a random map τ : Fp → {0, 1}m , each output indicator minus 2−m has independent centered values. The cube-collision argument for random signs in [Ngu24, Lemma 4] therefore applies to these indicators as well. Subtracting their empirical means costs at most a factor two in the Gowers norm; no balance assumption on the output probabilities is needed. Lemma 13 (Gowers norm of a random leakage function). Let t ≥ 2, m ≥ 1, and 0 < ρ ≤ 1. For a uniformly random map τ : Fp → {0, 1}m and a fixed output b, put fb (x) = 1[τ (x) = b] − t t Pru∼UFp [τ (u) = b]. If p(ρ/2)2 ≥ 2 22 , then t+1

p(ρ/2)2 Pr ∥fb ∥U t > ρ ≤ exp − τ 22t+3

Proof. Put ξb (x) = 1[τ (x) = b] − 2−m and T (τ ) = ∥ξb ∥2U t . If all 2t vertices of a Gowers cube are distinct, independence and Eτ [ξb (x)] = 0 make its expected product zero. Each pair of vertices coincides with probability 1/p, and |ξb | ≤ 1, so Eτ [T ] ≤

2t 2

∥fb ∥U t = ∥ξb − Ex [ξb (x)]∥U t ≤ ∥ξb ∥U t + |Ex [ξb (x)]| ≤ 2 ∥ξb ∥U t .

Changing one value τ (a) affects at most a 2t /p fraction of the cube products, each by at most two. Thus T changes by at most 2t+1 /p, and bounded differences [McD89] gives pu2 Pr[T − Eτ [T ] ≥ u] ≤ exp − 2t+1 τ 2

The hypothesis gives Eτ [T ] ≤ 21 (ρ/2)2 , whereas ∥fb ∥U t > ρ implies T > (ρ/2)2 . Taking u = 1 2t 2 (ρ/2) proves the claim. Proof of Theorem 7, part 2. Fix t and β as in (3), and choose t+2

ρ = p−1/2

ηc =

β , 2t+4

1 ≤ m ≤ ηc log2 p. t

For large p, the hypothesis of Lemma 13 holds because p(ρ/2)2 = 2−2 p3/4 . Its conclusion is √ Pr[∥fi,b ∥U t > ρ] ≤ exp(−b0 p) for a constant b0 > 0 depending only on t. A union bound over the n2m pairs (i, b) gives √ √ √ Pr[∥fi,b ∥U t > ρ for some (i, b)] ≤ n2m exp(−b0 p) ≤ p1+ηc exp(−b0 p) ≤ exp(−b0 p/2). 26

On the complementary event, take n large enough that qt (n, k) ≥ 3βn/4. Since log(1 + 2m ) ≤ log 2 + ηc log p, Proposition 3 gives 1 qt (n, k) SD τ (U C ), τ (U Fnp ) ≤ exp n log(1 + 2m ) − t+2 log p 2 2 1 1 ≤ exp (n log 2 − 2ηc n log p) ≤ exp(−ηc n log p). 2 2

The event depends only on the maps, so this holds simultaneously for all codes in the theorem and, by Remark 3, after all coordinatewise affine changes of input. Take bc = b0 /2 and ac = min{a1 /2, ηc }, increasing n0 (c) if needed. The factor two in the Shamir reduction is absorbed by the displayed factor 1/2 here and by the slack in a1 for part 1. For fixed m, the same proof gives the stronger success probability 1−exp(−Ωc,m (p)) with leakage distance exp(−Ωc,m (n)): choose a constant ρ > 0 such that β log(1/ρ) > log(1 + 2m ) and apply the same two bounds.

5.5

Field size for square-root thresholds

√ When k = Θ( n), the Cauchy–Schwarz order t must grow with n, so we use the finite-parameter bound rather than the constant-rate theorem. The next corollary gives an explicit sufficient field size for leakage error exp(−n) in both applications. Corollary 4 (An explicit field-size bound). Let 3 ≤ k ≤ n and t = ⌈(n − 1)/(k − 2)⌉. If log p ≥ 8n 2t , then for every C = GRSα,v (n, k − 1), SD(τ (U C ), τ (U Fnp )) ≤ exp(−n) for quadratic-residue leakage with the affine input changes of Theorem 7; and for independent uniformly random Boolean maps, with probability at least 1 − exp(−n), the same bound holds simultaneously for every such code. Both conclusions hold for Shamir leakage between every pair of secrets with the same error. Proof. By the choice of t, t(k − 2) ≥ n − 1, i.e. t(k − 1) − n ≥ t − 1, so q = qt (n, k) ≥ 1. Put ρ = exp(−n)/(2 · 3n ) and fi = 2(τi − Ex [τi (x)]). If ∥fi ∥U t ≤ ρ for every i, then Proposition 3 gives 3n ρq ≤ 3n ρ = 12 exp(−n), and the factor 21 yields the Shamir error through Lemma 1. t+1 For quadratic-residue leakage, Section 5.3 gives ∥fi ∥U t ≤ 4p−1/2 ≤ ρ whenever log p ≥ 2t+1 log(4/ρ) = 2t 2 log 8 + 2(1 + log 3)n , which follows from log p ≥ 8n2t since n ≥ 3. For a random Boolean map, 2τ − 1 has independent uniform signs. The same cube-collision t t argument as in Lemma 13 gives Eτ [∥2τ − 1∥2U t ] ≤ 22 /p, and ∥2(τ − Ex [τ (x)])∥U t ≤ 2 ∥2τ − 1∥U t . Markov’s inequality and a union bound therefore give t

n 22 22 Pr ∥fi ∥U t > ρ for some i ∈ [n] ≤ ≤ exp(−n), p ρ2t

the last step because 2t log(2/ρ)+n+log n+log 22 ≤ 2t (1+log 3)n+2 log 2 +n+log n+2t log 2 ≤ 8n2t ≤ log p, using 2 ≤ t ≤ n − 1 and n + log n + 2t log 2 ≤ 4n ≤ n2t . The event depends only on the maps and is preserved by affine input changes, so the bound holds simultaneously for all codes and input changes in the statement. √ For k = Θ( n) we have t = n/k + O(1), so the condition reads log p ≥ Cn 2n/k for √ a constant C. Concretely, for n = k 2 with k ≥ 5, one gets t = k + 3 and q = 1, so log p ≥ 64n 2 n suffices; a √ single Gowers factor carries the bound. This field size is doubly exponential in n; we do not claim it is necessary.

A contrasting attack at square-root thresholds. Kopparty’s algorithm for recovering a monic squarefree polynomial from noisy quadratic-character values [Kop26] attacks Shamir sharing when √ n = p − 1 and k is at most a small constant times n: party i leaks τQR (P (αi ) + αik ), which is the character value of the monic polynomial Q(X) = X k + P (X) at αi up to at most k + 1 discrepancies (the roots of Q and the missing point 0). The decoder tolerates these in this degree range and recovers Q, hence the secret Q(0), whenever Q is squarefree. For each fixed secret s, the discriminant of Q is a nonzero polynomial of degree at most 2k − 2 in the random coefficients of P (it is nonzero at X k + s for s = ̸ 0 and at X k + X for s = 0, both squarefree since k < p), so Q fails to be squarefree with probability at most (2k − 2)/p. The attack uses only the fixed input shifts covered by Theorem 7, not additional leaked bits. At every positive constant rate our theorem gives security even for p = n + 1; at square-root thresholds the corollary above gives security over sufficiently large fields. The intermediate range is open.

Leakage resilience below half

Theorem 8 (GRS codes below half). There are absolute constants cbh < 1/2, γ > 0, and n0 such that, for n ≥ n0 and every prime p > n, every GRS code over Fp of length n and rate at least cbh is e−γn -resilient to one-bit local leakage. We prove Theorem 8 by combining the three tools: Proposition 2 with an intermediate cutoff r0 close to n; a supportwise form of the list-recovery argument of Section 4, which controls the squared components below the cutoff (Section 6.1); and the MDS von Neumann inequality of Section 5.1 together with a second-moment bound, which control the components above it (Section 6.2). The supportwise form is needed because the list bound of Theorem 4 is available only at radius R < k, and below rate half Lemma 11 cannot use it. Both estimates have negative exponents at rate half; continuity gives a fixed rate below half (Section 6.3). Throughout, C is a GRS code of dimension k − 1 unless a statement says otherwise, and gi , fi are as in Section 3.4.

6.1

List recovery for small supports

Lemma 11 needs the list bound at radius n − j with j ≤ k − 1, whereas Theorem 4 supplies it at radius R < k; below rate half, n − k + 1 > k − 1, so no admissible j satisfies n − j ≤ R. At a fixed support size r, however, every dual word has n − r zero coordinates, which count as agreements with the list {0}. Retaining j Fourier factors on a common set H and putting {0} outside H brings the radius down to r − j, so j = r − R suffices, and j ≤ k − 1 as long as r ≤ k + R − 1. Summing over H gives the following bound. Lemma 14 (List recovery for a fixed support size). In the setting of Section 4, so that C ⊥ has minimum distance at least k, the maps τi have at most Q output symbols, and p ≥ 16Q or Q = 2 with p odd, for all integers k ≤ r ≤ n and 1 ≤ j < k, X

∥T(fC=A )∥22 ≤ ηQk−1−j ListC ⊥ (r − j, Q − 1)

|A|=r

n j r . j

Proof. Fix H ⊆ [n] with |H| = j. For each A ⊇ H of size r, choose IA with H ⊆ IA ⊆ A and |IA | = k − 1, which is possible since j ≤ k − 1 < r. Apply Lemma 8 with J = A \ IA , and bound the k − 1 − j factors indexed by IA \ H by ηQ using Lemma 9: X A⊇H |A|=r

∥T(fC=A )∥22 ≤

∥Ti χyi ∥22 ≤ ηQk−1−j

A⊇H y∈C ⊥ i∈IA |A|=r supp(y)=A

i∈H y∈C ⊥ wt(y)=r, H⊆supp(y)

∥Ti χyi ∥22 .

As in Lemma 11, the last sum is a nonnegative linear combination of monomials i∈H wi (yi ) in the weights wi (a) = ∥Ti χa ∥22 , a ∈ F∗p . The constraints on the weights follow from Lemma 9. Lemma 10 (the coordinates outside H play no role) yields lists Vi ⊆ F∗p of size Q − 1, i ∈ H, with X

∥Ti χyi ∥22 ≤ {y ∈ C ⊥ : wt(y) = r, yi ∈ Vi for all i ∈ H} .

i∈H y∈C ⊥ wt(y)=r, H⊆supp(y)

Take input lists Si = Vi on H and Si = {0} outside H. Every counted word agrees with the lists on H and on its n − r zero coordinates, which lie outside H; so the count is at most ListC ⊥ (r − j, Q − 1). Finally, sum over H. Each support of size r contains exactly rj sets H, so r j Dividing by

X X

∥T(fC=A )∥22 =

n ηQk−1−j ListC ⊥ (r − j, Q − 1). j

∥T(fC=A )∥22 ≤

|H|=j A⊇H |A|=r

|A|=r

r j proves the claim.

For one-bit leakage the input lists have size one, so list recovery becomes list decoding. Corollary 5 (List decoding for a fixed support size). Let p be an odd prime and C ⊆ Fnp a linear code whose dual has minimum distance at least k. For all integers k ≤ r ≤ n and R with 1 ≤ r − R < k, X

|ΓC (g A )| ≤ ListC ⊥ (R) 2

r−R−k+1

|A|=r

n r−R r . r−R

Proof. Take Q = 2 and j = r − R in Lemma 14. Then η2 = 1/2, ListC ⊥ (r − j, 1) = ListC ⊥ (R), and ∥T(fC=A )∥22 = |ΓC (g A )|2 by Lemma 7. Write D = C ⊥ for the remainder of this subsection. For our decoding radius R < k, the condition 1 ≤ r − R < k requires k ≤ r ≤ min{n, k + R − 1}; below rate half this leaves the largest supports untreated, and Section 6.2 bounds those by Cauchy–Schwarz. The next lemma gives a uniform estimate below the cutoff (1 − ε)n. Lemma 15 (Bound for smaller supports). Fix 0 < ζ < c < 1/2 and 0 < ε < 1 with 1 − ε < 2c − ζ. Let k = kn with (kn − 1)/n → c, and R = ⌊k − 1 − ζn⌋. Assume ListD (R) ≤ Ln with log Ln = o(n). Then every support size k ≤ r ≤ (1 − ε)n satisfies X

|ΓC (g A )|2 ≤ exp nG(c, ζ, ε) + o(n) ,

|A|=r

uniformly in the support size and the leakage maps, where G(c, ζ, ε) = (1 − 2c + ζ) log 2 + log

1 ε2 − . 2(c − ζ) 2

In particular, if G(c, ζ, ε) < 0, the sum is exponentially small at each of these support sizes. Proof. We first obtain an estimate with the integer parameters explicit. Suppose ListD (R) ≤ L with 1 ≤ R < k. For k ≤ r ≤ min{n, k + R − 1}, put j = r − R; then 1 ≤ j < k and r − j = R, so Corollary 5 gives X |A|=r

|ΓC (g A )|

n j−k+1 j ≤ L2 r . j

Set t = n − r and g = n − k − R + 1. The binomial ratio has the exact product form n t−1 Y n−u j−k+1 j g 2 = 2 . r 2(R + t − u) j u=0

For 0 ≤ u < t we have R + t − u ≥ R + 1, and 1 − v ≤ exp(−v) with R + 1 ≤ n gives R/(R + 1) ≤ exp(−1/(R + 1)) ≤ exp(−1/n). Hence u + 1 u R n−u n n 1− , ≤ ≤ exp − 2(R + t − u) 2R n R+1 2R n

and multiplying over u gives the finite bound X

|ΓC (g A )|2 ≤ L 2g

|A|=r

n t

exp −

t2 , 2n

since t(t + 1)/(2n) ≥ t2 /(2n). Empty products cause no difficulty when t = 0. Now take R = ⌊k − 1 − ζn⌋ and L = Ln . For large n, 1 ≤ R < k and 2R < n, since R/n → c − ζ < 1/2. Moreover, k + R − 1 = (2c − ζ)n + o(n) > (1 − ε)n, so r ≤ k + R − 1 throughout the stated range. Using εn ≤ t ≤ n in the finite bound gives X

|ΓC (g A )|2 ≤ Ln 2n−k−R+1

|A|=r

n n

ε2 n

exp −

= exp nG(c, ζ, ε) + o(n) , where the equality uses (k − 1)/n → c, R/n → c − ζ, and log Ln = o(n). The bound is independent of the support size and the leakage maps.

6.2

Iterated Cauchy–Schwarz for large supports

We bound the second term of (2). The proof separates two cases: Cauchy–Schwarz controls leakage functions with sufficiently large total squared bias, while the product of U 3 norms controls the remaining functions. Put (log κ0 )2 κ0 = (3/4)1/8 < 1, β0 = . 64 Proposition 4 (Bound for large supports). Suppose 2k − 2 ≤ n < 3k − 3, put c = (k − 1)/n, and fix 0 < ε < 1/2. Let r0 = ⌊(1 − ε)n⌋, and define H(c, ε) = h(ε) + max Then

n 3c − 1

log κ0 +

β0 , (1 − 2c)(log 2 + 1/2) −

β0 o . 2

X 1 |ΓC (f A )| ≤ exp nH(c, ε) + O(log n) . 2 A⊆[n] : |A|>r 0

In particular, H(1/2, 0) = max{ 18 log κ0 , −β0 /2} < 0, with the formula extended continuously to ε = 0. The strict inequality persists when c is slightly below half and ε is sufficiently small. We first establish the local U 3 bound, then give the two estimates for an individual support. 30

6.2.1

A uniform bound for centered bits

Lemma 16 (Bounds for a centered bit). For every map τ : Fp → {0, 1} over an odd prime field, the function f = 2(τ − E[τ ]), with µ = 1 − 2E[τ ], satisfies ∥f ∥2 =

1 − µ2 ,

∥f ∥U 3 ≤ κ0 ,

∥f ∥∞ ≤ 1 + |µ| ≤ 2.

Proof. Put V = 1 − µ2 . The values 1 + µ and −(1 − µ) occur with probabilities (1 − µ)/2 and (1 + µ)/2, respectively. This proves the L2 and pointwise bounds, and gives E[f 2 ] = V,

E[f ] = 0,

f 2 = V + 2µf.

The U 3 estimate uses the symmetry of the Fourier transform of a real function. Specifically, every real q satisfies ∥q∥4U 2 ≤ (E[q])4 +

2 1 1 1 ∥q∥22 − (E[q])2 ≤ ∥q∥42 + (E[q])4 . 2 2 2

To see this, pair each nonzero frequency a with −a; the two Fourier magnitudes are equal, and the frequencies are distinct because p is odd. If ba = |qb(a)|2 , with one representative from each pair, then X 2 X X |qb(a)|4 = 2 b2a ≤ 2 ba . a̸=0

pairs

Adding the zero frequency and using Parseval gives the first inequality; the second follows from (E[q])2 ≤ ∥q∥22 . Now let qt (x) = f (x + t)f (x) and K(t) = Ex [qt (x)]. Expanding f (x + t)2 f (x)2 with f 2 = V + 2µf and using E[f ] = 0 gives ∥qt ∥22 = V 2 + 4µ2 K(t),

Et [K(t)] = 0.

Cauchy–Schwarz and the real-function bound applied to f give |K(t)| ≤ V,

1 Et [K(t)2 ] = ∥f ∥4U 2 ≤ V 2 . 2

Applying the same bound to each qt , we obtain ∥f ∥8U 3 = Et [∥qt ∥4U 2 ] 1 1 ≤ Et [(V 2 + 4µ2 K(t))2 ] + Et [K(t)4 ] 2 2 1 4 4 1 2 ≤ V + 8µ + V Et [K(t)2 ] 2 2 3 4 3 3 ≤ V + 4µ4 V 2 ≤ (V + µ2 )4 = . 4 4 4 The second inequality uses Et [K(t)] = 0 and K(t)4 ≤ V 2 K(t)2 ; the last inequality follows by the binomial theorem, since V, µ2 ≥ 0.

6.2.2

Two bounds for each support

Write µi = 1 − 2θi . The preceding lemma gives two ways to make the average small: bias decreases the L2 norms, whereas small bias keeps the supremum norms close to one and lets the U 3 bounds act. Lemma 17 (Bounds on ΓC (f A )). Suppose 2k − 2 ≤ n < 3k − 3. For every A ⊆ [n] with |A| ≥ k, P put B = i∈A µ2i , e = n − 2k + 2, and q = q3 (n, k) = ⌊(3k − 3 − n)/2⌋. Then n

|ΓC (f A )| ≤ min exp q log κ0 +

√

nB , exp e(log 2 + 1/2) − B/2

Proof. For the first bound, use all n evaluation forms defining C, with the constant function one outside A; any k − 1 of the forms are independent by the MDS property, and q is the number of retained Gowers factors for t = 3. Since 0 ≤ q ≤ (k − 1)/2 < |A|, choose J ⊆ A of size q. The MDS von Neumann inequality (Corollary 3) with t = 3, followed by Lemma 16, gives |ΓC (f A )| ≤

∥fj ∥U 3

j∈J

∥fi ∥∞ ≤ κ0q

Y i∈A\J

(1 + |µi |) ≤ κ0q exp

√ |µi | ≤ κ0q exp( nB).

i∈A

i∈A\J

If q = 0, the first inequality is just the supremum bound. For the second bound, partition [n] = I1 ⊔ I2 ⊔ E with |I1 | = |I2 | = k − 1 and |E| = e. Bound the factors on E by two and apply Cauchy–Schwarz to the other two products. For X ∼ UC , |ΓC (f A )| ≤ 2e

2 Y

EX∼UC

t=1

h Y

|fi (Xi )|2

i1/2

= 2e

i∈A∩It

Y q

1 − µ2i ,

i∈A\E

where √ the equality uses independence and uniformity within each It , again from the MDS property. P Since 1 − x ≤ exp(−x/2) and i∈A∩E µ2i ≤ e, 2e

Y q

1 − µ2i ≤ exp e log 2 −

i∈A\E

1 X 2 µi ≤ exp e(log 2 + 1/2) − B/2 . 2 i∈A\E

Proof of Proposition 4. We have r0 ≥ k − 1, so Lemma 17 applies to every support in the sum. If B ≤ β0 n, use its first bound; otherwise use its second. Since q = (3c−1)n/2+O(1) and e = (1−2c)n, in either case

|ΓC (f A )| ≤ exp n max

n 3c − 1

log κ0 +

β0 , (1 − 2c)(log 2 + 1/2) −

β0 o + O(1) . 2

There are at most 0≤t<εn t ≤ (n + 1) exp(nh(ε)) such supports, since their complements have fewer than εn elements. Multiplying the two bounds proves the proposition. P

6.3

Combining the estimates

Both estimates have strictly negative exponents at rate half when the cutoff is sufficiently close to n. We use continuity to keep both exponents negative at a slightly smaller rate. Proof of Theorem 8. Consider the continuous formulas for G and H in Lemma 15 and Proposition 4. Since H(1/2, 0) < 0, fix 0 < ε < 1/4 with H(1/2, ε) < 0. For this ε, G(1/2, 0, ε) = −ε2 /2 < 0. By continuity there is a fixed 0 < δ < min{ε/3, 1/6} such that, with c0 = 1/2 − δ and ζ = δ, G(c0 , ζ, ε) < 0,

H(c0 , ε) < 0. 32

These choices also give 1/3 < c0 < 1/2, 0 < ζ < c0 , and 1 − ε < 1 − 3δ = 2c0 − ζ, as the two estimates require. All these constants are independent of n and p. Put kn = ⌈c0 n⌉ + 1, r0 = ⌊(1 − ε)n⌋ , Rn = ⌊kn − 1 − ζn⌋ . We first prove the claim for a code C of dimension kn − 1, and write D = C ⊥ . Since kn − 1 ≥ ζn, the consequence of Theorem 4 described in Section 2.5 gives ListD (Rn ) ≤ Ln = ncζ for a constant cζ and all sufficiently large n, uniformly over the code parameters; as ζ is fixed, log Ln = O(log n) = o(n). All averages ΓC (g A ) on nonempty supports of size smaller than kn vanish by Lemma 7. For kn ≤ r ≤ r0 , Lemma 15 and G(c0 , ζ, ε) < 0 give X

|ΓC (g A )|2 ≤ exp(−βL n)

|A|=r

for a fixed βL > 0 and all sufficiently large n, uniformly in r. For the remaining support sizes, 2(kn − 1) ≤ n < 3(kn − 1) for large n, and Proposition 4 gives X 1 |ΓC (f A )| ≤ exp(−βH n) 2 A⊆[n] : |A|>r 0

for a fixed βH > 0; here (kn − 1)/n → c0 , so continuity and H(c0 , ε) < 0 ensure that the rounding in kn does not change the sign of the exponent for large n. Proposition 2 now yields 1q SD τ (U C ), τ (U ) ≤ n exp(−βL n) + exp(−βH n) ≤ exp(−γn) 2 for some γ > 0 and all sufficiently large n; the factor n counts the support sizes in the first sum and is absorbed by the exponential decay. None of the constants depends on the leakage maps. For a larger GRS code, the subcode obtained by restricting the polynomial degree to less than kn − 1 has the dimension just treated, and Remark 1 gives the same guarantee for every larger dimension. Choose any fixed cbh with c0 < cbh < 1/2. The code theorem follows because every GRS code of rate at least cbh has dimension at least ⌈c0 n⌉. If a Shamir scheme has k ≥ cbh n, then for sufficiently large n, k − 1 ≥ cbh n − 1 ≥ c0 n, so its code dimension is also at least ⌈c0 n⌉, and Lemma 1 proves Theorem 1 with the same cbh and leakage distance at most 2e−γn . Fn p

Corollary 6 (An explicit constant). The conclusions of Theorems 1 and 8 hold with cbh = 1/2 − 10−14 . Proof. Taking ε = 6 · 10−7 , ζ = 2 · 10−14 , and c0 = 1/2 − 2 · 10−14 gives G(c0 , ζ, ε) < −5.6 · 10−14 and H(c0 , ε) < −3.7 · 10−7 . These choices satisfy 0 < ζ < c0 < 1/2, 1 − ε < 2c0 − ζ, and c0 < cbh < 1/2, so the preceding proof applies.

Acknowledgments The author used ChatGPT (Sol and Astra) as interactive research assistants throughout this work: to discuss and refine ideas and arguments, to check calculations and parameter choices, to locate related work, and to help draft and revise the text. Some mathematical suggestions made by the models were incorporated after the author’s own verification. In particular, discussions with the models brought recent list-decoding and list-recovery results for Reed–Solomon codes to the author’s attention and helped assess their applicability. The author supplied the research questions and the main ideas, evaluated and corrected the models’ output, and takes full responsibility for the correctness of the results, the references, and the final presentation. 33

References [ADN+ 19]

Divesh Aggarwal, Ivan Damgård, Jesper Buus Nielsen, Maciej Obremski, Erick Purwanto, João Ribeiro, and Mark Simkin. Stronger leakage-resilient and non-malleable secret sharing schemes for general access structures. In Advances in Cryptology – CRYPTO 2019, Part II, volume 11693 of Lecture Notes in Computer Science, pages 510–539. Springer, 2019.

[AGG+ 25]

Omar Alrabiah, Zeyu Guo, Venkatesan Guruswami, Ray Li, and Zihan Zhang. Random Reed–Solomon codes achieve list-decoding capacity with linear-sized alphabets. Advances in Combinatorics, 2025(8):1–39, 2025.

[BCP+ 26]

Joshua Brakensiek, Yeyuan Chen, Aaron Putterman, Zihan Zhang, and Kai Zhe Zheng. Algorithmic list decoding of Reed–Solomon codes up to capacity, 2026. arXiv:2609.08005, version 1.

[BDIR18]

Fabrice Benhamouda, Akshay Degwekar, Yuval Ishai, and Tal Rabin. On the local leakage resilience of linear secret sharing schemes. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, Part I, volume 10991 of Lecture Notes in Computer Science, pages 531–561, Cham, 2018. Springer.

[BDIR21]

Fabrice Benhamouda, Akshay Degwekar, Yuval Ishai, and Tal Rabin. On the local leakage resilience of linear secret sharing schemes. Journal of Cryptology, 34(2), 2021. Article 10.

[BGM23]

Joshua Brakensiek, Sivakanth Gopi, and Visu Makam. Generic Reed–Solomon codes achieve list-decoding capacity. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1488–1501. ACM, 2023.

[BHM+ 26a]

Aniruddha Biswas, Jihun Hwang, Hemanta K. Maji, Ilya D. Shkredov, and Xiuyu Ye. Beyond all-or-nothing corruption: Additive secret sharing under Hamming-weight leakage, 2026. Manuscript.

[BHM+ 26b]

Aniruddha Biswas, Jihun Hwang, Hemanta K. Maji, Ilya D. Shkredov, and Xiuyu Ye. Energy estimation of the Hamming slice and its applications, 2026. arXiv:2609.08056.

[BHMY26]

Aniruddha Biswas, Jihun Hwang, Hemanta K. Maji, and Xiuyu Ye. Resilience of inner-product masking scheme against Hamming weight leakage. In 7th Conference on Information-Theoretic Cryptography (ITC 2026), volume 385 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026.

[BOGW88]

Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 1–10. ACM, 1988.

[BS26]

Katharina Boudgoust and Mark Simkin. Scale, round, break: Simple leakage attacks on secret sharing schemes. Cryptology ePrint Archive, Paper 2026/833, 2026.

[CCD88]

David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty unconditionally secure protocols. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 11–19. ACM, 1988.

[CGG+ 20]

Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Ashutosh Kumar, Xin Li, Raghu Meka, and David Zuckerman. Extractors and secret sharing against bounded collusion protocols. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, pages 1226–1242. IEEE, 2020.

[CKOS22]

Nishanth Chandran, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, and Sruthi Sekar. Short leakage resilient and non-malleable secret sharing schemes. In Advances in Cryptology – CRYPTO 2022, Part I, volume 13507 of Lecture Notes in Computer Science, pages 178–207. Springer, 2022.

[CSTW24]

Roni Con, Noah Shutty, Itzhak Tamo, and Mary Wootters. Repairing Reed–Solomon codes over prime fields via exponential sums. IEEE Transactions on Information Theory, 70(12):8587–8594, 2024.

[DDF14]

Alexandre Duc, Stefan Dziembowski, and Sebastian Faust. Unifying leakage models: From probing attacks to noisy leakage. In Advances in Cryptology – EUROCRYPT 2014, volume 8441 of Lecture Notes in Computer Science, pages 423–440. Springer, 2014.

[DGW+ 10]

Alexandros G. Dimakis, P. Brighten Godfrey, Yunnan Wu, Martin J. Wainwright, and Kannan Ramchandran. Network coding for distributed storage systems. IEEE Transactions on Information Theory, 56(9):4539–4551, 2010.

[DKT26]

Quang Dao, Scott Duke Kominers, and Justin Thaler. Reed–Solomon codes beyond Johnson: Efficient decoding and smaller cryptographic proofs, 2026. Cryptology ePrint Archive, Report 2026/2056.

[DLM+ 26]

Dean Doron, Tal Leonov, Jonathan Mosheiff, Henrique Navas, Nicolas Resch, and João Ribeiro. Discrepancy for random linear codes, 2026. arXiv:2606.24471, version 2.

[DMRR25]

Dean Doron, Jonathan Mosheiff, Nicolas Resch, and João Ribeiro. List-recovery of random linear codes over small fields. IEEE Transactions on Information Theory, 71(12):9548–9562, 2025.

[FKS22]

Asaf Ferber, Matthew Kwan, and Lisa Sauermann. List-decodability with large radius for Reed–Solomon codes. IEEE Transactions on Information Theory, 68(6):3823–3828, 2022.

[FMM+ 24]

Sebastian Faust, Loïc Masure, Elena Micheli, Maximilian Orlt, and François-Xavier Standaert. Connecting leakage-resilient secret sharing to practice: Scaling trends and physical dependencies of prime field masking. In Advances in Cryptology – EUROCRYPT 2024, Part IV, volume 14654 of Lecture Notes in Computer Science, pages 316–344, Cham, 2024. Springer.

[FMM+ 26]

Sebastian Faust, Loïc Masure, Elena Micheli, Hai Hoang Nguyen, Maximilian Orlt, and François-Xavier Standaert. IP masking with generic security guarantees under minimum assumptions, and applications. In Advances in Cryptology – ASIACRYPT 2025, Part II, volume 16246 of Lecture Notes in Computer Science, pages 544–575. Springer, 2026.

[GG26]

Rohan Goyal and Venkatesan Guruswami. Improved analysis of list-decodability of random linear codes: It’s all about counting constraints, 2026. ECCC Report TR26-074.

[GHK11]

Venkatesan Guruswami, Johan Håstad, and Swastik Kopparty. On the list-decodability of random linear codes. IEEE Transactions on Information Theory, 57(2):718–725, 2011.

[GHSZ02]

Venkatesan Guruswami, Johan Håstad, Madhu Sudan, and David Zuckerman. Combinatorial bounds for list decoding. IEEE Transactions on Information Theory, 48(5):1021–1034, 2002.

[GK18]

Vipul Goyal and Ashutosh Kumar. Non-malleable secret sharing. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 685–698. ACM, 2018.

[GLS+ 24]

Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, and Mary Wootters. Improved list-decodability and list-recoverability of Reed–Solomon codes via tree packings. SIAM Journal on Computing, 53(2):389–430, 2024.

[GM26]

Utkarsh Gupta and Hessam Mahdavifar. On the security of linear secret sharing with general noisy side-channel leakage. In Joan Daemen and Emmanuel Thomé, editors, Advances in Cryptology – EUROCRYPT 2026, Part VII, volume 16547 of Lecture Notes in Computer Science, pages 477–505, Cham, 2026. Springer.

[Gow01]

W. T. Gowers. A new proof of Szemerédi’s theorem. Geometric and Functional Analysis, 11(3):465–588, 2001.

[GR08]

Venkatesan Guruswami and Atri Rudra. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Transactions on Information Theory, 54(1):135–150, 2008.

[GS99]

Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed–Solomon and algebraic-geometry codes. IEEE Transactions on Information Theory, 45(6):1757–1767, 1999.

[GT10]

Ben Green and Terence Tao. Linear equations in primes. Annals of Mathematics, 171(3):1753–1850, 2010.

[GW16]

Venkatesan Guruswami and Mary Wootters. Repairing Reed–Solomon codes. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 216–226. ACM, 2016.

[HMNY25]

Jihun Hwang, Hemanta K. Maji, Hai H. Nguyen, and Xiuyu Ye. Leakage-resilience of Shamir’s secret sharing: Identifying secure evaluation places. In Niv Gilboa, editor, 6th Conference on Information-Theoretic Cryptography (ITC 2025), volume 343 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1–3:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025.

[HS23]

Charlotte Hoffmann and Mark Simkin. Stronger lower bounds for leakage-resilient secret sharing. In Progress in Cryptology – LATINCRYPT 2023, volume 14168 of Lecture Notes in Computer Science, pages 215–228, Cham, 2023. Springer.

[HY26]

Shuji Horinaga and Takashi Yamakawa. Worst-case quantum algorithm for optimal polynomial intersection beyond decoded quantum interferometry, 2026. arXiv:2607.14650.

[Jer26]

Fernando Granha Jeronimo. Algorithmic list decoding at capacity and optimal proximity gaps for Reed–Solomon codes, 2026. arXiv:2609.05870, version 1; ECCC Report TR26-169.

[JMB26]

Vahid Jahandideh, Bart Mennink, and Lejla Batina. A decomposition approach for evaluating security of masking. In Advances in Cryptology – ASIACRYPT 2025, Part I, volume 16245 of Lecture Notes in Computer Science, pages 580–612. Springer, 2026.

[Jo26]

Sunghyeon Jo. Efficient exact quantum sampling from the Sun–Wootters distribution for optimal polynomial intersection, 2026. arXiv:2607.16541.

[KA26]

Hiroki Koga and Hiroto Abe. New tight bounds on the local leakage resilience of the additive (n, n)-threshold scheme determined by the eigenvalues of circulant matrices. In Advances in Cryptology – ASIACRYPT 2025, Part VIII, volume 16252 of Lecture Notes in Computer Science, pages 34–66. Springer, 2026.

[Kas25]

Dustin Kasser. An improvement upon the bounds for the local leakage resilience of Shamir’s secret sharing scheme. In Elette Boyle and Mohammad Mahmoody, editors, Theory of Cryptography – TCC 2024, Part IV, volume 15367 of Lecture Notes in Computer Science, pages 395–422, Cham, 2025. Springer. Proceedings of TCC 2024; publisher citation year 2025.

[KJJ99]

Paul C. Kocher, Joshua Jaffe, and Benjamin Jun. Differential power analysis. In Advances in Cryptology – CRYPTO 1999, volume 1666 of Lecture Notes in Computer Science, pages 388–397. Springer, 1999.

[KK23]

Ohad Klein and Ilan Komargodski. New bounds on the local leakage resilience of Shamir’s secret sharing scheme. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology – CRYPTO 2023, Part I, volume 14081 of Lecture Notes in Computer Science, pages 139–170, Cham, 2023. Springer.

[KMN22]

Hamidreza Amini Khorasgani, Hemanta K. Maji, and Hai H. Nguyen. Secure non-interactive simulation from arbitrary joint distributions. In Theory of Cryptography – TCC 2022, Part II, volume 13748 of Lecture Notes in Computer Science, pages 378–407. Springer, 2022.

[KMS19]

Ashutosh Kumar, Raghu Meka, and Amit Sahai. Leakage-resilient secret sharing against colluding parties. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, pages 636–660. IEEE, 2019.

[Koc96]

Paul C. Kocher. Timing attacks on implementations of Diffie–Hellman, RSA, DSS, and other systems. In Advances in Cryptology – CRYPTO 1996, volume 1109 of Lecture Notes in Computer Science, pages 104–113. Springer, 1996.

[Kop26]

Swastik Kopparty. Recovering polynomials over finite fields from noisy character values, 2026. To appear in FOCS 2026. arXiv:2601.07137.

[LS25]

Ray Li and Nikhil Shagrithaya. Near-optimal list-recovery of linear code families. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025), volume 353 of Leibniz International Proceedings in Informatics (LIPIcs), pages 53:1–53:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025.

[LW21]

Ray Li and Mary Wootters. Improved list-decodability of random linear binary codes. IEEE Transactions on Information Theory, 67(3):1522–1536, 2021.

[Man21]

Freddie Manners. True complexity and iterated Cauchy–Schwarz, 2021. arXiv:2109.05731.

[McD89]

Colin McDiarmid. On the method of bounded differences. In J. Siemons, editor, Surveys in Combinatorics, 1989, volume 141 of London Mathematical Society Lecture Note Series, pages 148–188. Cambridge University Press, 1989.

[MNPC+ 21] Hemanta K. Maji, Hai H. Nguyen, Anat Paskin-Cherniavsky, Tom Suad, and Mingyuan Wang. Leakage-resilience of the Shamir secret-sharing scheme against physical-bit leakages. In Advances in Cryptology – EUROCRYPT 2021, Part II, volume 12697 of Lecture Notes in Computer Science, pages 344–374, Cham, 2021. Springer. [MNPC+ 22] Hemanta K. Maji, Hai H. Nguyen, Anat Paskin-Cherniavsky, Tom Suad, Mingyuan Wang, Xiuyu Ye, and Albert Yu. Tight estimate of the local leakage resilience of the additive secret-sharing scheme & its consequences. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022), volume 230 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1–16:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. [MNPCW22] Hemanta K. Maji, Hai H. Nguyen, Anat Paskin-Cherniavsky, and Mingyuan Wang. Improved bound on the local leakage-resilience of Shamir’s secret sharing. In 2022 IEEE International Symposium on Information Theory (ISIT), pages 2678–2683. IEEE, 2022. [MNPCY24] Hemanta K. Maji, Hai H. Nguyen, Anat Paskin-Cherniavsky, and Xiuyu Ye. Constructing leakage-resilient Shamir’s secret sharing: Over composite order fields. In Advances in Cryptology – EUROCRYPT 2024, Part IV, volume 14654 of Lecture Notes in Computer Science, pages 286–315, Cham, 2024. Springer. [MPCSW21] Hemanta K. Maji, Anat Paskin-Cherniavsky, Tom Suad, and Mingyuan Wang. Constructing locally leakage-resilient linear secret-sharing schemes. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, Part III, volume 12827 of Lecture Notes in Computer Science, pages 779–808, Cham, 2021. Springer. [Ngu24]

Hai H. Nguyen. Towards breaking the half-barrier of local leakage-resilient Shamir’s secret sharing. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology – CRYPTO 2024, Part V, volume 14924 of Lecture Notes in Computer Science, pages 257–285, Cham, 2024. Springer.

[Ngu25]

Hai H. Nguyen. Physical-bit leakage resilience of linear code-based secret sharing. In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology – EUROCRYPT 2025, Part VIII, volume 15608 of Lecture Notes in Computer Science, pages 64–93, Cham, 2025. Springer.

[NS20]

Jesper Buus Nielsen and Mark Simkin. Lower bounds for leakage-resilient secret sharing. In Advances in Cryptology – EUROCRYPT 2020, Part I, volume 12105 of Lecture Notes in Computer Science, pages 556–577, Cham, 2020. Springer.

[O’D14]

Ryan O’Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.

[PR13]

Emmanuel Prouff and Matthieu Rivain. Masking against side-channel attacks: A formal security proof. In Advances in Cryptology – EUROCRYPT 2013, volume 7881 of Lecture Notes in Computer Science, pages 142–159. Springer, 2013.

[RV25]

Nicolas Resch and S. Venkitesh. List recoverable codes: The good, the bad, and the unknown (hopefully not ugly), 2025. arXiv:2510.07597.

[RW14]

Atri Rudra and Mary Wootters. Every list-decodable code for high noise has abundant near-optimal rate puncturings. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 764–773. ACM, 2014.

[Sha79]

Adi Shamir. How to share a secret. Communications of the ACM, 22(11):612–613, 1979.

[ST20]

Chong Shangguan and Itzhak Tamo. Combinatorial list-decoding of Reed–Solomon codes beyond the Johnson radius. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 538–551. ACM, 2020.

[Sud97]

Madhu Sudan. Decoding of Reed Solomon codes beyond the error-correction bound. Journal of Complexity, 13(1):180–193, 1997.

[SV19]

Akshayaram Srinivasan and Prashant Nalini Vasudevan. Leakage resilient secret sharing and applications. In Advances in Cryptology – CRYPTO 2019, Part II, volume 11693 of Lecture Notes in Computer Science, pages 480–509. Springer, 2019.

[SW26a]

Yihang Sun and Mary Wootters. Improved local leakage resilience of Shamir secret sharing and worst-case optimal polynomial intersection, 2026. arXiv:2610.12357, version 1.

[SW26b]

Yihang Sun and Mary Wootters. On worst-case optimal polynomial intersection, 2026. arXiv:2604.09533.

[TV06]

Terence Tao and Van H. Vu. Additive Combinatorics, volume 105 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2006.

[TYB17]

Itzhak Tamo, Min Ye, and Alexander Barg. Optimal repair of Reed–Solomon codes: Achieving the cut-set bound. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science, pages 216–227. IEEE, 2017.

[Ven26]

S. Venkitesh. Partial derandomization for leakage-resilient Shamir’s secret sharing over composite order fields. In Yevgeniy Dodis, editor, 7th Conference on Information-Theoretic Cryptography (ITC 2026), volume 385 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026.

List recovery with growing input lists

We prove Theorem 4, keeping the dependence on the input-list size explicit. Interpolation gives a differential equation satisfied by every candidate. We then count its solutions using their initial coefficients and their agreement equations. We state the interpolation input from [Jer26] explicitly and give the remaining counting argument below. P The Hasse derivatives are defined by P (X + U ) = j≥0 P [j] (X)U j . Write degtot Y Q for total degree in all the Y -variables. Lemma 18 (Interpolation, from [Jer26, Proposition 3.7]). Fix 0 < ζ < 1. There are constants bζ > 0 and tζ ≥ 1 such that the following holds. Let α1 , . . . , αn ∈ Fp be distinct, let S1 , . . . , Sn ⊆ Fp , P and put M = i |Si |. If integers K, A, t satisfy 2 ≤ K ≤ A ≤ n,

A 1 ≥ , K −1 1 − ζ/2

tζ ≤ t < K,

M ≤ bζ (K − 1)tζ/3 ,

then there is a nonzero Q(X, Y0 , . . . , Yt ) with & 3

degtot Y Q≤

degX Q ≤ t n,

t3 A , K −1

such that every P ∈ Fp [X] of degree below K agreeing with the lists on at least A coordinates satisfies Q(X, P, P [1] , . . . , P [t] ) = 0. Apply the cited proposition with derivative order t, multiplicity t3 , ϑ = ζ/2, and λ = 2/3. Its incidence exponent is λϑ = ζ/3. The monomial restrictions in [Jer26, Equations (11)–(12)] give the stated total Y -degree bound and degX Q < t3 A ≤ t3 n. The interpolation works over any coefficient field; no upper bound on p is required. Lemma 19 (Counting solutions with many agreements). Let 1 ≤ h ≤ n, t, B ≥ 1, and D0 ≥ 0 P be integers, with p > max{h − 1, B}. Fix distinct αi ∈ Fp , lists Si with M = i |Si | ≥ 1, and a nonzero Q ∈ Fp [X, Y0 , . . . , Yt ] with degX Q ≤ D0 and degtot Y Q ≤ B. The number of polynomials P ∈ Fp [X] of degree below h satisfying Q(X, P, P [1] , . . . , P [t] ) = 0, is at most 2

B D0 + B(h − 1) + 1

t X

|{i : P (αi ) ∈ Si }| ≥ h

(M E)j ,

E = 8B(h + 1)2 .

j=0

Proof. We make the recurrence and counting arguments of [Jer26, Lemmas 5.6–5.7 and 6.2] explicit. If h ≤ t, there are at most M h ordered choices of h agreements at distinct coordinates, each determining at most one polynomial P . This satisfies the claimed bound. Assume h > t, and work over the algebraic closure Fp . We use the following standard form of Bézout’s inequality (see [Jer26, Lemma 5.3]). The degree of an irreducible algebraic set is the number of points, counted with multiplicity, in a generic linear section of complementary dimension. A hypersurface defined by a nonzero polynomial of degree at most B has sum of component degrees at most B. Intersecting an irreducible component with a degree-E equation that does not vanish identically on it lowers its dimension and increases the sum of degrees by a factor of at most E. A zero-dimensional algebraic set has at most its sum of degrees many points. 39

If Q is independent of all Y -variables, there are no solutions. Otherwise let s ≤ t be its largest Y -index and put H = ∂Q/∂Ys = ̸ 0; nonvanishing follows from B < p. First count candidates with H(X, P, . . . , P [s] ) ̸= 0. Fix a set of D0 + B(h − 1) + 1 distinct points α ∈ Fp , independently of P . Since this polynomial has degree at most D0 + (B − 1)(h − 1), it is nonzero at one of these points. The algebraic closure allows this choice even when the number of points exceeds p. Recovering the coefficients at a fixed α. Write P (α + U ) = c = (c0 , . . . , cs ), and set Hα (c) = H(α, c0 , . . . , cs ). The identity [i]

P (α + U ) =

h−1 X q=i

Ph−1

q=0 cq U

q , with c ∈ F , put q p

q cq U q−i i

shows that the coefficient of U j , for 1 ≤ j ≤ h − 1 − s, in the substituted equation is !

s+j Hα (c)cs+j + Rj (c0 , . . . , cs+j−1 ) = 0. s j Indeed, in P [s] (α + U ), the coefficient cs+j first occurs as s+j s cs+j U . In every lower derivative P [i] it occurs at order s + j − i > j. Thus it contributes to the coefficient of U j only through a single Ys factor, with all other factors evaluated at U = 0; the resulting multiplier is Hα (c). Since s + j ≤ h − 1 < p, the binomial coefficient is nonzero. On Hα ̸= 0, these equations recursively give

cs+j =

Nj (c) , Hα (c)2j−1

deg Nj ≤ 4Bj 2 .

Here and below, degrees are in the initial coefficients c. To verify the bound, consider the noninitial P factors cs+a1 , . . . , cs+av in a monomial of Rj . Their orders satisfy u au ≤ j, and the case v = 1, a1 = j is absent. Thus, for j ≥ 2, X

(2au − 1) ≤ 2j − 2,

a2u ≤ j 2 − 2j + 2.

Using the previous recurrences and clearing denominators with Hα2j−2 gives deg Nj ≤ B + 4B(j 2 − 2j + 2) + (2j − 2)B ≤ 4Bj 2 . For j = 1, directly deg N1 ≤ B. This proves the bounds without any hidden dependence on B or t. Counting the initial coefficients. The recurrences define a polynomial Pc of degree below h whenever Hα (c) ̸= 0. Its first Taylor coefficients are c, so this parametrization is injective. Every candidate at this α lies in Q(α, c0 , . . . , cs ) = 0, Hα (c) ̸= 0. We may count all such initial vectors over Fp satisfying the agreement equations, even if their polynomials do not solve the full differential equation. When this set is nonempty, its defining polynomial is nonzero, because its derivative in cs is Hα . The hypersurface therefore has dimension at most s and sum of component degrees at most B. Each of the M possible agreements becomes a polynomial equation after multiplication by Hα2h : Hα (c)2h Pc (αi ) − b = 0,

b ∈ Si .

The preceding numerator bounds give degc Hα2h (Pc (αi ) − b) ≤ 4B(h − 1)2 + 2hB + 1 ≤ E.

Any h satisfied agreements at distinct coordinates determine Pc , hence c, uniquely where Hα ̸= 0. Let W be a positive-dimensional irreducible component through a candidate c. Since Hα (c) ̸= 0, the set W ∩ {Hα ̸= 0} is a nonempty open subset of W . If all of the candidate’s agreement equations vanished identically on W , every point in this open subset would give the same polynomial Pc , hence the same initial vector c, a contradiction. At least one agreement equation therefore cuts W properly. Repeating lowers the dimension to zero after at most s cuts. Hence every candidate at this α lies in a zero-dimensional component obtained from a component of {Q(α, c) = 0} by at most s successive proper cuts with agreement equations. Components contained in Hα = 0 can be discarded. For each ordered choice of equations, retain only proper intersections at each step. For j cuts there are at most M j such choices, and Bézout bounds their contribution by BE j for each choice. Hence s #{candidates at this α} ≤ B

(M E)j .

j=0

The remaining candidates satisfy H(X, P, . . . , P [s] ) = 0 identically. Repeat with H in place of Q. Each repetition lowers the total Y -degree without increasing the X-degree, so there are at most B stages. At each stage there are at most D0 + B(h − 1) + 1 choices of α from the fixed set. Summing the displayed bound over these stages and points proves the lemma. Proof of Theorem 4. Write h for the code dimension. Scaling Si by vi−1 reduces GRS codes to P ordinary RS codes. Fix lists of size at most ℓ and put M = i |Si | ≤ nℓ; if M = 0, there are no candidates. Set A = h + ⌈ζn⌉ ≤ n, K = ⌈(1 − ζ/2)A⌉ . The agreement threshold A corresponds exactly to the radius ⌊n − h − ζn⌋. For sufficiently large n, depending only on ζ (ensured by enlarging cζ ), K − h ≥ ζn/2, ζ/3

Choose aζ ≥ tζ with bζ ζaζ

K − 1 ≥ (1 − ζ/2)A/2 ≥ ζn/4, l

A 1 > . K −1 1 − ζ/2

≥ 4, and put t = aζ ℓ3/ζ . Then M ≤ nℓ ≤ bζ (K − 1)tζ/3 .

Increasing cζ , the hypothesis n ≥ cζ ℓ9/ζ ensures t < K and 5t3 ≤ n. Apply Lemma 18; every candidate of degree below h ≤ K satisfies its equation, with &

D0 = t n ≤ n ,

t3 A B= ≤ 5t3 ≤ n < p. K −1

Thus Lemma 19 applies. Since h ≤ n < p, M ≤ n2 , and E = 8B(h + 1)2 ≤ 32n3 , it gives 3/ζ

#{candidates} ≤ 3n4 (t + 1)(32n5 )t ≤ n18t ≤ ncζ ℓ

after enlarging cζ once more. All constants depend only on ζ, and none depend on p.

An alternative list-recovery calculation from DKT

We give a separate derivation of Theorem 4 from Dao, Kominers, and Thaler (DKT) [DKT26]. Their Theorem G.2 states a list-recovery bound for fixed input-list size. The finite estimates in their Lemma 6.2 and the proof of Theorem 6.7 make the dependence on that size explicit, as follows. Alternative proof of Theorem 4. Write h for the code dimension and fix lists Si of size at most ℓ. Scaling Si by vi−1 reduces GRS codes to ordinary RS codes. We count polynomials of degree below h with at least A = h + ⌈ζn⌉ agreements; this is exactly the radius ⌊n − h − ζn⌋ in the theorem. Parameters.

Set ρ = max{h/n, ζ/4},

a = ρ + ζ/2.

Since h ≤ (1 − ζ)n, ζ/4 ≤ ρ ≤ 1 − 3ζ/4,

a ≤ 1 − ζ/4 < 1,

h ≤ ρn,

an ≤ A.

Choose the derivative order t, interpolation multiplicity s, and total degree bound B in the derivative variables by &

(

1 t = max 519, 6

320ℓ 9ζ

2/ζ )'

s = 300t2 log(6t) ,

B = ⌈8s/ζ⌉ .

Here t is denoted by d in DKT. Their Equation (83) gives 9ρ (6t)(a−ρ)/a (1 + 1/t) 40 9ζ ≥ (6t)ζ/2 (1 + 1/t) ≥ 2ℓ(1 + 1/t). 160

Γ(ρ, a, t) =

DKT’s Lemma 6.2 bounds the finite interpolation ratio from below by Γ(ρ, a, t)e−1677/10 > ℓ when the local constraint rank is nonzero; when it is zero, the same lemma gives a nonzero interpolation space directly. Thus the interpolation condition in the proof of their Theorem G.2 holds for lists of size ℓ, with the displayed finite choice of s. Length and characteristic. The interpolant in the proof of DKT’s Theorem 6.7 has total degree at most ⌈2s/ρ⌉ ≤ B in the derivative variables, and the construction requires t+1 1 n ≥ max , ⌈2s/ρ⌉ + 1, ρ 1−ρ

Our choices give t ≥ ℓ, s ≥ t + 1, and t+1 4(t + 1) ≤ ≤ B, ρ ζ

1 4 ≤ < B, 1−ρ 3ζ

ℓ ≤ B,

4/ζ < B.

Consequently n ≥ B + 2 suffices. It also gives p > n > max{h − 1, t, B}, satisfying the characteristic condition of DKT’s Theorem G.2. Finally, t = Oζ (ℓ2/ζ ),

B = Oζ (ℓ4/ζ log(2ℓ)),

so the theorem’s hypothesis n ≥ cζ ℓ9/ζ ensures n ≥ B + 2 after increasing cζ . 42

List size.

DKT’s Theorem G.2, Equation (147), now gives #{candidate polynomials} ≤ B 2

2ℓB a−ρ

nt = B 2 3/ζ

≤ n4t+2 ≤ n5t ≤ ncζ ℓ

4ℓB ζ

The second line uses B, ℓ, 4/ζ ≤ n and t ≥ 2; the last inequality follows by increasing cζ once more. All constants depend only on ζ, not on p.

Local Leakage Resilience of Shamir Secret Sharing: Below Half Threshold Rate

Analyze & explore related research in Conceptio

Related documents