Discrepancy for Random Linear Codes

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Discrepancy for Random Linear Codes

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cryptography, security, privacy, cybersecurity

Discrepancy for Random Linear Codes Dean Doron∗

Tal Leonov∗

Jonathan Mosheiff∗

Nicolas Resch‡

Henrique Navas†

João Ribeiro†

arXiv:2606.24471v1 [cs.IT] 23 Jun 2026

Abstract We show that random linear codes possess nearly optimal discrepancy-type properties in a broad range of settings. Our main results are two general discrepancy theorems: one controls all translates of a fixed test, and the other controls large families of Fourier-pseudorandom tests. As motivating applications of these two theorems, respectively, we show that: • Random linear codes behave essentially like unstructured random codes for list-decoding from errors above capacity. More precisely, a random linear code C ⊆ Fnq of rate 1 − 1 n n logq |Bρ | + ε, where |Bρ | is the volume of a radius-ρ Hamming ball in Fq , satisfies |C ∩ B| = (1 ± o(1))

|C| · |B| qn

simultaneously for all radius-ρ Hamming balls B in Fnq with high probability. This vastly generalizes the previously best known fact that random linear codes of this rate have covering radius at most ρn with high probability (Blinovsky, 1987). • Over prime fields, random linear codes behave essentially like unstructured random codes for zero-error list-recovery above capacity. More precisely, for a prime q > 2 and input list size 2 ≤ ℓ ≤ q − 1, a random linear code C ⊆ Fnq of rate 1 − logq ℓ + ε will satisfy |C ∩ S| = (1 ± o(1))

|C| · ℓn qn

simultaneously for all combinatorial rectangles S = S1 × S2 × · · · × Sn , where |Si | = ℓ for all i, with high probability. We use this to show the abundance of n-party linear ramp secret sharing schemes over n Fq with, say, privacy threshold approximately 2 log q and reconstruction threshold approx5n imately 2 log q that are resilient against balanced local leakage functions. Prior work on the existence of leakage-resilient linear secret sharing was stuck at thresholds above n/2 for both threshold and ramp schemes, even for the special case of balanced leakage functions. The translate-family result, and hence the list-decoding application, applies over arbitrary finite fields, even when the field size grows with n. The list-recovery and leakage applications over prime fields hold under moderate-growth conditions on q, for example q ≤ n1/5−o(1) . Our results are obtained through a careful second-moment analysis of the evolution of intersection sizes as random generators are added to C one by one. ∗

Stein Faculty of Computer and Information Science, Ben-Gurion University. [email protected], [email protected], [email protected]. † Instituto de Telecomunicações and Departamento de Matemática, Instituto Superior Técnico, Universidade de Lisboa. [email protected], [email protected]. ‡ Informatics Institute, University of Amsterdam. [email protected].

Contents 1 Introduction 1.1 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Additional Context and Related Works . . . . . . . . . . . . . . . . . . . . . . . . . .

3 5 8

2 Main Results 2.1 Notation and Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Discrepancy Results for Random Linear Codes . . . . . . . . . . . . . . . . . . . . . 2.3 Applications to List-Decoding and List-Recovery . . . . . . . . . . . . . . . . . . . .

10 11 12 15

3 Proof Overview

4 Random Linear Codes are Smooth—Proof of Theorems 2.4 and 2.5 4.1 Smoothness via a Direct Second Moment Argument . . . . . . . . . . . . . . . . . . 4.2 Self Convolution and Variance of the Relative Deviation . . . . . . . . . . . . . . . . 4.3 Controlling the Deviation throughout the Construction Sequence . . . . . . . . . . .

23 24 27 30

5 α-Concentration of Combinatorial Rectangles

6 Improved Resilience of Linear Ramp Secret Sharing Schemes against Balanced Leakage Functions 43 6.1 Leakage-Resilience of Linear Secret Sharing Schemes . . . . . . . . . . . . . . . . . . 44 6.2 Prior Work on Leakage-Resilience of Linear Secret Sharing Schemes and Our Result 45 6.3 Linear Ramp Secret Sharing from Linear Codes . . . . . . . . . . . . . . . . . . . . . 47 6.4 Resilience of Massey Ramp Secret Sharing Schemes from Random Linear Codes against γ-Balanced Leakage Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 49

Introduction

A central theme in coding theory is to understand when random linear codes behave like unstructured uniformly random codes. This question is especially natural for list-decoding and list-recovery, two important relaxations of unique decoding. A code C ⊆ Fnq is called (ρ, L)-list-decodable (from errors) if, whenever a channel corrupts a ρ-fraction of symbols, there are at most L codewords that could have produced the received word. Combinatorially, this means that for every z ∈ Fnq , |C ∩ Bρ (z)| ≤ L, where Bρ (z) denotes the Hamming ball of radius ρn centered at z.1 Unique decoding is the special case L = 1. List-recovery is a further relaxation of list-decoding: instead of receiving a single word in Fnq , the receiver obtains input lists (S1 , . . . , Sn ), where each Si ⊆ Fq has size at most ℓ, and must return all codewords that largely agree with these lists. We focus on the important special case of zero-error list-recovery. A code C is (ℓ, L)-list-recoverable if for every such tuple (S1 , . . . , Sn ), |C ∩ (S1 × S2 × · · · × Sn )| ≤ L. Thus, list-decoding asks for small intersections with Hamming balls, while zero-error list-recovery asks for small intersections with combinatorial rectangles of bounded side lengths. With these notions in mind, a basic question is: for a code of a given rate R, how small can the list size L be? Both list-decoding and list-recovery exhibit phase transitions: below a certain rate, constant list size is possible; above it, every code must have exponentially large list size. For list-decoding, fix a field Fq and an error radius ρ. For every ε > 0, the following are known: • Below capacity. There exist codes of rate 1 − n1 logq |Bρ | − ε that are (ρ, L = O(1/ε))-listdecodable from errors. • Above capacity. Every code C ⊆ Fnq of rate 1 − n1 logq |Bρ | + ε has some center z ∈ Fnq for which |C ∩ Bρ (z)| ≥ q εn . We therefore call 1 − n1 logq |Bρ | the list-decoding capacity.2 The phase transition for zero-error list-recovery is analogous, with capacity 1 − logq ℓ. Unstructured uniformly random codes achieve the random-code benchmark on both sides of capacity. A standard probabilistic-method argument shows that a uniformly random code of rate 1 − n1 logq |Bρ | − ε is (ρ, L = O(1/ε))-list-decodable with high probability. Above capacity, a uniformly random code C ⊆ Fnq of rate 1 − n1 logq |Bρ | + ε satisfies, simultaneously for all z ∈ Fnq 1 2

Bρ (z) consists of all y ∈ Fn q at Hamming distance at most ρn from z, i.e., all y such that |{i : yi ̸= zi }| ≤ ρn. Recall that n1 logq |Bρ | = hq (ρ) − o(1), where hq (x) = x logq

q−1 1 + (1 − x) logq x 1−x

is the q-ary entropy function. Hence, 1 − hq (ρ) is also often termed the list-decoding capacity.

with high probability, |C ∩ Bρ (z)| = (1 ± o(1))

|C| · |Bρ | = (1 ± o(1))q εn . qn

(1)

Analogous statements hold for list-recovery. A long line of work has asked whether random linear codes match the performance of unstructured random codes for list-decoding and list-recovery. Most prior work has focused on the below-capacity setting, where random linear codes are known to match uniformly random codes in some parameter regimes [GHSZ02, GHK11, CGV13, Woo13, RW14, LW20, AGL24, DMRR25], but not in others [Gur03, GLM+ 21, RY24, LMS25, CZ25, LS25]. Our understanding of the abovecapacity setting is much poorer. This leads to the question that motivates our work: How well do random linear codes approximate uniformly random codes in list-decoding and list-recovery at rates above capacity? Take list-decoding as a running example. Above capacity, list-decoding for random linear codes is naturally a discrepancy problem: the expected size for |C ∩ Bρ (z)| is |C| · |Bρ |/q n ≈ q εn , and the goal is to show that a random linear code has approximately this many codewords in every Hamming ball. This is qualitatively different from the below-capacity setting. Below capacity, the benchmark |C|·|Bρ |/q n is exponentially small; moreover, for a linear code, the zero codeword always lies in Bρ (0), while for centers z with 0 ∈ / Bρ (z) the fixed-center expectation is exponentially small. Thus the below-capacity problem is not a uniform multiplicative-discrepancy question in the same sense. As we discuss in detail later, this above-capacity viewpoint leads us to discrepancy-type questions that generalize list-decoding and list-recovery. Toward proving Eq. (1) for random linear codes, one could first ask for the much weaker but still nontrivial guarantee that a random linear code C ⊆ Fnq of rate 1 − n1 logq |Bρ | + ε satisfies |C ∩ Bρ (z)| ≥ 1 for every z ∈ Fnq with high probability. This is precisely the statement that C has covering radius at most ρn. Blinovsky proved this over arbitrary fields almost forty years ago [Bli87]; see also the discussion in the book of Cohen, Honkala, Litsyn, and Lobstein on covering codes [CHLL97, Theorem 12.3.5]. To the best of our knowledge, this covering result is essentially all that was previously known about list-decoding random linear codes above capacity. Beyond being a natural question about the geometry of subspaces of Fnq , discrepancy questions for random linear codes above capacity arise in several other settings. For example, zero-error list-recovery above capacity appears naturally in the study of leakage-resilient linear secret-sharing schemes. Roughly speaking, such schemes should ensure that leaking, say, one bit of information about each share reveals almost nothing about the secret. There is a natural way, due to Massey, to turn a linear code into a secret-sharing scheme. For such a scheme, leakage resilience can be phrased as follows: for any functions f1 , . . . , fn : Fq → {0, 1}, the distribution of (f1 (c1 ), . . . , fn (cn )), where c = (c1 , . . . , cn ) is sampled uniformly from C, should be close in total variation distance to the distribution of (f1 (x1 ), . . . , fn (xn )), where x = (x1 , . . . , xn ) is sampled uniformly from Fnq . For leakage bits b1 , . . . , bn ∈ {0, 1}, put Si = fi−1 (bi ). Then Pr[(f1 (c1 ), . . . , fn (cn )) = (b1 , . . . , bn )] = 4

|(S1 × · · · × Sn ) ∩ C| . |C|

The numerator is the intersection of the code with a combinatorial rectangle, exactly the kind of quantity controlled by zero-error list-recovery. In this application, assuming the sets Si are not too small, the relevant intersection size is expected to be exponential; the point is not to make the list small, but to show that its exponential size is the correct one.

1.1

Our Contributions

We show that random linear codes match the performance of uniformly random codes in listdecoding (over any field) and zero-error list-recovery (over prime fields) above capacity. In fact, we go further than that. We prove two main discrepancy theorems for random linear codes which show that random linear codes have strong above-capacity discrepancy properties for a broad class of combinatorial tests, including the tests arising from list-decoding over any field and zero-error list-recovery over prime fields. Our new theorems also imply new results about leakage-resilient secret sharing. We state simplified versions of our general theorems here, specialized to the main motivating examples. The body of the paper gives the more general formulations. We first introduce a useful normalization. For a code C ⊆ Fnq and a nonempty set B ⊆ Fnq , define the relative deviation of C with respect to B by δC,B :=

Prx∼C [x ∈ B] q n · |C ∩ B| −1= − 1. Prx∼Fnq [x ∈ B] |C| · |B|

(2)

Thus |δC,B | ≤ τ is equivalent to (1 − τ )

|C| · |B| |C| · |B| ≤ |C ∩ B| ≤ (1 + τ ) . n q qn

List-Decoding and Beyond. Our first theorem applies to all translates of a single set. As we discuss below, this is a more general setting than list-decoding. Theorem 1.1 (Informal; see Theorem 2.4). For any constant prime power q and every n ∈ N the following holds. Let B ⊆ Fnq be nonempty, and for z ∈ Fnq define Bz := z + B. Let 1 logq |B|, n and fix η ∈ (0, 1 − β). Let C be a random linear code of rate R = β + η. Then, with probability at least 1 − q −Ω(ηn) , ∀z ∈ Fnq , |δC,Bz | ≤ q −Ω(ηn) . β := 1 −

For list-decoding, take B = Bρ (0). Then β = 1 − n1 logq |Bρ |, and Theorem 1.1 says that a random linear code of rate 1 − n1 logq |Bρ | + η has, with high probability, the correct intersection size |C| · |Bρ (0)| |C ∩ Bρ (z)| = (1 ± q −Ω(ηn) ) qn n for every center z ∈ Fq . In particular, this recovers and significantly strengthens Blinovsky’s covering-radius theorem [Bli87], which only guarantees that every Hamming ball contains at least one codeword. We additionally remark that defining a “capacity” with respect to an arbitrary set B via the formula 1 − n1 logq |B| is not new to our work; it appeared in an earlier work of Loeliger [Loe94]. 5

List-Recovery and Beyond. The translate theorem is well suited to list-decoding because all Hamming balls of a fixed radius are translates of one another. For list-recovery, the relevant rectangles are not all translates of a single set. Our second theorem handles large families of sets, provided the sets satisfy a Fourier pseudorandomness condition. We say that a set B ⊆ Fnq is α-Fourier-concentrated if ∀y ∈ Fnq ,

wt(y) , E [χy (Z)] ≤ α

Z∼B

where Z is uniform over B and χy is the Fourier character defined in Section 2.1. Informally, this condition says that B has little correlation with any nontrivial linear test, with the correlation decaying exponentially in the Hamming weight of the test. Theorem 1.2 (Informal; see Theorem 2.5). For any constant prime power q and every n ∈ N the following holds. Let B be a family of nonempty α-Fourier-concentrated subsets of Fnq , and let β := 1 −

1 min log |B|. n B∈B q

Fix η ∈ (0, 1 − β), and let C be a random linear code of rate β + η. Then, with probability at least 2

1 − q −Ωα (ηn) − |B| q −Ωα (n ) , we have |δC,B | ≤ q −Ω(ηn) .

∀B ∈ B,

As an example, consider zero-error list-recovery with input list size ℓ. For the upper-bound guarantee it suffices to control rectangles with side length exactly ℓ, since smaller input lists can be padded. Thus consider rectangles S1 × · · · × Sn with Si ∈ Fℓq . Over prime fields, standard Fourier estimates imply that such rectangles are α-Fourier-concentrated for α = α(q, ℓ) < 1, some 2) q n o(n assuming 2 ≤ ℓ ≤ q − 1. Therefore, in any regime where the family size ℓ is q , Theorem 1.2 implies that a random linear code of rate 1 − logq ℓ + η satisfies, with high probability, Fq ∀S1 , . . . , Sn ∈ , ℓ

1 − q −Ωq,ℓ (ηn)

|C| · ℓn qn

|C| · ℓn ≤ |C ∩(S1 ×· · ·×Sn )| ≤ 1 + q −Ωq,ℓ (ηn) . qn

In particular, the upper bound gives the expected above-capacity zero-error list-recovery guarantee for random linear codes in these regimes. Application to Leakage-Resilient Linear Ramp Secret Sharing. Our Theorem 1.2 yields new results about the local leakage-resilience of linear secret sharing schemes. We present here a brief overview of this topic and leave a more careful discussion to Section 6. Informally, a threshold secret sharing scheme encodes a secret into a tuple of n shares such that any appropriately large subset of shares determines the secret, while any appropriately small subset of shares reveals no information about the secret. For applications we often require that the secret sharing scheme be linear. Roughly speaking, this means that the secret and the shares are all elements of Fq , and any linear combination of shares of two secrets yields a valid sharing of the linear combination of the two secrets. When q is much smaller than the number of parties n (i.e., when we aim for small shares), there must be an Ω(n) gap between the reconstruction threshold 6

trec (all subsets of shares of size at least trec can reconstruct the secret) and the privacy threshold tpriv (all subsets of shares of size at most tpriv give no information about the secret) unless both trec and tpriv are unusually large [CCX13]. Such schemes with a gap between thresholds are called ramp secret sharing schemes, and they are the focus of our discussion. Motivated by side-channel attacks, recently there has been significant interest in understanding the resilience of linear secret sharing schemes against attacks that leak a small amount of side information from every share. More precisely, in the most popular model of bounded local leakage [BDIR21], an adversary chooses local leakage functions gi : Fq → {0, 1} for i ∈ [n], and, letting S = (S1 , . . . , Sn ) denote the n shares of some secret, learns the n-bit leakage g(S) = (g1 (S1 ), g2 (S2 ), . . . , gn (Sn )). Then, we want to establish that linear secret sharing schemes are information-theoretically resilient against this type of leakage, meaning that g(S) and g(S ′ ) should be very close in statistical distance for any sharings S and S ′ of two distinct secrets s and s′ , respectively. Establishing leakage-resilience of secret sharing schemes is easier for larger reconstruction threshold. Therefore, a central research direction has been to establish the existence of leakage-resilient linear secret sharing schemes with small reconstruction threshold (and, in the context of ramp secret sharing, with an as-small-as-possible gap between the privacy and reconstruction thresholds). State-of-the-art results have only managed to show existence of such leakage-resilient schemes for reconstruction thresholds above n/2 [MPSW21, TX22, KK23, Kas24, Ngu24]. Remarkably, this holds true even if we focus only on the restricted sub-family of balanced leakage functions, which, informally, satisfy |gi−1 (0)| ≈ |gi−1 (1)| for all i ∈ [n]. In contrast, we can do much better for unbalanced leakage functions [KK23]. This suggests that balanced leakage functions are the barrier towards further progress in leakage-resilient secret sharing. We use Theorem 1.2 to obtain an improved existential result about locally leakage-resilient linear ramp secret sharing schemes against balanced leakage functions. In fact, our result applies to a much weaker notion of “balanced”. To avoid complicating the exposition, we state here an informal and simplified version of our result and leave details Section 6. Theorem 1.3 (Informal version; see Theorems 6.6 and 6.15 and Corollary 6.16). Fix an arbitrary 1 prime q ≥ 11 and an arbitrary η ∈ (0, 2 log q ). Then, for all sufficiently large n there exists an n-party linear ramp secret sharing scheme over Fq with reconstruction and privacy thresholds trec and tpriv satisfying (η − o(1)) n ≤ tpriv < trec ≤ η + log2 q + o(1) n

that is resilient against all balanced leakage functions. As mentioned above, in the setting of Theorem 1.3 (constant q and linear reconstruction threshold), an Ωq (n) gap between trec and tpriv is unavoidable [CCX13]. We achieve a gap of ( log2 q +o(1))n, and both our privacy and reconstruction thresholds are linear in n. Furthermore, our reconstruction threshold can be made smaller than cn for any constant c > 0 by taking q to be a sufficiently large constant. In contrast, prior results were stuck at thresholds above n/2 even only for very balanced leakage functions. A Glimpse at our Techniques. While we will provide a much more detailed overview of our techniques below in Section 3, we briefly give a birds-eye view of our approach. To construct a 7

random linear code, we imagine constructing a random linear code by iteratively sampling uniformly random basis vectors. That is, define C0 := {0}, and inductively put Ci := Ci−1 + span{ui }, where ui is sampled uniformly at random from Fnq : the final code is C = Ck , where k = Rn is the target dimension. The main task, then, is to control the growth of the intersections |Ci ∩ B| for increasing i = 0, 1, . . . , k, for all sets B under consideration. A first, fairly obvious fact is that the growth rate is “correct” in expectation – after all, we are trying to argue that the |Ck ∩ B| is always roughly its expectation! The main challenge is to get a tail bound: we need to argue that it is very unlikely that any |Ci ∩ B| deviates far from its expectation. The main tool at our disposal is the fact that the events “x ∈ C” (over distinct x) are “nearly” pairwise independent (there is a slight exception from colinear pairs, but this is negligible): thus, a second-moment method is natural. The challenge is that applying a second moment argument to each B under consideration and then applying a union bound is doomed to fail (there are more sets to union over than the reciprocal of the failure probability). Our main accomplishment is to identify a single common event that implies all the growth rates are adequately controlled; additionally, this event can be proved likely to occur via a basic second-moment argument.

1.2

Additional Context and Related Works

Having now given a taste of our results and our techniques, we now discuss (additional) related works, to help situate our contribution. Covering Radius. As mentioned above, in studying codes above capacity the parameter that has seen the most attention is its covering radius ρ, and that work by Blinovsky from the 80’s [Bli87] demonstrates that codes of rate 1 − n1 logq |Bρ | + η are very likely to satisfy |C ∩ Bρ (z)| ≥ 1 for all z ∈ Fnq . The textbook argument of this fact [CHLL97] indeed considers revealing the random linear codes basis vectors one at a time, analogously to us. However, a notable simplification here is that the property of having covering radius ρ is monotone: once a code covers a certain vector z, adding additional basis vectors cannot “undo” this. The argument of [CHLL97] exploits this fact, essentially by arguing that after a certain number of steps “almost all” points are covered, and then adding a handful of more basis vectors to handle the uncovered vectors (in particular, the union bound here can be much smaller). In contrast to this, since we establish a two-sided bound, we are not able to argue that certain vectors z are “satisfied,” as every step could potentially cause an issue. In particular, while covering codes can be viewed as codes “above capacity,” the defining property is not a real “discrepancy” problem, as we focus on addressing here. Linear Hashing. Discrepancy questions for random linear codes above capacity do arise in the study of linear hashing [ADM+ 99, DD22, JKZ25, Bsh26]. Here one fixes a subset S ⊆ Fnq and, identifying C with the kernel of a random linear map, asks that every translate y +S have about the expected intersection size with C. The relevant regime is again just above the natural threshold: C is chosen so that |C| · |S| = q n+O(1) . The main difference here is that we look at codes with constant relative gap above capacity (i.e., |C| · |S| = q (n+ε)n ): it is an interesting open problem to determine if our techniques can additionally work with this narrower gap. We remark that most of these works achieve bounds only over the binary field [ADM+ 99, JKZ25, Bsh26]; only the work of Dhar and Dvir [DD22] achieves bounds over arbitrary fields (as we do). 8

Potential Function-Based Arguments. Prior works [GHSZ02, LW20, JKZ25, Bsh26] have used potential function-based arguments to study the list-decodability of random linear codes below capacity and linear hashing. Briefly, all these arguments consider a potential function of the form Φ(C) = EX∈Fn2 b|C∩(X+S)| , where S is the set under consideration (Bρ (0) for list-decoding, or an arbitrary set for linear hashing), and b > 0 is an appropriate base for the exponential (about 2n/L for list-decoding, b ≤ 1 for linear hashing). As in our work, the arguments in these works consider constructing the codes by including a basis vector one at a time, and observing how this potential function changes. The crucial observation is that for any fixed code C, we have EU ∼Fn2 [Φ(C + ⟨U ⟩)] ≤ Φ(C)2 . That is, on average over the newly included basis vector, the k potential is squared. By iterating this, one obtains a bound of the form Φk ≤ Φ({0})2 , which is enough to show that some linear code exists with the desired property (this is essentially where the argument of [GHSZ02] stops); later works [LW20, JKZ25, Bsh26] refine this argument to also obtain a statement that holds with high probability. Establishing that this potential function squares crucially uses the assumption that the field is binary. Over the binary field, every line consists of just two points; additionally, note that adding a random basis vector essentially amounts to adding a line at every codeword in a random direction. For random linear codes (over any field), the events “x ∈ C” (over distinct non colinear vectors x) are always pairwise independent; however, they fail to be even 3-wise independent (for example, conditioned on x ∈ C and y ∈ C, it holds that x + y ∈ C with probability 1). In particular, one obtains correlations in computing EU ∼Fn2 [Φ(C + ⟨U ⟩)] that appear hard to handle. Thus, this potential function-based argument – while extremely elegant – is currently limited to F2 . In fact, a motivation for our work was to develop techniques allowing for an analysis over arbitrary fields. We remark that by combining the potential function-based argument of [GHSZ02, LW20] and the recent tail bound of Jaber, Kumar, and Zuckerman [JKZ25] one can prove a much weaker version of Theorem 1.1 for binary codes only, where the 2−Ω(ηn) term is replaced by a constant larger than 2 (in particular, it only guarantees list size a constant factor larger than the expectation) and the probability bound is also weaker. Generalizing this type of argument to larger fields has eluded researchers for the last 25 years. For future work, it would be interesting to determine to what extent our techniques can be applied to random linear codes below capacity. Optimal Polynomial Intersection (OPI). This problem has recently attracted attention as a possible route to demonstrating quantum advantage [JSW+ 25, CT25, Cha25, KSG+ 25, Ros26, SW26]. In one version of the problem,3 one is given input lists S1 , . . . , Sn ⊆ Fq and a description of a linear code C, and must output a codeword c ∈ C maximizing |{i ∈ [n] : ci ∈ Si }|. Equivalently, one seeks a codeword in an output list for a list-recovery problem (with errors) at the smallest possible decoding radius. The parameter regimes of interest are above capacity: the corresponding list will contain exponentially many codewords. However, the question here is more algorithmic – find some codeword from this (exponentially large) set of possibilities – rather than combinatorial/discrepancy-theoretic, like the questions we study. Random Linear Codes Below Capacity. Finally, while our main goal is to study random linear codes at rates above capacity, we remark that there has been a long line of work studying 3

We state here the version for general linear codes. The original formulation focused on Reed–Solomon codes, hence the word “polynomial,” but the same question is natural for arbitrary linear codes.

random linear codes below capacity (we already mentioned some such works above when discussing potential function-based arguments). Firstly, we consider the task of list-decoding: at rates 1 − 1 n logq |Bρ |−ε, one aims to establish that random linear codes are with high probability (ρ, O(1/ε))list-decodable, which matches the performance of uniformly random codes. It is worth mentioning a classical argument of Zyablov and Pinsker [ZP81] demonstrates they are (ρ, q O(1/ε) )-list-decodable; so the challenge is to show an exponentially smaller list-size is still sufficient. The aforementioned work [GHSZ02] derived the O(1/ε) list-size, but only over the binary alphabet; later works managed to (largely) extend this to arbitrary, constant-sized fields [GHK11, CGV13, Woo13], although often with some parameter restrictions. List-recovery has also seen more attention in recent years, both with errors4 and without. For list-recovery in this setting, there has only been one positive result establishing that random linear codes can be list-recovered with list-size Oq,ℓ (1/ε) [DMRR25] (while to match plain random codes, one would hope for list-size O(ℓ/ε)). However, there have been a number of negative results [GLM+ 21, RY24], in some cases showing that random linear codes provably perform worse than plain random codes. Notably, the restrictions for zero-error list-recovery arise over fields of small characteristic, but disappear over prime fields: similarly, to establish zero-error list-recovery bounds (and hence our application to leakage-resilient secret-sharing), we work over prime fields. When q is large (at least exp(Ω(1/ε))), many recent works [ST23, BGM23, GZ23, AGL24, LMS25] have established that random linear codes (and, even more interestingly, random ReedSolomon codes;5 in this case q ≥ Ω(n)·exp(Ω(1/ε))) of rate R are (1−R−ε, O(1/ε))-list-decodable. L More generally, they can be shown to achieve the generalized Singleton bound, i.e., are ( L+1 (1 − Ω(1/ε) R − ε), L)-list-decodable for any L ≥ 1. For list-recovery over large alphabets (q ≥ ℓ ), recent works have shown matching lower [LS25] and upper [RW14, RW18, BCDZ26] bounds on the listsize required at decoding radius 1 − R − ε: L = ℓO(1/ε) . This is provably worse than plain random codes (where L = O(ℓ/ε) is sufficient); furthermore, we emphasize that this limitation is inherent over every finite field, not just small characteristic fields.

Main Results

This section presents the formal versions of the paper’s main discrepancy results. We begin by fixing notation and conventions, and then state two theorems on the discrepancy of random linear codes: the first controls all translations of a single test function, while the second applies to large families of Fourier-concentrated test functions. We then derive the corresponding applications to list-decoding and list-recovery. The application to leakage-resilient secret-sharing schemes is treated separately in Section 6. 4

Briefly, a code C is (ρ, ℓ, L)-list-recoverable from errors if for any combinatorial rectangle S1 × · · · × Sn with each |Si | ≤ ℓ, we have |{c ∈ C : |{i ∈ [n] : ci ∈ / Si }| ≤ ρn}| ≤ L. That is, we allow a ρ fraction of the coordinates ci to not lie in the input list Si . 5 Reed-Solomon codes are defined by evaluating low-degree univariate polynomials at n distinct field elements; to generate a random Reed-Solomon code, one samples these evaluation points randomly.

2.1

Notation and Conventions

Random Linear Codes Fix a prime power q and integers k, n ∈ N with k ≤ n. In this work, a random linear code (RLC) of designed dimension k and length n over Fq is the image of a uniformly random matrix G ∈ Fn×k . q Equivalently, its designed rate is k/n. We refer to this as the random generating matrix model. Another common model samples C uniformly from the set of all k-dimensional subspaces of n Fq . The two models agree after conditioning on the event that G has full rank, since the image of a full-rank random matrix is a uniformly random k-dimensional subspace. Moreover, the latter −(n−k+1) event holds with probability at least 1 − q 1−1/q . Thus, whenever n − k grows linearly with n, passing between the two models changes the stated probabilities only by a negligible term. This is the regime of the constant-rate applications below. Fourier Transform For functions f : Fnq → C, we use the expectation measure on the primal space and the counting measure on the Fourier side. The Fourier transform of f at y ∈ Fnq is X fb(y) = q −n f (x)χy (x), x∈Fn q

where χy is the additive character of Fnq associated with y. Specifically, if Fq has characteristic p and q = pm , then 2πi χy (x) = exp tr(⟨x, y⟩) , p P where ⟨x, y⟩ = nj=1 xj yj is the standard inner product over Fq . Here tr : Fq → Fp is the absolute field trace, 2 m−1 tr(a) = a + ap + ap + · · · + ap . Under these normalizations, for r ≥ 1 we write  1/r X ∥f ∥r = q −n |f (x)|r  and

1/r

 fb

x∈Fn q

=

|fb(y)|r 

y∈Fn q

We define convolution by (f ∗ g)(y) = q −n

f (x)g(y − x).

x∈Fn q

With these choices, Parseval’s identity takes the form ∥f ∥2 = fb , and convolution satisfies 2

f[ ∗ g = fb · gb. A nonnegative function f : Fnq → R≥0 is normalized if its expectation is 1, i.e., ∥f ∥1 = E [f (x)] = 1. n x∼Fq

We will use the following Fourier pseudorandomness condition. 11

Definition 2.1 (α-Fourier-concentration). A normalized function f : Fnq → R≥0 is α-Fourierconcentrated, for α ∈ [0, 1], if for every y ∈ Fnq , fb(y) ≤ αwt(y) . Relative Deviation In Eq. (2), we defined the relative deviation of a code C with respect to a set B. We now extend this notion from sets to nonnegative normalized functions. This formulation is more convenient when the tests are weighted functions rather than indicators. For a nonempty set B ⊆ Fnq , let qn fB := 1B . |B| Then fB is normalized, and the set-based relative deviation is recovered from the functional definition below. Definition 2.2 (Relative deviation). Let f : Fnq → R≥0 be normalized, and let C ⊆ Fnq be nonempty. Write X f (C) := f (x). x∈C

The relative deviation of C with respect to f is δC,f := E [f (x)] − E [f (x)] = n x∼C

x∼Fq

f (C) − 1. |C|

In particular, for fB = (q n /|B|)1B , δC,fB =

q n |C ∩ B| − 1 = δC,B . |C| |B|

Thus, |δC,fB | ≤ τ is equivalent to (1 − τ )

2.2 2.2.1

|C| |B| |C| |B| ≤ |C ∩ B| ≤ (1 + τ ) . n q qn

Discrepancy Results for Random Linear Codes Small Relative Deviation for Translations of a Single Function

We first state a detailed version of Theorem 1.1. It shows that, for any fixed normalized nonnegative function f , a random linear code of rate slightly above the natural threshold for f has exponentially small relative deviation with respect to every translation of f . For a normalized function f , define its capacity parameter by β :=

1 logq ∥f ∥∞ . n

This choice is motivated in detail in Section 3. For now, observe that if B ⊆ Fnq is nonempty and f = fB = (q n /|B|)1B , then 1 β = 1 − logq |B|. n Moreover, for a code of rate R, the expected intersection of C with a uniformly random translate of B is |C| |B| = q (R−β)n . qn Thus R = β is the point at which this expected intersection size is 1, while rates R = β + η correspond to the above-capacity regime where the expected intersection size is q ηn . Definition 2.3 (Translation). For a function f : Fnq → C and a vector z ∈ Fnq , define the translation fz : Fnq → C by fz (x) = f (x + z). Theorem 2.4 (Small deviation of a translation family). Fix a normalized function f : Fnq → R≥0 , and let β = n1 · logq ∥f ∥∞ . Let F = {fz : z ∈ Fnq } be the family of all translations of f . Let C ⊆ Fnq be a random linear code of rate R = β + η (where η > 0 and k = Rn), and assume η . Then, with probability at least that n is large enough that ηn ≥ 240 logq n. Let ε = 12 ηn

1 − 4q 1− 3 −

2 n2 q k−n+1 2n− η1440 − q (q − 1)2

over the choice of C, we have maxn |δC,fz | ≤ q −εn . z∈Fq

2.2.2

Small Relative Deviation for a Family of Fourier-Concentrated Functions

We next state a detailed version of Theorem 1.2, dealing with general families of Fourier-concentrated functions. Theorem 2.5 (Small deviation of Fourier-concentrated Functions). Fix a family F of normalized and α-Fourier-concentrated functions f : Fnq → R≥0 (where 0 < α < 1), and set β = maxf ∈F n1 · logq ∥f ∥∞ . Let C ⊆ Fnq be a random linear code of rate R = β + η ≤ 1 for some η > 0. Denote ( & !') log2 (q − 1)/(q η/100 − 1) d = max 0, log2 . log2 (1/α) η , 2η and let Fix a parameter t > 20 logq (n) such that 2t/n < 2−d min R − 50 2t η ε = 2−d min R − , 2η − . 50 n Then, for sufficiently large n, with probability at least ηn

1 − n(Rn + 1)q − 100 − |F | · d · q n−t /10 over the choice of C, we have |δC,f | ≤ q −εn for every f ∈ F. 13

The following corollary is a simplified and slightly weaker version of Theorem 2.5. It is intended to make the trade-off between the family size, the success probability, and the resulting deviation bound easier to parse. Corollary 2.6 (Simplified version of Theorem 2.5). For every n ∈ N, prime power q, and 0 < α < 1, the following holds. Let F be a family of normalized and α-Fourier-concentrated functions f : Fnq → R≥0 . Let 1 β := max logq ∥f ∥∞ . f ∈F n Let 0 < η ≤ 50β/51, and let C ⊆ Fnq be a random linear code of rate R = β + η ≤ 1. Set log(1/α) λ := min 1, . 2 log(100q/η) Let 0 < θ < ηλ. Then, assuming n ≥ n0 (q, η, α, θ), it holds with probability at least θ 2 n2

ηn

1 − q − 200 − |F|q n− 20 , that |δC,f | ≤ q −2(ηλ−θ)n for every f ∈ F. In particular, it suffices to take s ( ) c logq (1/η) c q , , logq 2 + log n0 ≥ max η θ η(1 − α) where c > 0 is a sufficiently large universal constant. Remark 2.7 (On the probability–deviation trade-off in Corollary 2.6). The parameter θ controls the trade-off between the success probability and the deviation bound. For a simple way to read the corollary, suppose that logq |F| grows at least linearly in n. If one only wants success probability 1 − o(1), one may take q θ :=

logq |F| n

g(n),

where g(n) → ∞ sufficiently slowly that g(n)

q logq |F| = o(λn).

The resulting deviation bound is √ |δC,f | ≤ q −2(ηλ−θ)n = q −2ηλn+2g(n) logq |F | . κ

In particular, if |F| ≤ q n for some fixed 1 ≤ κ < 2, then the same calculation yields constants γ = γκ,η > 0 for which, in the corresponding parameter regimes, the bound takes the form γ

|δC,f | ≤ q −n , γ

for all sufficiently large n. For example, this applies in regimes such as q ≤ 2n and α ≤ 1 − n−γ , after choosing γ sufficiently small as a function of κ and η. We defer the proof of Corollary 2.6 to Section 4.3.3. 14

2.3

Applications to List-Decoding and List-Recovery

We now record two direct coding-theoretic consequences of Theorems 2.4 and 2.5. The definitions of list-decoding and zero-error list-recovery were given in the introduction; we repeat them here only to fix notation for the formal statements. Definition 2.8 (List-decodable code). A code C ⊆ Fnq is (ρ, L)-list-decodable if, for every z ∈ Fnq , |Bρ (z) ∩ C| ≤ L. Recall that 1 − n1 logq |Bρ | is the list-decoding capacity. Below this rate, uniformly random codes achieve constant list size with high probability; above this rate, the relevant benchmark is the expected intersection size with a Hamming ball. More precisely, a uniformly random code of rate 1 − n1 logq |Bρ | + γ has about |C| · |Bρ | ≈ q γn qn codewords in each Hamming ball with high probability. The next theorem shows that random linear codes satisfy the same above-capacity discrepancy guarantee. Theorem 2.9 (Random linear codes achieve nearly optimal list size in list-decoding above capacity). Let n ∈ N, let q be a prime power, let 0 < ρ < 1 − 1/q, and let 0 < γ < n1 logq |Bρ (0)|, where γn ≥ 240 logq n. Set 1 R := 1 − logq |Bρ (0)| + γ. n Let C ⊆ Fnq be a random linear code of designed rate R. Then, with probability at least 1 − 4q 1−γn/3 −

q −(1−R)n+1 2 2 − q 2n−γ n /1440 , (q − 1)2

the following holds simultaneously for every z ∈ Fnq : |C| · |B (0)| ρ . |Bρ (z) ∩ C| = 1 ± q −γn/12 n q

(3)

In particular, C is (ρ, L)-list-decodable with l m L = 1 + q −γn/12 q γn . Remark 2.10. Observe that the probability bound is 1−o(1) whenever γ 2 n → ∞ and (1−R)n → ∞ Proof. We apply Theorem 2.4 to the normalized indicator of the Hamming ball centered at the origin, qn 1 . f= |Bρ (0)| Bρ (0) Its capacity parameter is βn :=

1 1 logq ∥f ∥∞ = 1 − logq |Bρ (0)|. n n 15

Thus Theorem 2.4 gives maxn |δC,fz | ≤ q −γn/12 z∈Fq

with probability at least γn

1 − 4q 1− 3 −

γ 2 n2 q Rn−n+1 − q 2n− 1440 . 2 (q − 1)

The functions fz are the normalized indicators of the balls Bρ (−z); as z ranges over Fnq , these are exactly all Hamming balls of radius ρn. Translating this relative-deviation bound gives Eq. (3). Finally, |C| ≤ q Rn by construction, so |C| · |Bρ (0)| ≤ q γn . qn This yields the stated list-size bound. We now turn to zero-error list-recovery. Definition 2.11 (List-recoverable code). A code C ⊆ Fnq is (ℓ, L)-list-recoverable if, for every collection of sets S1 , S2 , . . . , Sn ⊆ Fq with |Si | ≤ ℓ for all i ∈ [n], |(S1 × S2 × · · · × Sn ) ∩ C| ≤ L. We call ℓ the input list size and L the output list size. For the upper-bound guarantee, it suffices to consider rectangles S1 × · · · × Sn with |Si | = ℓ for every i, since smaller input lists can be padded to size ℓ. The zero-error list-recovery capacity is 1 − logq ℓ: below this rate uniformly random codes achieve constant output list size, while above this rate the expected intersection with an ℓ-by-· · · -by-ℓ rectangle is exponential. We focus on the nontrivial range 2 ≤ ℓ ≤ q − 1, since ℓ = 1 and ℓ = q give the trivial bounds L = 1 and L = |C|, respectively. Theorem 2.12 (Random linear codes achieve nearly optimal output list size in zero-error list-recovery above capacity). There exist universal constants c, c′ > 0 such that the following holds. Let n ∈ N, let q be prime, and let 2 ≤ ℓ ≤ q − 1. Let 0<γ≤

1 min{logq ℓ, 1 − logq ℓ}, 2

and set R = 1 − logq ℓ + γ. Assume that n ≥ c′ ·

q 5 log2 (q/γ) . γ2

Let C ⊆ Fnq be a random linear code of designed rate R. Then, with probability at least 2

1 − 2q −cγn/(q log(q/γ)) , the following events both hold:

1. the code C is (ℓ, L)-list-recoverable with l m 2 L = 1 + q −cγn/(q log(q/γ)) q γn . 2. For every combinatorial rectangle S = S1 × · · · × Sn with |Si | = ℓ for each i, we have |C|ℓn 2 |C ∩ S| = 1 ± q −cγn/(q log(q/γ)) . qn Proof. Observe that the second event in the statement implies the first one. Indeed, let S = S1 × · · · × Sn be a sequence of sets Si ⊆ Fq , each of size at most ℓ. Then there are sets S1′ , . . . , Sn′ , such that Si ⊆ Si′ and |Si′ | = ℓ for all i. By the second event, |C|ℓn 2 −cγn/(q 2 log(q/γ)) ≤ 1 + q q γn , |S ∩ C| ≤ S ′ ∩ C ≤ 1 + q −cγn/(q log(q/γ)) qn implying the first event. It thus suffices to prove that the second event holds with probability at least 2 1 − 2q −cγn/(q log(q/γ)) . Let F be the family of normalized indicators fS = (q n /|S|)1S over rectangles defined by S1 , . . . , Sn each of size exactly ℓ. Then n q |F| = ≤ 2qn ≤ q qn , ℓ and ∥fS ∥∞ = (q/ℓ)n , so the capacity parameter in Corollary 2.6 is β = 1 − logq ℓ. By Lemma 5.2, every fS ∈ F is α-Fourier-concentrated with α = cos(π/q). Therefore the parameter λ from Corollary 2.6 satisfies c1 log(1/ cos(π/q)) ≥ 2 λ = min 1, 2 log(100q/γ) q log(q/γ) for a universal constant c1 > 0, using Lemma 5.3 to lower bound log(1/ cos(π/q)) ≥ Ω(1/q 2 ). Choose the theorem constant c > 0 so that c ≤ min{c1 /4, 1/200}, and set θ :=

cγ q 2 log(q/γ)

Then θ < γλ, and 2(γλ − θ) ≥

cγ . q 2 log(q/γ)

Also, since γ ≤ 12 (1 − logq ℓ) = β/2, the hypothesis γ ≤ 50β/51 of Corollary 2.6 is satisfied. Taking c′ large enough, the assumed lower bound n ≥ c′

q 5 log2 (q/γ) γ2

implies the lower bound n ≥ n0 (q, γ, α, θ) required in Corollary 2.6. Hence Corollary 2.6, applied with η = γ, gives 2 |δC,fS | ≤ q −cγn/(q log(q/γ)) for every fS ∈ F, except with failure probability at most 2 2

q −γn/200 + |F|q n−θ n /20 . 2

The first term is at most q −cγn/(q log(q/γ)) by the choice of c. For the second, using |F| ≤ q qn and increasing c′ if necessary, the lower bound on n gives θ2 n/20 ≥ q + 1 + θ. Therefore 2 2

2 2

|F|q n−θ n /20 ≤ q qn+n−θ n /20 ≤ q −θn = q −cγn/(q log(q/γ)) . Thus the desired deviation event holds with probability at least 2

1 − 2q −cγn/(q log(q/γ)) . On this event, every rectangle S with side length exactly ℓ satisfies |C|ℓn 2 . |C ∩ S| = 1 ± q −cγn/(q log(q/γ)) qn

Proof Overview

We organize the proof around two motivating examples. We begin with binary list-decoding, where the relevant sets are Hamming balls of a fixed radius. This illustrates Theorem 2.4: all such balls are translates of the ball centered at the origin, so the family consists of the translations of a single normalized indicator function. We then turn to list-recovery over a constant-size alphabet, where the relevant sets are combinatorial rectangles A1 × · · · × An ,

|Ai | = ℓ,

2 ≤ ℓ ≤ q − 1.

This illustrates Theorem 2.5: these rectangle indicators are α-Fourier-concentrated for some α < 1 2 bounded away from 1, and the number of such rectangles is only q o(n ) . Hamming Balls and the Translation-Family Case Let B = B(0, ρn) ⊆ Fn2 be the Hamming ball of radius ρn around the origin, and let fB =

2n · 1B |B|

be its normalized indicator. The Hamming ball around a center z ∈ Fn2 is B + z, whose normalized indicator is the translate (fB )z (x) = fB (x + z). 18

Thus, in the binary list-decoding example, the family we need to control is precisely {(fB )z : z ∈ Fn2 }, the set of all translates of one function. This is the motivating special case of Theorem 2.4. We expose the random code one generator at a time. That is, starting from C0 = {0}, we consider the random sequence C0 ⊆ C1 ⊆ · · · ⊆ Ck ,

Ci = Ci−1 + span{ui },

where the vectors u1 , . . . , uk are chosen independently and uniformly from Fn2 . The final code is C = Ck . The reason for using this incremental construction is that the deviation δ has a simple expected evolution in one step. Suppose C ′ = C + span{u}. Over F2 , this means

C ′ = C ∪ (C + u).

The old coset C contributes the old deviation, while the new coset C + u behaves like a random translate of C. A direct calculation gives 1 E δC ′ ,f = δC,f . 2 u Thus one new generator should ideally divide the deviation by 2. This explains the rate threshold: If β=

1 log2 ∥fB ∥∞ n

then the initial deviation of a translate is at most on the order of 2βn . If k = Rn = (β + η)n and each of the k steps divided the deviation by 2, then the final deviation would be roughly 2βn−k = 2−ηn , which is exponentially small. We formalize this ideal behavior using smoothness. Given a function g and a parameter Γ, we say that the construction sequence is (g, Γ)-smooth if |δCi ,g | ≤ 2k−i Γ

for every 0 ≤ i ≤ k.

This is a two-sided deviation bound. It says that the deviation at time i is no larger than what one would expect if the final deviation were Γ and each preceding step divided the deviation by 2. In the q-ary setting, the corresponding definition uses q k−i Γ in place of 2k−i Γ. An iterative dimension-by-dimension viewpoint also appears in Blinovsky’s covering-radius proof [Bli87] (see also [CHLL97, Theorem 12.3.5]), but the discrepancy problem requires a more precise version of this process. For comparison, in a covering argument with g the normalized indicator of a ball, it is enough to prove the one-sided condition δCi ,g > −1 19

for some i, since this is exactly the statement that the ball contains at least one codeword of Ci . Once this happens, it remains true for every later code Cj ⊇ Ci . In the present problem we instead want |δCk ,g | to be small, meaning that the final code samples the ball with approximately the correct multiplicity. This property is not monotone: even if |δCi ,g | is small at some intermediate stage, later added codewords may oversample the same ball and make the deviation large again. Although the theorem only concerns the final code Ck , our proof method requires the stronger inductive invariant that the deviations are controlled throughout the construction. A first attempt would be to prove smoothness directly for every ball B + z. Indeed, the secondmoment smoothness lemma (see Lemma 4.5) shows that, for a fixed normalized function g and any Γ > 2−k g(0), the failure probability is at most (k + 1)2−k ∥g∥22 + 2k−n . (Γ − 2−k g(0))2 In the overview, it is useful to read this as roughly (k + 1)2−k Γ−2 ∥g∥22 , as long as Γ is not too close to 2−k g(0). Since ∥(fB )z ∥22 ≤ ∥(fB )z ∥∞ = ∥fB ∥∞ = 2βn , this gives exponentially small failure probability for each fixed center z, provided Γ is chosen exponentially small but still larger than 2−k (fB )z (0) with sufficient slack. This direct argument is not enough. There are 2n possible centers, while the second-moment estimate gives only a bound of order 2−cn for some small constant c > 0. The latter is not large enough to support a union bound over all centers. Thus we need a way to upgrade the probability after paying for only one direct second-moment estimate. We apply the direct second-moment estimate only once, to a common auxiliary function, and then use that common event to control all translates with much better conditional probability. In the binary case, the auxiliary function is the ordinary self-convolution Ff = f ∗ f. For the ball function fB , the value FfB (w) is a normalized count of pairs x, y ∈ B

with

x + y = w.

Thus controlling FfB on a code is the smoothed version of controlling (B + B) ∩ C. The reason for introducing Ff is the one-step variance identity 1 Varu δC ′ ,f = δC,Ff , 4 readily proven as part of Lemma 4.12. Thus Ff measures the noise in the update of δC,f . If the construction sequence is smooth for Ff , then the update for f is concentrated around its mean δCi ,f /2 at every step. Consequently, unless the deviation of f is already small, the next step is very likely to reduce it by almost the expected factor 2.

We now bootstrap as follows. First, apply the second-moment bound only to the single function FfB . This is possible because FfB has essentially the same second-moment size as fB : ∥FfB ∥2 = ∥fB ∗ fB ∥2 ≤ ∥fB ∥1 ∥fB ∥2 = ∥fB ∥2 , and hence ∥FfB ∥22 ≤ ∥fB ∥22 ≤ ∥fB ∥∞ = 2βn . Therefore Lemma 4.5 implies that, with probability at least 1 − 2−Ω(n) , the construction sequence is (FfB , Γ)-smooth for a suitable exponentially small Γ = 2−cn . The crucial point is that this smoothness event is common to all balls. For every translate (fB )z , the binary self-convolution appearing in the variance identity is the same: (fB )z ∗ (fB )z = fB ∗ fB . Thus we do not need to prove smoothness separately for the self-convolution of each ball. We condition on the single event that FfB is smooth. After this conditioning, the probability scale improves dramatically. The smoothness-transfer lemma, Lemma 4.14, says that if the sequence is (FfB , Γ)-smooth, then for any fixed translate 2 (fB )z , the conditional probability that (fB )z fails to be smooth is at most 2−Ω(t ) , where t is a slackness parameter. A union bound over all 2n centers gives failure probability at most 2

2n−Ω(t ) . 2

Taking t = Θ(n) makes this probability 2−Ω(n ) . This proves the translation-family theorem in the motivating binary list-decoding case. The statement of Theorem 2.4 is more general: it applies to arbitrary normalized functions and to q-ary alphabets. For q > 2, the only change is that the ordinary self-convolution is replaced by the mirrored self-convolution Ff = f ∗ fˇ, fˇ(x) = f (−x) . Combinatorial Rectangles and the General Family Case We now turn to the setting that motivates Theorem 2.5. Think of zero-error list-recovery over a constant-size alphabet Fq . A typical bad set is a combinatorial rectangle S1 × S2 × · · · × Sn ,

Si ⊆ Fq ,

|Si | = ℓ,

where 2 ≤ ℓ ≤ q − 1. Let fS denote the normalized indicator of such a rectangle. The important facts about these functions are the following. First, they are α-Fourier-concentrated for some constant α < 1 depending only on q and ℓ. Indeed, the Fourier transform factors coordinate by coordinate, and the one-dimensional nontrivial Fourier coefficients are bounded away from 1. Second, there are n q 2 ≤ q o(n ) ℓ 21

such rectangles in the constant-alphabet regime under discussion. More generally, Theorem 2.5 is 2 designed to handle any family of q o(n ) normalized α-Fourier-concentrated functions. The argument for Hamming balls breaks down because the functions in this family are not all translates of a single function. For different rectangles f ∈ F, the mirrored self-convolutions Ff may be different. Thus we cannot apply the direct second-moment estimate to each Ff separately: that estimate gives only q −Ω(n) failure probability for each fixed function, whereas the family size allowed in Theorem 2.5 is much larger than what such a direct union bound can handle. The extra assumption we use is Fourier-concentration. The mirrored self-convolution improves Fourier-concentration: if f is α-Fourier-concentrated, then Ff is α2 -Fourier-concentrated. Iterating this operation, define f (0) = f, f (r+1) = Ff (r) . r

Then f (r) is α2 -Fourier-concentrated. We choose d so that d

1 + (q − 1)α2 ≤ q η/100 . At this depth, the Fourier coefficients of f (d) decay quickly enough that smoothness follows from a mild code-dependent event. The event we need is that the dual codes do not have too many vectors at any Hamming weight. More precisely, for Wj = {y ∈ Fnq : wt(y) = j}, we require |Ci⊥ ∩ Wj | ≤ γq −i |Wj |

for every 0 ≤ i ≤ k and every 1 ≤ j ≤ n,

where γ = q ηn/100 . This event depends only on the construction sequence, not on the function f . It holds with high probability by a standard first-moment argument applied to the sets Wj . Assume this dual weight event holds. If g is normalized and α′ -Fourier-concentrated, then |b g (y)| ≤ (α′ )wt(y) . Using the Fourier identity δCi ,g =

gb(y),

y∈Ci⊥ \{0}

we obtain |δCi ,g | ≤

X y∈Ci⊥ \{0}

|b g (y)| ≤ γq −i

n X

|Wj |(α′ )j ≤ γq −i 1 + (q − 1)α′

j=1

Thus, under the dual weight event, every sufficiently Fourier-concentrated function is smooth. Applying this to g = f (d) gives C0 , . . . , Ck is (f (d) , Γd )-smooth, with

Γd = q −k γ 1 + (q − 1)α2

≤ q −k+ηn/50 .

We then build back from f (d) to the original function f = f (0) . At each step we use the same smoothness-transfer lemma as in the translation-family case. If f (r) = Ff (r−1) 22

is smooth with parameter Γr , then f (r−1) is smooth with parameter n p o Γr−1 = q t max ∥f (r−1) ∥∞ q −k , Γr . 2

except with probability q n−Ω(t ) . The square root is the main quantitative loss. If Γr ≈ q −an , then this step gives Γr−1 ≈ q −an/2 up to the slack factor q t . Thus each reverse step essentially halves the smoothness exponent. After d steps, this accounts for the factor 2−d in the final exponent. Since the starting functions are α-Fourier-concentrated with α < 1 bounded away from 1, the required number of iterations d does not grow with n. The slack factor q t is chosen to make the conditional failure probability small enough. Taking t = Θ(2−d ηn) makes

q n−Ω(t ) = q −Ω(n ) . This is strong enough to union bound over all f ∈ F and over all d levels of the convolution 2 iteration, even when |F| = q o(n ) . Finally, the initial terms in the recurrence are small because R = β + η. For every relevant iterate, ∥f (r) ∥∞ q −k ≤ q −ηn , using the bound ∥f (r) ∥∞ ≤ ∥f ∥∞ ≤ q βn . Unfolding the recurrence for the Γr ’s gives a final smoothness parameter Γ0 ≤ q −εn , where ε = Θ(η2−d ) with the constants made explicit in Theorem 2.5. Hence |δCk ,f | ≤ q −εn for every function in the family. The dual weight event is common to the entire family, and the 2 remaining bootstrapping failures have q −Ω(n ) probability, so the final union bound gives Theorem 2.5.

Random Linear Codes are Smooth—Proof of Theorems 2.4 and 2.5

In this section we prove Theorems 2.4 and 2.5. We begin with several definitions. As explained in Section 3, we view a given RLC as being constructed one dimension at a time, leading us to define a construction sequence. Definition 4.1. A construction sequence is a sequence of codes C0 , . . . , Ck ⊆ Fnq where Ci = Ci−1 + span{ui } for some vector ui ∈ Fnq . When u1 , . . . , uk are chosen uniformly at random, we say that this is a random construction sequence, and each Ci is an RLC of designed dimension i. 23

We would like to talk about a code having small deviation with regard to a specific function not just for the full code but also throughout its construction sequence. This requirement is captured by the notion of smoothness, motivated in Section 3. Definition 4.2. Fix a non-zero function f : Fnq → R≥0 . A construction sequence C0 , . . . , Ck is (f, Γ, j)-smooth (for some real Γ ≥ 0 and integer 0 ≤ j ≤ k) if |δCi ,f | ≤ q k−i · Γ for all 0 ≤ i ≤ j. As a shorthand, we write (f, Γ)-smooth to mean (f, Γ, k)-smooth. Definition 4.3. For 0 ≤ j ≤ n, let Wj = x ∈ Fnq : wt(x) = j , where wt(x) denotes the Hamming weight. Let C0 , . . . , Ck be a construction sequence. We say that this sequence is γ-dual-typical (γ ≥ 1) if Ci⊥ ∩ Wj ≤ γ · q −i · |Wj | for all 0 ≤ i ≤ k and 1 ≤ j ≤ n. In Section 4.1 we begin with a weaker probabilistic argument that shows that RLCs are smooth for any fixed given function, and also dual-typical, with probability q −Ω(n) . In Section 4.2 we introduce the averaged convolution function Ff and relate δCi ,Ff to the i-th step change in δCi+1 ,f . In Section 4.3 we use this relation to control the smoothness of f via that of Ff , and use this implication as the basis to prove Theorems 2.4 and 2.5.

4.1

Smoothness via a Direct Second Moment Argument

In this subsection we use a simple second-moment argument to show that RLCs are smooth and dual-typical, with probability 1 − q −Ω(n) . The core of the argument is the following lemma. Lemma 4.4. Fix n ∈ N and m ≤ n. Let f : Fnq → R≥0 be normalized, and let C be the linear code generated by a uniformly random matrix G ∈ Fn×m . Then, for every ∆ > q −m |f (0) − 1|, q Pr [|δC,f | > ∆] ≤ G

q−1 q m−n 2 ∥f ∥ + . 2 q−1 q m (∆ − q −m |f (0) − 1|)2

Proof. We evaluate the relative deviation by first considering the multiset of all vectors generated by G. Define X X= f (Gv) , v∈Fm q

and let δG,f = q −m X − 1 be the relative deviation over this multiset. m distinct vectors, If G has full column rank, the multiset {Gv : v ∈ Fm q } contains exactly q meaning it coincides perfectly with the code subspace C. In this case, δC,f = δG,f . Therefore, the event that the set deviation exceeds ∆ can only occur if either the multiset deviation exceeds ∆, or G fails to have full rank. By the union bound: Pr [|δC,f | > ∆] ≤ Pr [|δG,f | > ∆] + Pr [rank(G) < m] . G

We Pfirst bound then multiset deviation unconditionally over the choice of G. Since f is normalized, x∈Fnq f (x) = q . For any fixed v ̸= 0, the vector Gv is uniformly distributed over Fnq , so EG [f (Gv)] = 1. The expectation of X is X m E [f (Gv)] = f (0) + q − 1 . E [X] = f (0) + G

v∈Fm q \{0}

Hence, the exact expected multiset deviation is µ = E [δG,f ] = q −m E [X] − 1 = q −m (f (0) − 1) . G

We next bound the variance of X. Since f (0) is a constant, we can expand the variance using the sum definition: X VarG (X) = E [f (Gv)f (Gw)] − E [f (Gv)] E [f (Gw)] . v,w∈Fm q \{0}

If v and w are linearly independent, the vectors Gv and Gw are independent and uniformly distributed in Fnq . Thus, EG [f (Gv)f (Gw)] = EG [f (Gv)] EG [f (Gw)] = 1, making the term exactly zero. The only non-zero terms in the double sum occur when v and w are linearly dependent, meaning w = αv for some α ∈ F∗q . In this case, Gw = αGv. Since f is non-negative, we can form an upper bound by dropping the subtracted product EG [f (Gv)] EG [f (Gw)] = 1: X −n f (x)f (αx) . E [f (Gv)f (αGv)] − 1 ≤ E [f (Gv)f (αGv)] = q G

x∈Fn q

By Cauchy–Schwarz, for every α ∈ F∗q : sX sX X X f (x)f (αx) ≤ f (x)2 f (αx)2 = f (x)2 = q n ∥f ∥22 . x∈Fn q

x∈Fn q

Substituting this back into the variance expansion, we sum only over the pairs (v, αv). There are q m − 1 choices for v ̸= 0 and q − 1 choices for α ∈ F∗q , giving: X X VarG (X) ≤ q −n q n ∥f ∥22 = (q m − 1)(q − 1) ∥f ∥22 ≤ q m (q − 1) ∥f ∥22 . ∗ v∈Fm q \{0} α∈Fq

Scaling down to the relative deviation δG,f , we get VarG (δG,f ) = q −2m VarG (X) ≤

q−1 ∥f ∥22 . qm

By Chebyshev’s inequality, to bound the absolute deviation we measure the distance from the mean µ to the boundary of the interval [−∆, ∆]. Provided ∆ > |µ|, we have: Pr [|δG,f | > ∆] ≤ Pr [|δG,f − µ| > ∆ − |µ|] ≤ G

VarG (δG,f ) (∆ − q −m |f (0) − 1|)2

Substituting our variance bound yields: Pr [|δG,f | > ∆] ≤ G

q−1 q m (∆ − q −m |f (0) − 1|)2

∥f ∥22 .

Finally, we bound the probability that G fails to have full column rank. The matrix G is rankdeficient if and only if at least one of its m columns falls into the span of the previous columns. The i-th column falls into the span of the first i − 1 columns with probability at most q i−1 /q n . Applying the union bound over all m columns gives Pr [rank(G) < m] ≤ G

m X q i−1 i=1

= q −n

qm − 1 q m−n ≤ . q−1 q−1

Adding this rank-deficiency bound to the multiset deviation bound completes the proof. Using Lemma 4.4 across every dimension in the construction sequence and union-bounding the failures, we can show that a random linear code is highly likely to be smooth with respect to f . Lemma 4.5. Let f : Fnq → R≥0 be normalized, and let C0 , . . . , Ck be a random construction sequence. If Γ > q −k |f (0) − 1|, then C0 , . . . , Ck is (f, Γ)-smooth with probability at least 1−

(k + 1)(q − 1)q −k (Γ − q −k |f (0) − 1|)

2 2 ∥f ∥2 −

q k−n+1 . (q − 1)2

Proof. Fix 0 ≤ i ≤ k. Since Ci is an RLC of dimension i, applying Lemma 4.4 with ∆i = q k−i Γ gives q i−n 2 ∥f ∥ + 2 2 q−1 q i (q k−i Γ − q −i |f (0) − 1|) (q − 1)q i q i−n = ∥f ∥22 + 2 q−1 (q k Γ − |f (0) − 1|) q−1

h i Pr |δCi ,f | > q k−i Γ ≤ Ci

≤ =

(q − 1)q k (q k Γ − |f (0) − 1|) (q − 1)q −k

2 2 ∥f ∥2 +

q i−n q−1

q i−n 2 ∥f ∥ + . 2 2 q−1 (Γ − q −k |f (0) − 1|)

A union bound over i = 0, . . . , k gives the bound on the sum of the first terms, and sums the P i−n k−n+1 rank-deficiency error as ki=0 qq−1 ≤ q(q−1)2 . We next show that a random construction sequence is dual-typical with high probability.

Lemma 4.6. A random construction sequence C0 , . . . , Ck is γ-dual-typical with probability at least 1−

n(k + 1) . γ

Proof. Fix 0 ≤ i ≤ k and 1 ≤ j ≤ n, and write Xi,j := |Ci⊥ ∩ Wj |. For every fixed nonzero y ∈ Wj , the event y ∈ Ci⊥ is the event that ⟨y, us ⟩ = 0 for every s ∈ [i]. Since y ̸= 0 and the generators us are independent and uniform in Fnq , this event has probability q −i . Hence E [X]i,j = q −i |Wj |. By Markov’s inequality, 1 Pr Xi,j > γq −i |Wj | ≤ . γ A union bound over the n(k + 1) choices of (i, j) proves the claim. We finish this section by showing that a dual-typical code is smooth on all sufficiently Fourierconcentrated functions. Lemma 4.7. Suppose that the construction sequence C0 , . . . , Ck is γ-dual-typical and that f : Fnq → R≥0 is normalized and α-Fourier-concentrated. Then C0 , . . . , Ck is (f, q −k · γ (1 + (q − 1)α)n )smooth. Proof. Observe that |δCi ,f | ≤

fb(y)

y∈Ci⊥ \{0}

≤

n X

|Ci⊥ ∩ Wj | · αj

j=1

≤

n X

γ · q −i · |Wj | · αj

j=1

=γ·q

−i

=γ·q

−i

n X n j=1

4.2

· (q − 1)j · αj

· ((1 + (q − 1)α)n − 1) .

Self Convolution and Variance of the Relative Deviation

The direct second-moment bound from Section 4.1 yields a failure probability of q −Ω(n) , which is 2 too weak to union-bound over exponentially large function families. To achieve the required q −Ω(n ) probability, we must sharply bound the variance of the relative deviation at each step of the code’s construction. Remarkably, this one-step variance is entirely controlled by the code’s deviation with respect to an auxiliary smoothed function, which we define here as the averaged convolution Ff . Definition 4.8 (Self-Convolution Function Ff ). Let f : Fnq → R≥0 be a function. We define the reflected function fˇ : Fnq → R by fˇ(x) = f (−x). We then define the self-convolution function Ff as

Ff = f ∗ fˇ. Equivalently, Ff can be defined by X

Ff (w) = q −n

f (x) · fˇ(w − x)

x∈Fn q

= q −n

f (x) · f (x − w) .

x∈Fn q

We next prove several simple properties of Ff . Lemma 4.9 (Fourier transform of Ff ). Let f : Fnq → R≥0 be a normalized function. Then, 2

cf (y) = fb(y) F for all y ∈ Fnq . Proof. First, observe that X X X fb̌(y) = q −n f (−x)χy (x) = q −n f (x)χy (−x) = q −n f (x)χy (x) = fb(y) . x∈Fn q

x∈Fn q

Thus, by the Convolution Identity, cf (y) = fb(y) · fb̌(y) = fb(y) · fb(y) = fb(y) F

Lemma 4.9 immediately yields the following corollary. Lemma 4.10 (α-Fourier-concentration of Ff ). Let f : Fnq → R≥0 be a normalized function. If f is α-Fourier-concentrated, then its self-convolution function Ff is α2 -Fourier-concentrated. Lemma 4.11 (Translation Invariance of Ff ). For any function f : Fnq → R and any translation vector z ∈ Fnq , let fz be its translation. Then Ffz = Ff . Proof. We prove this directly using the expanded definition of the self-convolution. Evaluating Ffz at any point w ∈ Fnq yields: Ffz (w) = q −n

fz (x) · fz (x − w) = q −n

x∈Fn q

f (x + z) · f (x − w + z) .

x∈Fn q

Let us apply the change of variables y = x + z. As x iterates over all of Fnq , y also iterates over all of Fnq . Substituting y into the summation gives: Ffz (w) = q −n

f (y) · f (y − w) = Ff (w) .

y∈Fn q

Since Ffz (w) = Ff (w) for all w, we have Ffz = Ff . 28

The following lemma describes how δC,Ff controls the single-step change in δC,f . Lemma 4.12 (Deviation of Ff controls the change in deviation of f ). Let f : Fnq → R≥0 be normalized. Fix a linear code C ⊆ Fnq and assume δC,f ̸= 0. Let u ∼ Fnq be a uniformly random vector, and let C ′ = C + span(u). Then, for any λ > 0: Pr u

δC ′ ,f > |δC,f |

1 +λ q

≤

q−1 q

δC,Ff

2 λ2 · δC,f

Proof. For any normalized function f : Fnq → R (meaning fb(0) = ∥f ∥1 = 1), we can P express its relative deviation over C using the Fourier transform. Utilizing the property that x∈C χy (x) = |C| · 1[y∈C ⊥ ] , we have: δC,f =

X 1 X f (x) − 1 = fb(y) − 1 = |C| ⊥ x∈C

y∈C

fb(y) ,

(4)

y∈C ⊥ \{0}

where the second equality is due to the Convolution Identity. For the augmented code C ′ = C + span(u), its dual space is (C ′ )⊥ = {y ∈ C ⊥ | ⟨y, u⟩ = 0}. Let ξy (u) be the indicator random variable 1[⟨y,u⟩=0] . Thus, for any vector u ∈ Fnq , the deviation over the augmented code becomes: X δC ′ ,f = fb(y) · ξy (u) . y∈C ⊥ \{0}

Since u is chosen uniformly at random, for any non-zero y ∈ Fnq , the inner product ⟨y, u⟩ is uniformly distributed over Fq . Therefore, Eu [ξy (u)] = 1/q. By linearity of expectation, 1 E δC ′ ,f = q u

X y∈C ⊥ \{0}

δC,f . fb(y) = q

Next, we bound the variance of δC ′ ,f . We evaluate X ′ Varu δC ′ ,f = fb(y) · fb(y ) E ξy (u)ξy′ (u) − E [ξy (u)] E ξy′ (u) . u

y,y ′ ∈C ⊥ \{0}

Observe that for linearly independent y and y ′ , −2 −2 E ξy (u)ξy′ (u) − E [ξy (u)] E ξy′ (u) = q − q = 0 , u

so these terms vanish from the sum. For y and y ′ colinear, we have q−1 −1 −2 . E ξy (u)ξy′ (u) − E [ξy (u)] E ξy′ (u) = q − q = q2 u u u

Thus, q−1 Varu δC ′ ,f = q2 ≤

q−1 q2

q−1 ≤ 2q 2

fb(y) · fb(cy)

y∈C ⊥ \{0} c∈F∗q

fb(y) · fb(cy)

(triangle inequality)

y∈C ⊥ \{0} c∈F∗q

(AM-GM inequality)

fb(y) + fb(cy)

y∈C ⊥ \{0} c∈F∗q





q−1 (q − 1) 2q 2

fb(y) + (q − 1)

fb(y ′ )  (taking y ′ = cy)

y ′ ∈C ⊥ \{0}

y∈C ⊥ \{0}

q−1 · 2(q − 1) fb(y) 2q 2 y∈C ⊥ \{0} 2 X 2 q−1 = fb(y) q y∈C ⊥ \{0} 2 X q−1 cf (y) F = q y∈C ⊥ \{0} 2 q−1 = δC,Ff . q =

(by Lemma 4.9)

(by Eq. (4))

Therefore, by Chebyshev’s inequality, 1 Pr |δC ′ ,f | > |δC,f | +λ ≤ Pr δC ′ ,f − E δC ′ ,f > λ|δC,f | u u q u 2 q−1 δC,Ff Varu δC ′ ,f q ≤ . ≤ 2 2 λ2 δC,f λ2 δC,f

4.3

Controlling the Deviation throughout the Construction Sequence

To extend our one-step variance bound across the entire k-step construction, we must carefully track the deviation’s trajectory. The following lemma achieves this by categorizing each step as: • Horrible—steps in which the deviation grows. • Good—steps in which the deviation goes down significantly, or is already as small as expected to begin with. • Bad—steps in which the deviation does not increase, but also does not drop significantly even though it is expected to.

The lemma demonstrates that a breakdown in f ’s smoothness requires an accumulation of too many “bad” steps or at least one “horrible” step. We bound the probability of the first sort of failure, namely, we essentially show that a failure due to t bad steps occurs with probability at 2 most q −Ω(t ) . Later, in Lemma 4.14, we take care of the other failure condition. Lemma 4.13. Let f : Fnq → R≥0 be normalized, let C0 , . . . , Ck be a random construction sequence, let Γ > 0, and let t ∈ N satisfy 20 logq (n) ≤ t ≤ k. Set √ Λ := max{∥f ∥∞ · q −k , Γ}. • Let SF -smooth (f ) denote the event that C0 , . . . , Ck is (Ff , Γ)-smooth. • Let Smonotone (f) denote the event that |δCj ,f | ≤ |δCj−1 ,f | for all j such that (C0 , . . . , Cj−1 ) is f, q t · Λ, j − 1 -smooth. • Let Ssmooth (f ) denote the event that C0 , . . . , Ck is f, q t · Λ -smooth. Then Pr

C0 ,...,Ck

[SF -smooth (f ) and Smonotone (f ) and not Ssmooth (f )] ≤ q − 10 t .

(5)

Proof of Lemma 4.13. The event Ssmooth (f ) holds if and only if |δCi ,f | ≤ q k−i+t ·Λ for all 0 ≤ i ≤ k. Suppose that Smonotone (f ) holds but Ssmooth (f ) fails. Let 0 ≤ ℓ ≤ k be the minimum index for which C0 , . . . , Ck is not (f, q t Λ, ℓ)-smooth In particular, q k−ℓ+t Λ < |δCℓ ,f | .

(6)

i−t/2

1 q +λ

;

3. The i-th step is bad if it is not horrible, |δCi−1 ,f | > q k Λ( 1q + λ)i−t/2 , and |δCi ,f | > |δCi−1 ,f |( 1q + λ). In other words, the i-th step is bad if it is neither horrible nor good. First, note that if the event Smonotone (f ) holds then no horrible steps may occur up to and including the ℓ-th step. Now, for 0 ≤ i ≤ ℓ let gi denote the number of good steps from among the steps {1, . . . , i}. We claim that if no step is horrible then gi −t/2 1 |δCi ,f | ≤ q k Λ +λ . (7) q We prove this by induction on i. This is clearly true for i = 0, since δC0 ,f ≤ q k Λ. Now, suppose Eq. (7) holds for i. We will show that it also holds for i + 1. If the (i + 1)-st step is bad then gi+1 = gi , and so in this case gi −t/2 gi+1 −t/2 1 1 k k |δCi+1 ,f | ≤ |δCi ,f | ≤ q Λ +λ =q Λ +λ . q q On the other hand, if the (i + 1)-st step is good then gi+1 = gi + 1 ≤ i + 1. We now consider two cases. 31

• If this step is good because k

|δCi+1 ,f | ≤ |δCi ,f | ≤ q Λ

1 +λ q

i+1−t/2 ,

|δCi+1 ,f | ≤ q Λ

1 +λ q

gi −t/2+1

=q Λ

1 +λ q

gi+1 −t/2 ,

since gi+1 = gi + 1. In both cases we get the desired upper bound on |δCi+1 ,f |, proving Eq. (7). We turn to show that the event combination Smonotone (f) and ¬Ssmooth (f ) implies an upper t . Since q ≥ 2, we strictly have c > 0. bound on the number of good steps gℓ . Let c = 1−logq 1 + 4k 1 We can rewrite our step multiplier exactly as q + λ = q −c . By Eq. (7), |δCℓ ,f | ≤ q k Λq −c(gℓ −t/2) . Therefore: q k−ℓ+t Λ < |δCℓ ,f | ≤ q k−c(gℓ −t/2) Λ , where the left-hand inequality is due to Eq. (6). Comparing exponents yields: c(gℓ − t/2) < ℓ − t =⇒ gℓ <

ℓ−t t + . c 2

Let bℓ be the number of bad steps up to step ℓ, so gℓ = ℓ − bℓ . Combining these inequalities and isolating bℓ : t 1 1 1 ℓ−t + =⇒ bℓ > ℓ 1 − +t − . ℓ − bℓ < c 2 c c 2 Since c < 1, the term (1 − 1c ) is negative. To find the minimum required bad steps τ , we minimize the right-hand side by setting ℓ = k. We explicitly set: 1 1 1 τ = max 0, k 1 − +t − . c c 2 We have shown that the conjunction of events Smonotone (f ) ∧ ¬Ssmooth (f ) implies that there exists some failure step ℓ ∈ [τ, k] such that bℓ > τ , and crucially, the sequence is monotone up to step ℓ − 1. For 0 ≤ i ≤ k, let Ti denote the event that |δCj ,Ff | ≤ q k−j · Γ for all 1 ≤ j ≤ i. Note that the event SF -smooth (f ) directly implies Tk . For an increasing sequence 1 ≤ i1 < i2 < · · · < iτ ≤ k, let Wi1 ,...,iτ denote the event that the steps i1 , . . . , iτ are bad and the sequence is monotone up to step iτ − 1. Therefore, the left-hand side of Eq. (5) is bounded from above by the union over all such failing sequences: " # [ Pr SF -smooth (f ) and Wi1 ,...,iτ . C0 ,...,Ck

i1 <···<iτ

We bound this by summing over all sequences of τ bad steps: # " X [ Pr[Wi1 ,...,iτ ∩ Tk ] SF -smooth (f ) and Wi1 ,...,iτ ≤ Pr C0 ,...,Ck

τ X Y i1 ,...,iτ r=1

≤

i1 ,...,iτ

i1 <···<iτ

Pr[Wi1 ,...,ir ∩ Tir | Wi1 ,...,ir−1 ∩ Tir−1 ](conditioning fixes Cir −1 , leaving only uir as random)

uir

τ X Y i1 ,...,iτ r=1

Pr[Wi1 ,...,ir | Wi1 ,...,ir−1 ∩ Tir−1 ] .

(8)

uir

To bound the probability Pruir [Wi1 ,...,ir | Wi1 ,...,ir−1 ∩ Tir−1 ], fix a code Cir −1 for which the conditioning holds. If δCir −1 ,f = 0 then the ir -th step cannot be bad, so the probability of Wi1 ,...,ir under the conditioning is 0. Suppose now that δCir −1 ,f ̸= 0. Then, Lemma 4.12 yields Pr [step ir is bad | Cir −1 ] ≤

q−1 q

|δCir −1 ,Ff |

2 λ2 · δ C i −1 ,f

uir

k−(ir −1) Γ = q k−ir +1 Γ on the numerator. Since The event n Tir −1 yields oan upper bound of q √ Λ = max ∥f ∥∞ · q −k , Γ and ∥f ∥∞ ≥ |δC0 ,f |, we have Γ ≤ Λ2 , so the numerator is at most

Squaring this lower bound, the denominator is strictly greater than λ2 q 2k−2ir +t Λ2 . Therefore, Pr[Wi1 ,...,ir | Wi1 ,...,ir−1 ∩ Tir−1 ] ≤

uir

2 q−1 · q k−ir +1 Λ2 q λ2 · q 2k−2ir +t Λ2

1 −k+ir +1−t q λ2 q ≤ 2 q −t (since ir ≤ k) . λ

≤

Returning to Eq. (8), we substitute this uniform bound for all τ bad steps. Recalling our exact

t : substitution λ = 4qk

C0 ,...,Ck

[SF -smooth (f ) and Smonotone (f ) and not Ssmooth (f )] ≤

Pr[Wi1 ,...,iτ ∩ Tk ]

i1 ,...,iτ

≤

τ X Y 16q 3 k 2 i1 ,...,iτ r=1

−t

τ k 16q 3 k 2 −t ≤ q . τ t2 k τ

We bound the binomial coefficient using the standard inequality into our probability bound isolates the exponent:

≤ k τ . Substituting this

16q 3 k 2 −t Pr [SF -smooth (f ) and Smonotone (f ) and not Ssmooth (f )] ≤ k q C0 ,...,Ck t2 τ 16q 3 k 3 −t q = t2 τ

3 3 −τ t−logq 16q 2 k t

Now we bound τ . Since q ≥ 2, we have ln q ≥ ln 2 ≈ 0.693. Using the standard bound t t logq (1 + x) ≤ lnxq , let L = logq 1 + 4k . We have L ≤ 4k tln q ≤ 2.77k . For valid fractional parameters where t ≤ k, we have L ≤ 0.36 < 1, ensuring c = 1 − L > 0. Substitute c = 1 − L into the required steps condition: 1 1 1 −L 1 1 τ ≥ 1− +t − =k +t − 1−L 1−L 2 1−L 1−L 2 1 t(1 − L) = −kL + t − 1−L 2 1 t t tL ≥ − + + 1−L 4 ln q 2 2 1 1 ≥t − ≥ 0.13t . 2 4 ln 2 Therefore, τ ≥ ⌊0.13t⌋ ≥ 0.1t for sufficiently large t. Substituting this simplified lower bound into our probability inequality yields the final dependence: Pr

C0 ,...,Ck

[SF -smooth (f ) and Smonotone (f ) and not Ssmooth (f )] ≤ q

3 3 −0.13t t−logq 16q 2 k t

≤ q −0.1t = q −Ω(t ) . which completes the proof. We now show that smoothness of Ff implies smoothness for f with very high probability. In Lemma 4.7 we showed this implication “modulo” the possibility of failure due to horrible steps. 34

Below we deal with this obstacle: we show that if f fails to be smooth then there exists some translation fz that fails to be smooth but also avoids horrible steps. The claim then follows from Lemma 4.13 via a union bound on all translations of f . Lemma 4.14. In the setting of Lemma 4.13, Pr

C0 ,...,Ck

[SF -smooth (f ) and not Ssmooth (f )] ≤ q n · q −0.1t .

Proof. We first prove the following implication: If not Ssmooth (f )

then ∃z ∈ Fnq Smonotone (fz ) and not Ssmooth (fz ) .

(9)

Assume Ssmooth (f ) fails at a first time 0 ≤ j ≤ k, meaning δCj ,f > q k−j+t Λ, where Λ = n √ o max ∥f ∥∞ q −k , Γ . We construct a sequence of vectors zj , . . . , z0 backward, starting with zj = 0. For 0 ≤ i < j, after choosing zi+1 , we choose zi = zi+1 + γi ui+1 with γi ∈ Fq maximizing δCi ,fzi+1 +γui+1 . Since Ci+1 = Ci + span{ui+1 }, we can express the deviation over the larger code as an average over the q cosets: 1 X δCi ,fzi+1 +γui+1 . δCi+1 ,fzi+1 = q γ∈Fq

Because the absolute value of an average is bounded by its maximum component, our choice of γi implies: δCi ,fzi ≥ δCi+1 ,fzi+1 . Next, setting z = z0 , we replace the moving translations fzi with the single fixed translate fz . For every 0 ≤ i ≤ j, we have z − zi ∈ Ci by construction. Hence, translating by z − zi preserves the subspace Ci , and therefore: δCi ,fz = δCi ,fzi . Together with the previous bound, this yields: |δCi ,fz | ≤ δCi−1 ,fz for all 1 ≤ i ≤ j. Since Ssmooth (fz ) already fails at time j, the definition of Smonotone (fz ) imposes no conditions after the first failure time, so the required monotonicity is fully satisfied. Furthermore, this fixed translation inherits the original failure at time j. Since zj = 0, it follows that z − zj = z ∈ Cj . Thus: δCj ,fz = δCj ,f > q k−j+t Λ =⇒ ¬Ssmooth (fz ) , where we use the fact that ∥fz ∥∞ = ∥f ∥∞ , ensuring the threshold Λ remains identical.

This establishes Eq. (9). The lemma then follows by applying a union bound: [SF -smooth (f ) and not Ssmooth (f )] ≤ Pr ∃z ∈ Fnq SF -smooth (fz ) and Smonotone (fz ) and not Ssmooth (fz ) C0 ,...,Ck X Pr [SF -smooth (fz ) and Smonotone (fz ) and not Ssmooth (fz )] ≤ Pr

C0 ,...,Ck

z∈Fn q

C0 ,...,Ck 2

≤ q n · q −0.1t . The first inequality uses Eq. (9) and the fact that Ff = Ffz implies SF -smooth (f ) = SF -smooth (fz ). The final bound follows directly from Lemma 4.13. 4.3.1

Proof of Theorem 2.4

We now prove Theorem 2.4, which controls the deviation for all translations of a single function f . The core insight is that every translation fz shares the exact same averaged convolution Ff . By securing a global smoothness bound for this single shared Ff , we use Lemma 4.14 to bound the 2 probability to q −Ω(n ) , then using union bound over all q n translations. Proof of Theorem 2.4. Let c = η3 . Let Γ = q −cn . Let SF -smooth (f ) be the event that the construction sequence C0 , . . . , Ck is (Ff , Γ)-smooth. This requires δCi ,Ff ≤ q k−i Γ for all 0 ≤ i ≤ k. The lower bound δCi ,Ff ≥ −q k−i Γ holds deterministically since δCi ,Ff =

Ff (C) cf (C ⊥ ) − 1 = −1=F |C|

cf (y) ≥ 0 . F

y∈C ⊥ \{0}

cf (0) = 1, Here, the second transition is Parseval’s identity, the third is since Ff is normalized so F cf (y) ≥ 0 for all y. and the inequality is because Lemma 4.9 implies F k−i Applying Lemma 4.4 to Ci with ∆ = q Γ yields: h i Pr δCi ,Ff > q k−i Γ ≤

4(q − 1)q βn q i−n q i−n ≤ + ∥Ff ∥22 + 2 2k−i 2 i q−1 q−1 q Γ

q−1

q i (q k−i Γ − |Ff (0) − 1|/q )

where the second inequality comes from q k−i Γ = q βn−i+2ηn/3 tightly dominating the subtraction, |Ff (0) − 1|/q i ≤ q βn−i , and substituting ∥Ff ∥22 ≤ q βn . Then we use union bound for SF -smooth (f ): Pr [¬SF -smooth (f )] ≤

k X 4(q − 1)q βn i=0 4q βn+1

q 2k−i Γ2

q i−n q−1

q k−n+1 (q − 1)2 q k Γ2 q k−n+1 = 4q · q −ηn/3 + . (q − 1)2

≤

We turn to bound Pr [Ssmooth (fz )]. Let t = θn for θ = η/12. By the hypothesis ηn ≥ 240 logq n, we have t = ηn/12 ≥ 20 logq n, and t = ηn/12 ≤ Rn = k since η < R. Hence the condition 36

20 logq (n) ≤ t ≤ k required by Lemmas 4.13 and 4.14 is satisfied. For each z ∈ Fnq , define Ssmooth (fz ) as the event that the sequence is (fz , Γ′ )-smooth, where n √ o Γ′ = q t max ∥f ∥∞ q −k , Γ . Because Ffz = Ff , the event SF -smooth (fz ) is equivalent to SF -smooth (f ). By Lemma 4.14, 2

Pr [SF -smooth (f ) ∩ ¬Ssmooth (fz )] ≤ q n−0.1t . We can bound the probability that any translation fails to be smooth by conditioning on the global smoothness of Ff : Pr ∃z ∈ Fnq ¬Ssmooth (fz ) ≤ Pr ∃z ∈ Fnq ¬Ssmooth (fz ) ∩ SF -smooth (f ) + Pr [¬SF -smooth (f )] X Pr [¬Ssmooth (fz ) ∩ SF -smooth (f )] + Pr [¬SF -smooth (f )] ≤ z∈Fn q 2

≤ q n · q n−0.1t + 4q · q −ηn/3 + η 2 n2

≤ q 2n− 1440 + 4q · q −ηn/3 +

q k−n+1 (q − 1)2

q k−n+1 . (q − 1)2

To calculate Γ′ . Since ∥f ∥∞ = q βn , yielding ∥f ∥∞ q −k = q βn−Rn = q −ηn . We then √ conclude, −ηn/6 get Γ = q . Substituting these bounds: n o Γ′ ≤ q θn max q −ηn , q −ηn/6 ηn

ηn

= q 12 · q − 6 ηn

= q − 12 . By setting ε = η/12 > 0, we achieve maxz∈Fnq |δCk ,fz | ≤ q −εn , which completes the proof.

4.3.2

Proof of Theorem 2.5

We are now ready to prove Theorem 2.5. The proof analyzes a sequence of functions f (0) , . . . , f (d) generated by repeated averaged convolution, starting with f (0) = f . Because each convolution squares the concentration parameter, the top iterate f (d) is highly Fourier-concentrated, allowing its smoothness to be bounded by the code’s dual-typicality. We then work backward, inductively applying Lemma 4.14 to transfer this smoothness step-by-step from f (m) down to the base function f (0) . Proof of Theorem 2.5. Let Stypical denote the event that C0 , . . . , Ck is γ-dual-typical where γ = ηn q 100 and k = Rn. By Lemma 4.6, Pr [Stypical ] ≥ 1 −

ηn n(k + 1) = 1 − n(Rn + 1)q − 100 . γ

η log((q−1)/(q η/100 −1)) d , so that 1 + (q − 1)α2 ≤ q 100 . Choose d = max 0, log2 log(1/α) Fix f ∈ F. We claim that 2 Pr Stypical and |δC,f | > q −εn ≤ d · q n−0.1t .

(10)

Observe that Eq. (10) implies the theorem since Pr ∃f ∈ F | |δC,f | > q −εn ≤ Pr [not Stypical ] + Pr Stypical and ∃f ∈ F |δC,f | > q −εn X ≤ Pr [not Stypical ] + Pr Stypical and |δC,f | > q −εn f ∈F

≤ n(Rn + 1)q

ηn − 100

+ |F| · d · q n−0.1t

We turn to proving Eq. (10). Define the sequence f (0) := f , and f (m) := Ff (m−1) for m ≥ 1. m Applying Lemma 4.10 we get that f (m) is α2 -Fourier-concentrated. Assuming Stypical , Lemma 4.7 implies C0 , . . . , Ck is (f (d) , Γd )-smooth, with: ηn ηn ηn d n Γd = q −k · γ · 1 + (q − 1)α2 ≤ q −k+ 100 + 100 = q −k+ 50 . Define the sequence Γd . . . Γ0 where for all 1 ≤ m ≤ d: n p o Γm−1 = q t max ∥f (m−1) ∥∞ q −k , Γm .

(11)

Define the event Tsmooth (f, i) as C0 . . . Ck being (f (i) , Γi )-smooth. Let Tsmooth (f ) be the event that Tsmooth (f, i) holds for all 0 ≤ i ≤ d. Applying Lemma 4.14 to f (m−1) with Γ = Γm yields 2

Pr [Tsmooth (f, m) ∩ ¬Tsmooth (f, m − 1)] ≤ q n−0.1t . Therefore, Pr [Stypical and |δC,f | > Γ0 ] ≤ Pr [Stypical and not Tsmooth (f, 0)] . Suppose that the event on the right-hand side holds, and let 0 ≤ m ≤ d be the maximum index for which Tsmooth (f, i) does not hold. Recall that m ̸= d since Stypical implies Tsmooth (f, d). Thus, Pr [Stypical and not Tsmooth (f, 0)] ≤ Pr [∃ 0 ≤ m ≤ d − 1 Tsmooth (f, m + 1) and not Tsmooth (f, m)] ≤

≤

d−1 X m=0 d X

Pr [Tsmooth (f, m + 1) and not Tsmooth (f, m)] 2

q n−0.1t

m=1 2

= d · q n−0.1t . Now, we bound the error term Γ0 . By definition, Ck is (f (0) , Γ0 )-smooth. Setting i = k, we obtain: |δCk ,f | ≤ q k−k · Γ0 = Γ0 . 38

Unfolding the recurrent definition Eq. (11) and setting Aj = f (j) ∞ · q −k : n o 1/2 Γ0 = q t max A0 , Γ1 n o1/2 1/2 t t = q max A0 , q max A1 , Γ2 .. . −d f (j) ≤ q · max Γ2d , max 2t

0≤j≤d−1

∞

−k

2−j

(12)

We bound the first term of the maximum on the right-hand side of Eq. (12). Recall that ηn Γd ≤ q −Rn+ 50 . Thus, −d ηn 2 −d q 2t · Γd2 ≤ q 2t · q −Rn+ 50 =q

−d −n R2−d − η250 − 2t n

(13)

We turn to bound the other terms in the right-hand side of Eq. (12). We bound the L∞ norm of f (j) . Recall that f (j) = Ff (j−1) = f (j−1) ∗ fˇ(j−1) , and so f (j)

∞

= f (j−1) ∗ fˇ(j−1) ∞ X −n (j−1) = max q f (x)fˇ(j−1) (w − x) w

x∈Fn q

= max q −n w

f (j−1) (x)f (j−1) (x − w)

x∈Fn q

≤ max q −n f (j−1) w

= q −n f (j−1) = f

(j−1) ∞

∞

X ∞

f (j−1) (x)

x∈Fn q

q n f (j−1)

Then we get a bound on all f (j) ∞ : f (j)

∞

≤ f (j−1)

∞

≤ · · · ≤ f (0)

∞

= ∥f ∥∞ .

Therefore, for all j ≥ 0, we have f (j) ∞ ≤ ∥f ∥∞ = q βn . Substituting this into our maximum yields: f (j) q −k ≤ q βn q −Rn = q (β−R)n = q −ηn . ∞

Substituting this bound back into Eq. (12): 2−j 2t (j) −k q · max f q ≤ q 2t · max 0≤j≤d−1

∞

0≤j≤d−1

q −ηn

2−j

−(d−1)

= q 2t · q −ηn2 −d+1 − 2t n) . = q −n(η2 39

(14)

−d

Set ε1 := R2−d − η250 and ε2 := η2−d+1 . Finally, letting ε = min(ε1 , ε2 ) − 2t n , and noting by our assumption on t that ε > 0, we have by Eqs. (12) to (14): n o 2t 2t Γ0 ≤ max q −n(ε1 − n ) , q −n(ε2 − n ) ≤ q −εn . Therefore, assuming Stypical , the event Tsmooth (f, 0) guarantees |δCk ,f | ≤ q −εn . Because Tsmooth (f, 0) 2 fails with probability at most d · q n−0.1t , we have established Eq. (10), which completes the proof. 4.3.3

Proof of Corollary 2.6

Finally, we use Theorem 2.5 to prove the simplified version given in Corollary 2.6. Proof of Corollary 2.6. Let d be the auxiliary integer from Theorem 2.5, and set ρ∗ := 2−d . We first show that ρ∗ ≥ λ. Write q−1 B := log(1/α) and L := log . q η/100 − 1 We claim that

B ρ∗ ≥ min 1, 2L

Indeed, if L ≤ B, then d = 0 and ρ∗ = 1. Otherwise, d = ⌈log2 (L/B)⌉, so 2d ≤ 2L/B, and hence ρ∗ = 2−d ≥ B/(2L). Since η log q q η/100 − 1 = eη log q/100 − 1 ≥ , 100 we have 100(q − 1) q−1 100q ≤ ≤ . η/100 η log q η q −1 Thus L ≤ log(100q/η), and therefore

log(1/α) ρ∗ ≥ min 1, 2 log(100q/η)

= λ.

Apply Theorem 2.5 with t = θn. Since η ≤ 50β/51, we have β ≥ 51η/50, and hence 49 η −d = ρ∗ β + η ≥ 2ηρ∗ . 2 R− 50 50 Therefore,

n o η 2−d min R − , 2η = 2ηρ∗ . 50 Since θ < ηλ ≤ ηρ∗ , the condition on t in Theorem 2.5 is satisfied. The theorem gives ε = 2ηρ∗ − 2θ, so for every f ∈ F, |δC,f | ≤ q −2(ηρ∗ −θ)n ≤ q −2(ηλ−θ)n . 40

It remains to simplify the failure probability. By Theorem 2.5, this probability is at most 2 2

n(Rn + 1)q −ηn/100 + |F|dq n−θ n /10 . Since R ≤ 1 and η ≤ 50/51, the first term is at most q −ηn/200 whenever n ≥ cη −1 logq (1/η), after increasing the universal constant c. For the second term, the definition of d, together with q η/100 − 1 ≥ η log q/100 and log(1/α) ≥ 1 − α, gives d ≤ c′ log(q/(η(1 − α))) for a universal constant c′ > 0. Thus the second lower bound on n in the statement implies 2 2 2 2 logq d ≤ θ2 n2 /20, again after increasing c, and hence dq n−θ n /10 ≤ q n−θ n /20 . Therefore the failure probability is at most 2 2 q −ηn/200 + |F|q n−θ n /20 , as claimed.

α-Concentration of Combinatorial Rectangles

In this section, we show α-Fourier-concentration for normalized indicator functions of combinatorial rectangles, which are the subsets relevant to zero-error list-recovery, or list-recovery from erasures. In full generality, we fix subsets S1 , . . . , Sn ⊆ Fq , and put ℓi := |Si | for all i ∈ [n]. This argument will only apply to the special case that q = p, a prime integer. Some such restriction is necessary: for example, if q = 2t , if each Si is an F2 -subspace of Fq , then it is not hard to see that any such α-Fourier-concentration is not possible.6 The main tool which we will use is the following bound on sums over subsets of p-th roots of unity, proved by Benhamouda et al [BDIR21, Lemma 3.11]. Below, ωp = e2πi/p denotes a primitive p-th root of unity. Lemma 5.1 (Bound on subset sums). Let S ⊆ Fp be a subset of size ℓ. Then 1X x sin(πℓ/p) ωp ≤ . ℓ ℓ sin(π/p) x∈S

In fact, the proof establishes that the sum is maximized if the sum is over “consecutive” p-roots Pℓ−1 j+i of unity, i.e., it is of the form for some i ∈ {0, 1, . . . , p − 1}. This is predictable, upon j=0 ωp visualizing the p-th roots of unity as lying on the radius one disk in the complex plane: to maximize the magnitude of the sum, all the p-th roots of unity should “as much as possible” point in the same direction. Additionally we remark that there is no need for p to be prime: the same result would hold for any m-th root of unity and any subset of Zm . We can now easily prove the requisite α-Fourier-concentration. 6

One could, for example, weaken the requirement to being that char(q) > maxi ℓi ; however, we do not pursue that here.

Lemma 5.2 (α-Fourier-concentration of rectangles). Let p be a prime, n ∈ N, and let S1 , . . . , Sn ⊆ n Fp be subsets, of size ℓ1 , . . . , ℓn , respectively. Let f = ℓ1p···ℓn 1S1 ×···×Sn denote the normalized indicator for the combinatorial rectangle S1 × · · · × Sn . Then, f is α-Fourier-concentrated for sin(πℓi /p) α := max . ℓi sin(π/p) i∈[n] If 2 ≤ ℓi ≤ p − 1 for all i ∈ [n], then α ≤ cos(π/p) < 1. Proof. Let ξ ∈ Fnp be given, and let T = supp(ξ) = {i ∈ [n] : ξi ̸= 0}. We need to prove |fb(ξ)| =

h i −⟨X,ξ⟩ f (X) ω ≤ α|T | . En p

X∼Fp

Firstly, as f is normalized we have h i −⟨X,ξ⟩ = E f (X) ωp X∼Fn p

X∼S1 ×···×Sn

h i ωp−⟨X,ξ⟩ .

(15)

As S1 × · · · × Sn is a product set, the coordinates X1 , . . . , Xn of X are independent, so (15) =

n Y i=1

i h Xi ·ξi . ω E p

(16)

Xi ∼Si

Now, for each i ∈ [n] with ξi = 0 the expectation is clearly 1. Hence:    i Y 1 X h Y Y 1 X ·ξ   (16) = ωp−xi ·ξi  = E ωp i i = ℓi ℓi Xi ∼Si i∈T

i∈T

xi ∈Si

i∈T

 X

ωpxi  .

xi ∈−ξi ·Si

Taking absolute values and applying Lemma 5.1 yields the desired bound: |fb(ξ)| =

Y 1 ℓi

i∈T

ωpxi ≤

xi ∈−ξi ·Si

Y sin(πℓi /p) i∈T

ℓi sin(π/p)

where the last inequality recalls we defined α as maxi∈[n]

sin(πℓi /p) ℓi sin(π/p)

≤ α|T | , o .

To see the last claim about the cos(π/p) upper bound on α when 2 ≤ ℓi ≤ p − 1 for all i, it sin(2π/p) sin(πℓ/p) suffices to show that ℓsin(πℓ/p) sin(π/p) is decreasing in ℓ, since 2 sin(π/p) = cos(π/p). To see that ℓ sin(π/p) is decreasing in ℓ, note that this is equivalent to sin(π(ℓ + 1)/p) sin(πℓ/p) ≤ , ℓ+1 ℓ and that sin(x)/x is decreasing for x ∈ [0, π]. Finally, in practice what we need to lower bound is log(1/α). For α = cos πp , we record below the estimate log cos1π/p ≥ Ω(1/p2 ). 42

Lemma 5.3. There is a constant c > 0, such that log

c 1 = log sec(π/p) ≥ 2 cos(π/p) p

for all p > 2. Proof. For |z| < π2 , the Taylor series for sec z about z = 0 is given by sec z =

∞ X (−1)j E2j

(2j)!

j=0

z 2j .

where the E2j are the Euler numbers [AS48, p. 75, eq. 4.3.68]. Since all these coefficients are positive (the Euler numbers E2j are positive iff j is even [AS48, pp. 804–805]), we in particular 2 have sec z ≥ 1 + z2 . Hence, since πp < π2 by the assumption on p, π2 π log sec p ≥ log 1 + 2 . 4p 2

π Then, since ln(1 + y) ≥ y2 for all y ∈ [0, 1], as p > 2 also guarantees 4p 2 ≤ 1, we find 1 π2 1 1 π2 π2 ln 1 + 2 ≥ · · , log 1 + 2 ≥ 4p ln 2 4p ln 2 2 4p2 2

so we get the claimed lower bound (with c = 8πln 2 ).

Improved Resilience of Linear Ramp Secret Sharing Schemes against Balanced Leakage Functions

In this section we apply our results to the study of leakage-resilient secret sharing schemes. Roughly speaking, an (n, t)-threshold secret sharing scheme encodes a secret s into a set of n shares S1 , . . . , Sn , each assigned to one of n parties, with the property that every subset of at least t parties can pool their shares and perfectly reconstruct s, while any subset of fewer than t parties learns no information about the secret. It is not hard to see that in any (n, t)-threshold secret sharing scheme the length (in bits) of each share must be at least the length of the secret. To obtain small share size compared to the number of parties n, we must weaken the requirements above by allowing a gap between the reconstruction threshold trec (with the property that any subset of parties of size at least trec can reconstruct the secret) and the privacy threshold tpriv (with the property that any subset of parties of size at most tpriv learns no information about the secret) [CCX13]. This corresponds to the notion of ramp secret sharing. The notion of (n, t)threshold secret sharing corresponds to the special case where trec = t and tpriv = trec − 1 = t − 1. We present a formal definition below. Definition 6.1 (Ramp secret sharing scheme). An (n, trec , tpriv )-ramp secret sharing scheme with secret space S is a pair of algorithms (Share, Rec) with Share a randomized algorithm that receives as input a secret s ∈ S and outputs a share Si for the i-th party, i ∈ [n], and Rec a deterministic algorithm that receives a subset T ⊆ [n] of parties and the shares (Si )i∈T corresponding to parties in T and outputs a guess for the secret satisfying the following properties: 43

• Privacy: For any subset T ⊆ [n] such that |T | ≤ tpriv and any two secrets s, s′ ∈ S, the random variables ShareT (s) and ShareT (s′ ) (i.e., the shares of s and s′ corresponding to parties in T , respectively) are identically distributed. • Reconstruction: For any subset T ⊆ [n] such that |T | ≥ trec and any secret s ∈ S we have Pr[Rec(Share(s)T , T ) = s] = 1, with the probability taken over the random coins of Share. When tpriv = trec − 1, we say that (Share, Rec) is an (n, trec )-threshold secret sharing scheme. Linear secret sharing schemes are especially important objects in cryptography (for example, in secure multiparty computation). Informally, these are secret sharing schemes that operate over some finite field Fq , and such that local linear combinations of shares of two secrets yield a correct sharing of the linear combination of the secrets. More precisely, we have the following definition. Definition 6.2 (Linear ramp secret sharing scheme). We say that a ramp secret sharing scheme (Share, Rec) is linear if the following holds: • The Share procedure maps a secret s ∈ Fq to shares Si ∈ Fm q for some integer m; n • For every s ∈ Fq , the tuple Share(s) is uniformly distributed over an affine subspace of (Fm q ) ;

• If S = (S1 , . . . , Sn ) = Share(s) and S ′ = (S1′ , . . . , Sn′ ) = Share(s′ ) for any two secrets s, s′ ∈ Fq , then αS + βS ′ is identically distributed to Share(αs + βs′ ), for any α, β ∈ Fq . We remark that ramp secret sharing schemes are the best we can hope for in regimes where n is much larger than q, which is our main focus here. For example, we must always have trec − tpriv ≥ n−tpriv +1 [CCX13], regardless of the size of the secret and of linearity. In particular, if q is held q constant and tpriv ≤ trec ≤ cn for some constant c < 1, then necessarily trec − tpriv = Ω(n).

6.1

Leakage-Resilience of Linear Secret Sharing Schemes

Motivated by side-channel attacks in cryptography, Benhamouda, Degwekar, Ishai, and Rabin [BDIR21] studied a different mode of attack on secret sharing schemes. They considered an attacker that learns some side information about every share (as opposed to an attacker that learns full information about a small subset of shares). The goal is then to ensure that the secret remains hidden from such an adversary, in which case we call the secret sharing scheme leakage-resilient. Studying this requires specifying the leakage functions that the adversary can apply to the shares. We first provide a general definition of leakage-resilience against an abstract family of leakages, and then discuss the important special case on which we focus (bounded local leakage). Definition 6.3 (Statistical distance). The statistical distance between two discrete random variables X and Y supported on a finite set S, denoted by SD(X, Y ), is defined as SD(X, Y ) = max | Pr[X ∈ A] − Pr[Y ∈ A]| = A⊆S

1X | Pr[X = s] − Pr[Y = s]|. 2 s∈S

We may write X ≈ε Y , and say that X and Y are ε-close, when SD(X, Y ) ≤ ε. 44

Definition 6.4 (Leakage-resilient ramp secret sharing scheme). An (n, trec , tpriv , G, ε)-leakageresilient ramp secret sharing scheme is an (n, trec , tpriv )-ramp secret sharing scheme with the following additional property: • Leakage-resilience against G: For any leakage function g ∈ G and any two secrets s, s′ ∈ S with corresponding shares S = (S1 , . . . , Sn ) = Share(s) and S ′ = (S1′ , . . . , Sn′ ) = Share(s′ ), we have g(S) ≈ε g(S ′ ). When the remaining parameters are not relevant, we may also say that (Share, Rec) is (G, ε)leakage-resilient. We will be interested in linear ramp secret sharing schemes with m = 1, i.e., whose secrets and shares are elements of Fq . The most well-studied leakage model for secret sharing is bounded local leakage, which corresponds to independently applying a leakage function with bounded output length to each share. For simplicity, and because this already yields a highly non-trivial problem, we focus on the special case where leakage functions have 1-bit output. More precisely, this corresponds to the family G containing all functions g = (g1 , . . . , gn ) of the form g(S) = (g1 (S1 ), . . . , gn (Sn )), for possibly distinct bounded-output functions gi : Fq → {0, 1}. Secret sharing schemes that are (G, ε)-leakage-resilient for this family G are commonly called ε-locally leakage-resilient, and we use this name too. As we discuss in the next section, known analysis of leakage-resilient secret sharing suggests that the most difficult type of bounded local leakage functions to handle are balanced leakage functions. These will be our main focus, and we now provide a formal definition. Definition 6.5. We say that a tuple of functions g = (g1 , . . . , gn ) with gi : Fq → {0, 1} is γbalanced if 1 1 −1 − γ q ≤ |gi (0)| ≤ +γ q 2 2 for all i ∈ [n]. We denote the family of all γ-balanced tuples by Gγ .

6.2

Prior Work on Leakage-Resilience of Linear Secret Sharing Schemes and Our Result

The study of the leakage-resilience of linear threshold secret sharing schemes has attracted significant attention ever since its introduction in [BDIR21]. Establishing the local leakage-resilience of a secret sharing scheme becomes easier when the reconstruction threshold grows. Given this, one basic question in this area is to pinpoint the smallest reconstruction threshold (as a function of the number of parties n) that allows for resilience against bounded local leakage. General bounded local leakage. The state-of-the-art (non-explicit) result for locally leakageresilient linear threshold secret sharing schemes is due to Maji, Paskin-Cherniavsky, Suad, and Wang [MPSW21], who showed the existence of ε-locally leakage-resilient linear (n, t)-threshold 45

secret sharing schemes with threshold t = ( 12 + ε)n and exponentially small ε, for any ε > 0, over an exponentially large field of prime order q = 2Θ(n) .7 This is achieved by considering secret sharing schemes induced by random linear codes, as we discuss in more detail below. The best known explicit construction of locally leakage-resilient linear threshold secret sharing schemes is due to Kasser [Kas24], who showed that Shamir’s secret sharing is ε-locally leakage-resilient with exponentially small ε for any threshold t ≥ 0.668n. It has been conjectured that there exist locally leakage-resilient linear threshold secret sharing schemes with threshold t = cn for any constant c > 0, and that this holds even for Shamir’s secret sharing [BDIR21]. Motivated by the prospect of constructing leakage-resilient secret sharing schemes with small share size (for which a gap between the privacy and reconstruction thresholds is unavoidable, as discussed above), Tjuawinata and Xing [TX22] studied the leakage-resilience of linear ramp secret sharing schemes over constant-sized fields. They use algebraic-geometric codes to obtain explicit constructions (for thresholds above n/2). Restricted bounded local leakage. The state-of-the-art result from [MPSW21] hits a fundamental barrier at threshold n/2. Indeed, this work uses a Fourier-analytic proxy to establish local leakage-resilience that fails against quadratic residue leakage (for each share, leak whether it is a quadratic residue or not) for any threshold t < n/2. This has motivated work on restricted types of bounded leakage, in particular with the aim of breaking this n/2 barrier. Note that since the number of quadratic residues modulo a prime q > 2 is q−1 2 , quadratic residue 1 . Therefore, the barrier to the approach of [MPSW21] is a very leakage is γ-balanced with γ = 2q balanced leakage function. Unbalanced bounded local leakage functions, on the other hand, seem to be much easier to handle. Klein and Komargodski [KK23] showed that Shamir’s secret sharing is resilient against unbalanced leakage functions for any threshold t ≥ 0.01n. This goes well below the n/2 barrier of [MPSW21]. Klein and Komargodski [KK23] also studied γ-balanced leakage functions with sufficiently small γ > 0, and showed that Shamir’s secret sharing is leakage-resilient for any threshold t ≥ 0.58n. Afterwards, Nguyen [Ngu24] developed an alternative proxy for establishing local leakageresilience based on Gowers uniformity norms, and used it to show that Shamir’s secret sharing with any linear threshold t = cn is resilient against almost all bounded local leakage functions, in the following sense: if we sample a tuple of leakage functions gi : Fq → {0, 1} uniformly at random, the probability of hitting a tuple of leakage functions not handled by the proxy is very small. This result is incomparable to the above. Summarizing, the current state of affairs is that the existence of linear threshold and ramp secret sharing schemes with reconstruction threshold trec < n/2 resilient against all γ-balanced functions remains open even for very small constant γ > 0. Our result, which we state below in simplified form for constant field size, makes progress on this question whenever the field size does not grow too fast, in which case we must necessarily focus on ramp secret sharing. Theorem 6.6 (Simplified version of Theorem 6.15, see also Corollary 6.16). Fix an arbitrary 8 1 constant γ ∈ (0, 1/2). Fix also an arbitrary prime q > 1−2γ and an arbitrary constant η ∈ (0, 2 log q ). Then, for all sufficiently large n there exists an (n, trec , tpriv , Gγ , ε)-leakage-resilient linear ramp 7

It is easy to see that local leakage-resilience cannot be achieved over fields of characteristic 2 [BDIR21].

secret sharing scheme over Fq with 1 2 1 + η − o(1) n ≤ tpriv < trec ≤ logq +η+ + o(1) n logq 1 − 2γ 1 − 2γ log q Ω(1)

and ε = q −n

The next sections are devoted to proving a more general version of Theorem 6.6. We begin by setting up the standard underlying framework for building linear ramp secret sharing schemes out of linear codes, which matches that used by [MPSW21].

6.3

Linear Ramp Secret Sharing from Linear Codes

Towards proving Theorem 6.6, we will study a classical construction of linear secret sharing schemes from error-correcting codes due to Massey [Mas95], which we proceed to describe. Let C + ⊆ Fn+1 q (n+1)×(k+1)

be a linear code with corresponding generator matrix G+ ∈ Fq we assume to be of the form 1 0 + , G = v G

in systematic form, which

where v ∈ Fnq and G ∈ Fn×k . Then, the Massey secret sharing scheme associated with C + has q secret space Fq and works as follows: by setting x0 = s and sampling x1 , . . . , xk ∼ Fq . • To share a secret s ∈ Fq , choose x ∈ Fk+1 q + + + + + Then, compute c = (c0 , c1 , . . . , cn ) = G x, and set the i-th share to be c+ i for i ∈ [n]. Note = s. that c+ 0 • Given a subset of parties T ⊆ [n] and the corresponding shares (Si )i∈T , find the unique + codeword c+ ∈ C + such that c+ i = Si for all i ∈ T and output s = c0 . It is not hard to see that the minimum distance and dual distance of C + respectively control the reconstruction and privacy thresholds of the resulting ramp secret sharing scheme, as formalized in the next lemma. be a linear code with distance d and dual distance d⊥ . Then, the Lemma 6.7. Let C + ⊆ Fn+1 q Massey secret sharing scheme associated with C + is an (n, trec = n − d + 2, tpriv = d⊥ − 2)-ramp secret sharing scheme. Proof. We provide a short argument for completeness. To see the claim about reconstruction, note that since C + has minimum distance d, it corrects any d − 1 erasures. Therefore, (n + 1) − (d − 1) = n − d + 2 shares are sufficient to recover c+ = Gx, and so we recover the secret + ⊥ s = c+ 0 . To see the claim about privacy, note that since C has dual distance d , then the uniform + ⊥ + distribution over C is (d − 1)-wise independent. This means that if c ∼ C + , then for any + + indices 1 ≤ i1 < i2 < · · · < id⊥ −2 ≤ n we have that (c+ 0 , ci1 , . . . , ci ⊥ ) is uniformly distributed d

−2

⊥ over Fdq −1 . This means that the shares associated with parties i1 , . . . , id⊥ −2 are independent of the secret c+ 0.

Remark 6.8. If C + is an MDS code of dimension k + 1, then Lemma 6.7 yields a linear (n, k)threshold secret sharing scheme. First, since d = (n + 1) − k + 1 = n − k + 2, we get that trec = n − d + 2 = k. Second, since the dual of C + is also MDS with dimension k ⊥ = n + 1 − k, we get that d⊥ = (n + 1) − k ⊥ + 1 = k + 1, and so tpriv = d⊥ − 2 = k − 1 = trec − 1. If the field size q is sufficiently large compared to the block length n, then a random linear code will be MDS with high probability. This fact was leveraged by [MPSW21] to obtain locally leakageresilient linear threshold secret sharing schemes from random linear codes over exponentially large fields. To study the local leakage-resilience of a Massey secret sharing scheme based on a linear code C + the following alternative perspective is useful. Let G ∈ Fn×k be the matrix obtained by removing q + the first column and first row of G . Then, G is the generator matrix of a code C ⊆ Fnq , which we call the reduced code of C + . Denote the first column of G+ by v + = (1, v1 , . . . , vn )⊤ , and let v = (v1 , . . . , vn )⊤ . Sharing a secret s ∈ Fq using the Massey secret sharing scheme associated with C + is equivalent to the following: sample x ∼ Fkq , compute c = (c1 , . . . , cn )⊤ = s · v + Gx, and set the i-th share to be ci . In other words, the shares of s are generated by sampling a vector uniformly at random from the affine subspace s · v + C. This alternative perspective helps us see that the leakage-resilience of this secret sharing scheme is controlled by the discrepancy of the reduced code C, as formalized in the next lemma. Lemma 6.9. Let (Share, Rec) be the Massey ramp secret sharing scheme associated to a linear with reduced code C ⊆ Fnq . Suppose that code C + ⊆ Fn+1 q SD(g(C), g(Un )) ≤ ε for all γ-balanced tuples of leakage functions g = (g1 , . . . , gn ). Then, (Share, Rec) is (Gγ , 2ε)leakage-resilient. Proof. Fix an arbitrary γ-balanced tuple of leakage functions g = (g1 , . . . , gn ). Fix also two secrets s, s′ ∈ Fq , with corresponding tuples of shares S = (S1 , . . . , Sn ) and S ′ = (S1′ , . . . , Sn′ ), respectively. Recall that the shares of s (resp. s′ ) correspond to a uniformly random sample from s · v + C (resp. s′ · v + C). Let X and X ′ be independent and uniformly distributed over C. Define also gs (z) = g(s · v + z) for any s ∈ Fq , and note that gs is a tuple of γ-balanced functions as well. Then, SD(g(S), g(S ′ )) ≤ SD(g(s · v + X), g(Un )) + SD(g(s′ · v + X ′ ), g(Un )) = SD(gs (X), g(Un )) + SD(gs′ (X ′ ), g(Un )) = SD(gs (X), gs (Un )) + SD(gs′ (X ′ ), gs′ (Un )) = SD(gs (C), gs (Un )) + SD(gs′ (C), gs′ (Un )) ≤ 2ε. The first inequality follows by the triangle inequality, the second equality uses the fact that g(Un ) and gs (Un ) are identically distributed for any s ∈ Fq , and the last inequality uses the hypothesis from the lemma statement applied to gs and gs′ , which are both γ-balanced. Remark 6.10. We emphasize that there is no real novelty in the above statement and lemma; it is at least implicit in prior works, e.g., [BDIR21]. Additionally, we remark that there is nothing particularly special about the family Gγ ; all that is required is for the family to be closed under translations (i.e., if g is in the family, then so is the function gz (x) = g(x + z) for all z ∈ Fnq ). 48

6.4

Resilience of Massey Ramp Secret Sharing Schemes from Random Linear Codes against γ-Balanced Leakage Functions

We now use the standard framework described in Section 6.3 to prove Theorem 6.6. In fact, we will prove the stronger statement that a random linear code yields a linear ramp secret sharing scheme with the desired properties with high probability. 6.4.1

Leakage-Resilience of Low-Rate Random Linear Codes

We begin by proving our key lemma, which establishes the resilience of low-rate random linear codes against γ-balanced leakage functions, with the help of our main Theorem 2.5. We will then couple this result with Lemma 6.9 to show the existence of Massey ramp secret sharing schemes with reconstruction and privacy thresholds well below the 1/2-barrier appearing in prior works. 2 Lemma 6.11. Fix any constant γ ∈ (0, 21 ). For any given integer n, let q > 1−2γ be a prime and 2 n η ∈ 0, 50 (both possibly depending on n) satisfying q2 log(q/η) → ∞ as n → ∞. Then, 51 logq 1−2γ n for all sufficiently large n the following holds. Let C ⊆ Fq be a random linear code of rate R = 2 logq 1−2γ + η. For a tuple of leakage functions g = (g1 , . . . , gn ), write g(C) = (g1 (c1 ), . . . , gn (cn )) for c ∼ C and g(Un ) = (g1 (u1 ), . . . , gn (un )) for u ∼ Fnq . Then,

SD(g(C), g(Un )) ≤ q

−

ηn 2q 2 log(100q/η) ηn

simultaneously for all γ-balanced tuples of leakage functions g with probability at least 1 − q − 100 − q

n(1+(q+1)/ log q)−

η 2 n2 80q 4 log2 (100q/η)

over the sampling of C.

Proof. We apply Corollary 2.6. For each tuple g = (g1 , . . . , gn ), index i ∈ [n], and bit a ∈ {0, 1}, define Sg,i,a := gi−1 (a). For b = (b1 , . . . , bn ) ∈ {0, 1}n , define Sg,b := Sg,1,b1 × · · · × Sg,n,bn . Note that 1 1 − γ q ≤ |Sg,i,b | ≤ + γ q, 2 2 since g is γ-balanced. Consider the family of functions F consisting of all normalized indicator functions fg,b =

q n 1Sg,b |Sg,b | .

Note that |F| ≤ 2n · 2qn = q n(q+1)/ log q . Also, ∥fg,b ∥∞ ≤

1 n 1 2 −γ

with equality for some g and b, and so 1 β = max logq ∥fg,b ∥∞ = logq fg,b ∈F n

2 1 − 2γ

We can also show that the functions fg,b are appropriately Fourier-concentrated. Fix y ∈ Fnq . Since q is prime, by Lemma 5.2 we get that fd g,b (y) ≤

Y sin(π|Sg,i,b |/q) ≤ cos(π/q)wt(y) , |Sg,i,b | sin(π/q)

i:yi ̸=0

where we have used the fact that 2 ≤ |Sg,i,b | ≤ q − 1 by the fact that γ < 21 − 1q . Therefore, the functions fg,b are α-Fourier-concentrated with α = cos(π/q) < 1. We now show how to instantiate Corollary 2.6 to obtain the desired result. First, note that C 50 has rate β + η with η ∈ 0, 51 β . To control the λ parameter in the statement of Corollary 2.6, note that α = cos(π/q) ≥ 10012 q2 for all q > 2, and so log(1/α) ≤ 1, 2 log(100q/η) log(1/α) log(1/α) = 2 log(100q/η) . Take meaning that λ = min 1, 2 log(100q/η) θ=

ηλ ∈ (0, ηλ). 2

Note that θn → ∞ as n → ∞ since log(1/α) = log(1/ cos(π/q)) ≥ Ω(1/q 2 ) for all q > 2 by n Lemma 5.3, and since q2 log(q/η) → ∞ as n → ∞ by hypothesis. Finally, instantiating Corollary 2.6 with F and these choices of η and θ gives that |δC,fg,b | ≤ q −2(ηλ−θ)n = q −ηλn ≤ q

−

ηn 2q 2 log(100q/η)

(17)

simultaneously for every fg,b with probability at least ηn

θ 2 n2

ηn

1 − q − 100 − |F |q n− 20 ≥ 1 − q − 100 − q

n(1+(q+1)/ log q)−

η 2 n2 80q 4 log2 (100q/η)

To conclude the proof, fix an arbitrary tuple of γ-balanced leakage functions g and note that SD(g(C), g(Un )) = = = ≤

1 2 1 2 1 2 1 2

≤q

X b∈{0,1}

−

Pr [g(c) = b] − Prn [g(u) = b]

c∼C

u∼Fq

|C ∩ Sg,b | |Sg,b | − n |C| q n |Sg,b | δC,fg,b qn n ηn |Sg,b | − 2q2 log(100q/η) · q qn n

ηn 2q 2 log(100q/η)

where the first inequality follows from Eq. (17) and the second inequality uses the fact that, for any fixed g, the sets Sg,b partition Fnq . The following corollary highlights that Lemma 6.11 gives good guarantees even when the field size q is polynomial in n.

2 )) and any prime q ≤ n1/5−ν Corollary 6.12. In the context of Lemma 6.11, take η = Θ(logq ( 1−2γ 2 for an arbitrary constant ν > 0. Let C ⊆ Fnq be a random linear code of rate R = logq 1−2γ + η. Then, Ω(1) SD(g(C), g(Un )) ≤ q −n Ω(1)

simultaneously for all γ-balanced tuples of leakage functions g with probability at least 1 − q −n over the sampling of C.

Proof. Note that η = Ω(1/ log q) since we take γ to be a fixed constant. Therefore, q 2 log(100q/η) = O(q 2 log q), and so for the conditions of Lemma 6.11 to be satisfied it is enough for q to satisfy n → ∞ as n → ∞, which holds due to our upper bound on q above. Again because η = q 2 log q Ω(1/ log q), from Lemma 6.11 we get that |δC,fg,b | ≤ q

−Ω 2 n 2 q log q

= q −n

Ω(1)

simultaneously for all fg,b with probability at least 1−q

ηn − 100

−q

n(1+(q+1)/ log q)−

η 2 n2 80q 4 log2 (100q/η)

Ω(1)

= 1 − q −n

n In the equality we used the fact that η = Ω(1/ log q) and that q4 log = ω(nq) under our assumption 4 q

that q ≤ n1/5−ν . 6.4.2

The Main Result for Massey Ramp Secret Sharing

The following theorem is an easy consequence of Lemmas 6.7, 6.9 and 6.11. It shows that the 2 Massey ramp secret sharing scheme induced by a code of rate slightly above logq 1−2γ will be leakage-resilient against the family of γ-balanced leakage functions with high probability. For sufficiently large q (as a function of γ), both thresholds will be linear in n and much smaller than the n/2-barrier present in prior works [MPSW21, TX22]. First, we state two well-known facts that will be useful in our analysis. The first one is easily implied from the proof of [GRS25, Section 4.2.2, Theorem 4.2]. Recall that the q-ary entropy function hq has a well-defined continuous inverse on the interval [0, 1 − 1/q]. Lemma 6.13. Suppose that C ⊆ Fnq is sampled from a distribution over linear codes of rate R such that for all x ∈ Fnq \ {0} we have Pr[x ∈ C] ≤ q k−n . Let θ > 0 be arbitrary (possibly depending on n −θn . and q). Then, C has minimum distance at least h−1 q (1 − R − θ)n with probability at least 1 − q The second fact gives a simple bound on the q-ary entropy function that will be useful to control its inverse later. A proof can be found in [GRS25, proof of Proposition 3.3.4]. Lemma 6.14. For any positive integer q and real number ρ ∈ (0, 1 − 1/q] we have hq (ρ) ≤ ρ + 1 Therefore, h−1 q (ρ + log q ) ≥ ρ.

1 . log q

We are now ready to prove our main result. 1 Theorem 6.15 (Full version of Theorem 6.6). Fix constant γ ∈ (0, an arbitrary 2 ). For any given log n

q 8 50 2 2 integer n, let q > 1−2γ be an arbitrary prime, η ∈ 0, 51 logq 1−2γ , and θ ∈ n , logq 1−2γ n → ∞ as n → ∞. Then, for all sufficiently (all possibly depending on n) satisfying q2 log(q/η) n large n the following holds. Let C ⊆ Fq be a random linear code of dimension Rn with R = 2 + η < 1 − θ, let v ∈ Fnq be sampled uniformly (and independently of G), and let logq 1−2γ

C + ⊆ Fn+1 be the code generated by q 1 0 G = ∈ Fq(n+1)×(k+1) . v G +

Then, the Massey ramp secret sharing scheme associated with C + is an (n, trec , tpriv , Gγ , ε)-leakageresilient ramp secret sharing scheme with 1 −1 trec ≤ (1 − hq (1 − R − θ))n + 2 ≤ R + θ + n + 2, log q 1 n − 2, tpriv ≥ h−1 q (R − θ)n − 2 ≥ R − θ − log q and ε ≤ 2q

−

ηn 2q 2 log(100q/η)

with probability at least 1−q

−θn/2

−q

−(1−R−θ)n

−q

ηn − 100

−q

n(1+(q+1) logq 2)−

η 2 n2 80q 4 log2 (100q/η)

over the sampling of C + . 1 Proof. Note that C + ⊆ Fn+1 is a linear code of design rate R′ satisfying R ≤ R′ ≤ R + n+1 . We q + ′ first note that C has rate R with high probability. Indeed, this is the probability that G+ has rank k + 1, which is the same as the probability that G has rank k, which is k−1 Y

1−

i=0

1 q n−i

≥ 1 − kq k−n ≥ 1 − q −(1−R)n+logq n ≥ 1 − q −(1−R−θ)n

log n

since θ > nq by hypothesis. We next observe that if x ∈ Fn+1 \ {0}, then q h i + Pr x ∈ C + = Pr ∃m ∈ Fk+1 \ {0} s.t. G m = x ≤ q

v,G

X m∈Fk+1 \{0} q

Pr G+ m = x .

v,G

(18)

Now, if one writes m = (m0 , m̃) with m̃ ∈ Fkq and x = (x0 , x̃) with x̃ ∈ Fnq , we see G+ m = x ⇐⇒ m0 v + Gm̃ = x, which holds iff m0 = x0 and Gm̃ = x̃ − x0 v. Now, if m̃ = 0, so m0 = x0 ̸= 0,

we have Gm̃ = x̃ − x0 v iff v = x̃, which occurs with probability q −n . Otherwise, Gm̃ is uniformly random over Fnq , so again Pr[Gm̃ = x̃ − x0 v] = q −n . Thus, X q −n ≤ q k · q −n = q (k+1)−(n+1) . (18) = \{0} m∈Fk+1 q m0 =x0

We can therefore apply Lemma 6.13 to conclude that C + has distance at least h−1 q (1 − R − θ)(n + 1) −θ(n+1) with probability at least 1 − q . + As for the dual of C , we have x ∈ (C + )⊥ if and only if x⊤ G+ = 0. Writing again x = (x0 , x̃) with x0 ∈ Fq and x̃ ∈ Fnq , this is thus equivalent to ⟨v, x̃⟩ = x0 and x̃⊤ G = 0. If x̃ = 0, then x0 ̸= 0, so the probability that ⟨v, x̃⟩ = x0 is 0 (we have Pr[⟨v, x̃⟩ = 0] = 1). Else, (⟨v, x̃⟩, x̃T G) is distributed uniformly over Fk+1 (over the randomness of v and G), so it equals 0 with probability q q −(k+1) . Hence, h i q (n+1)−(k+1) Pr x ∈ (C + )⊥ ≤ q −(k+1) = , v,G q n+1 so we may again apply Lemma 6.13 to conclude that (C + )⊥ has distance at least h−1 q (R − θ)(n + 1) −θ(n+1) with probability at least 1 − q . Assuming these three favourable events hold, invoking Lemma 6.7, we conclude that the associated Massey ramp secret sharing scheme will have reconstruction threshold 1 trec = n − d + 2 ≤ 1 − h−1 q (1 − R − θ) n + 2 ≤ R + θ + log q n + 2 and privacy threshold 1 tpriv = d⊥ − 2 ≥ h−1 q (R − θ)n − 2 ≥ R − θ − log q n − 2. The rightmost bounds on trec and tpriv above follow from Lemma 6.14, noting that 1q ≤ R ≤ 1 − 1q (with the upper bound holding by the lower bound on q from the theorem statement, which implies 2 that (1 − 1q ) log q > 2 log( 1−2γ ) > R log q) and that θ < R by hypothesis. The claim about leakage-resilience follows directly by combining Lemmas 6.9 and 6.11, and the claim about the probability with which the desired properties all hold over the sampling of C + follows by a union bound combining the probability lower bound from Lemma 6.11 with the fact that C + has the desired rate, minimum distance, and dual distance with probability at least 1 − q −(1−R−θ)n − 2q −θ(n+1) ≥ 1 − q −(1−R−θ)n − q −θn/2 for all sufficiently large n. By replacing Lemma 6.11 with its simplified version in Corollary 6.12 in the proof of Theorem 6.15, we immediately get that Theorem 6.15 gives good guarantees even when the field size q is polynomial in n, as stated formally in the corollary below. We leave it as an interesting open problem to extend Theorem 6.15 to much larger fields. If such a statement held for exponentially large field size q, then we would get existence of linear threshold secret sharing schemes with threshold much smaller than n/2 and great resilience against balanced leakage functions. This is because a random linear code over an exponentially size field will be MDS with high probability. Corollary 6.16. Fix any constants γ ∈ (0, 1/2), ν ∈ (0, 1/5), and c ∈ (0, 50/51). In the context 8 2 < q ≤ n1/5−ν , η = c logq ( 1−2γ ), and θ = n−1/2 . of Theorem 6.15, take any prime q satisfying 1−2γ 53

Then, for all sufficiently large n the following holds. Let C ⊆ Fnq be a random linear code of 2 dimension Rn with R = logq 1−2γ + η, let v ∈ Fnq be sampled uniformly (and independently of G), and let C + ⊆ Fn+1 be the code generated by q 1 0 + G = ∈ Fq(n+1)×(k+1) . v G Then, the Massey ramp secret sharing scheme associated with C + is an (n, trec , tpriv , Gγ , ε)-leakageresilient ramp secret sharing scheme with 2 4 + c logq + o(1) n, trec ≤ (R + θ + logq 2)n + 2 = logq 1 − 2γ 1 − 2γ 2 1 + c logq + o(1) n, tpriv ≥ R − θ − logq 2 n − 2 = logq 1 − 2γ 1 − 2γ Ω(1)

and ε ≤ q −n

Ω(1)

with probability at least 1 − q −n

over the sampling of C + .

Acknowledgements Dean Doron is supported in part by Israel Science Foundation grant #857/25 and by NSFBSF grant #2022644. Tal Leonov is supported by Israel Science Foundation grant #3450/24. Jonathan Mosheiff is supported by Israel Science Foundation grant #3450/24 and an Alon Fellowship. Henrique Navas is funded by FCT - Fundação para a Ciência e a Tecnologia, I.P., under grant 2025.05868.BD and by national funds through FCT, I.P., and, when eligible, co-funded by EU funds under project/support UID/50008/2025 – Instituto de Telecomunicações, with DOI 10.54499/UID/50008/2025. Nicolas Resch is supported in part by an NWO (Dutch Research Council) Veni grant VI.Veni.222.347. João Ribeiro is funded by the European Union (LESYNCH, 101218842) and by national funds through FCT – Fundação para a Ciência e a Tecnologia, I.P., and, when eligible, co-funded by EU funds under project/support UID/50008/2025 – Instituto de Telecomunicações, with DOI 10.54499/UID/50008/2025. Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.

References [ADM+ 99] Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, and Gábor Tardos. Linear hash functions. Journal of the ACM (JACM), 46(5):667–683, 1999. [AGL24]

Omar Alrabiah, Venkatesan Guruswami, and Ray Li. Randomly punctured Reed– Solomon codes achieve list-decoding capacity over linear-sized fields. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1458–1469, 2024.

[AS48]

Milton Abramowitz and Irene A Stegun. Handbook of mathematical functions with formulas, graphs, and mathematical tables, volume 55. US Government printing office, 1948. 54

[BCDZ26] Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang. Combinatorial bounds for list recovery via discrete Brascamp-Lieb inequalities. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, pages 365–376, 2026. [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), February 2021. Preliminary version in CRYPTO 2018.

[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, 2023.

[Bli87]

Vladimir Markovich Blinovskii. Lower asymptotic bound on the number of linear code words in a sphere of given radius in Fnq . Problemy Peredachi Informatsii, 23(2):50–53, 1987. Translated in: Problems of Information Transmission, vol. 23, no. 2, pp. 130–132.

[Bsh26]

Nader H Bshouty. A note on second-order expected maximum-load bounds for binary linear hashing. arXiv preprint arXiv:2605.18335, 2026.

[CCX13]

Ignacio Cascudo, Ronald Cramer, and Chaoping Xing. Bounds on the threshold gap in secret sharing and its applications. IEEE Transactions on Information Theory, 59(9):5600–5612, 2013.

[CGV13]

Mahdi Cheraghchi, Venkatesan Guruswami, and Ameya Velingker. Restricted isometry of Fourier matrices and list decodability of random linear codes. SIAM Journal on Computing, 42(5):1888–1914, 2013.

[Cha25]

André Chailloux. OPI × soft decoders. arXiv preprint arXiv:2511.22691, 2025.

[CHLL97] Gérard Cohen, Iiro Honkala, Simon Litsyn, and Antoine Lobstein. Covering Codes, volume 54 of North-Holland Mathematical Library. Elsevier, 1997. [CT25]

André Chailloux and Jean-Pierre Tillich. Quantum advantage from soft decoders. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 738– 749, 2025.

[CZ25]

Yeyuan Chen and Zihan Zhang. Explicit folded Reed-Solomon and multiplicity codes achieve relaxed generalized Singleton bounds. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, page 1–12, New York, NY, USA, 2025. Association for Computing Machinery.

[DD22]

Manik Dhar and Zeev Dvir. Linear hashing with ℓ∞ guarantees and two-sided Kakeya bounds. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 419–428. IEEE, 2022.

[DMRR25] Dean Doron, Jonathan Mosheiff, Nicolas Resch, and João Ribeiro. List-recovery of random linear codes over small fields. IEEE Transactions on Information Theory, 2025.

[GHK11]

Venkatesan Guruswami, Johan Hå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 Hastad, Madhu Sudan, and David Zuckerman. Combinatorial bounds for list decoding. IEEE Transactions on Information Theory, 48(5):1021–1034, 2002. [GLM+ 21] Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters. Bounds for list-decoding and list-recovery of random linear codes. IEEE Transactions on Information Theory, 68(2):923–939, 2021. [GRS25]

Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential Coding Theory. 2025. Draft available at https://cse.buffalo.edu/faculty/atri/courses/ coding-theory/book/web-coding-book.pdf.

[Gur03]

Venkatesan Guruswami. List decoding from erasures: bounds and code constructions. IEEE Transactions on Information Theory, 49(11):2826–2833, 2003.

[GZ23]

Zeyu Guo and Zihan Zhang. Randomly punctured Reed-Solomon codes achieve the list decoding capacity over polynomial-size alphabets. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 164–176. IEEE, 2023.

[JKZ25]

Michael Jaber, Vinayak M Kumar, and David Zuckerman. Linear hashing is optimal. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 245–255, 2025.

[JSW+ 25] Stephen P. Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V. Isakov, Tanuj Khattar, and Ryan Babbush. Optimization by decoded quantum interferometry. Nature, 646(8086):831–836, 2025. [Kas24]

Dustin Kasser. An improvement upon the bounds for the local leakage resilience of Shamir’s secret sharing scheme. In Theory of Cryptography Conference (TCC), page 395–422. Springer Nature Switzerland, December 2024.

[KK23]

Ohad Klein and Ilan Komargodski. New bounds on the local leakage resilience of Shamir’s secret sharing scheme. In Advances in Cryptology – CRYPTO 2023, page 139–170. Springer Nature Switzerland, 2023.

[KSG+ 25] Tanuj Khattar, Noah Shutty, Craig Gidney, Adam Zalcman, Noureldin Yosri, Dmitri Maslov, Ryan Babbush, and Stephen P. Jordan. Verifiable quantum advantage via optimized dqi circuits. arXiv preprint arXiv:2510.10967, 2025. [LMS25]

Matan Levi, Jonathan Mosheiff, and Nikhil Shagrithaya. Random Reed-Solomon codes and random linear codes are locally equivalent. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 2097–2131. IEEE, 2025.

[Loe94]

Hans-Andrea Loeliger. On the basic averaging arguments for linear codes. In Communications and Cryptography: Two Sides of One Tapestry, pages 251–261. Springer, 1994. 56

[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), pages 53–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025.

[LW20]

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

[Mas95]

James L Massey. Some applications of coding theory in cryptography. Codes and Ciphers: Cryptography and Coding IV, pages 33–47, 1995.

[MPSW21] Hemanta K. Maji, Anat Paskin-Cherniavsky, Tom Suad, and Mingyuan Wang. Constructing locally leakage-resilient linear secret-sharing schemes. In Advances in Cryptology – CRYPTO 2021, page 779–808. Springer International Publishing, 2021. [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, pages 257–285, Cham, 2024. Springer Nature Switzerland.

[Ros26]

Ansis Rosmanis. A nearly linear-time decoded quantum interferometry algorithm for the optimal polynomial intersection problem. arXiv preprint arXiv:2601.15171, 2026.

[RW14]

Atri Rudra and Mary Wootters. Every list-decodable code for high noise has abundant near-optimal rate puncturings. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 764–773, 2014.

[RW18]

Atri Rudra and Mary Wootters. Average-radius list-recoverability of random linear codes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 644–662. SIAM, 2018.

[RY24]

Nicolas Resch and Chen Yuan. Threshold rates of code ensembles: Linear is best. IEEE Transactions on Information Theory, 70(7):4823–4842, 2024.

[ST23]

Chong Shangguan and Itzhak Tamo. Generalized Singleton bound and list-decoding Reed–Solomon codes beyond the Johnson radius. SIAM Journal on Computing, 52(3):684–717, 2023.

[SW26]

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

[TX22]

Ivan Tjuawinata and Chaoping Xing. Leakage-resilient secret sharing with constant share size. IEEE Transactions on Information Theory, 68(12):8228–8250, 2022.

[Woo13]

Mary Wootters. On the list decodability of random linear codes with large error rates. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 853–860, 2013.

[ZP81]

Victor Vasilievich Zyablov and Mark Semenovich Pinsker. List concatenated decoding. Problemy Peredachi Informatsii, 17(4):29–33, 1981.

Record · ID 303148 · SHA-256 53ba54141486d57c
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.