Discrepancy for Random Linear Codes

arXiv:2606.24471 · cs.IT, cs.CC, cs.CR, math.CO, math.IT · Submitted 2026-06-23 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia, and with me are Elias and Priya, guest researcher.

Elias: Today's paper: "Discrepancy for Random Linear Codes".

Nadia: This paper presents two general discrepancy theorems for random linear codes, demonstrating that these codes possess nearly optimal discrepancy-type properties in a broad range of settings.

Elias: First, who's behind it and why it matters.

Title and authors: Nadia: So, we've got this paper from arXiv called "Discrepancy for Random Linear Codes," and to recap, the main gist is that random linear codes actually behave pretty well when you relax the strict decoding rules, specifically in list-decoding and list-recovery scenarios above capacity.

Elias: Yeah, I see it boils down to showing these codes maintain nearly optimal discrepancy properties even when we allow for errors exceeding the theoretical capacity limits. It’s about proving that random linear codes match unstructured random codes in those relaxed settings.

Priya: From a privacy standpoint, what I'm picking up is that this mathematical control over intersection sizes allows us to guarantee robust performance in ways previous bounds couldn't, especially when dealing with structured inputs like lists or rectangles.

Nadia: Exactly, and the real payoff here is applying these theorems to build really strong secret sharing schemes that are resilient against balanced local leakage functions, pushing those security thresholds way past where they used to be.

Elias: I agree about the security aspect; it’s not just theoretical math for me, it’s about what breaks if we try to exploit this structure; the proof hinges on showing a smooth construction sequence to control that deviation growth.

Priya: And what the data really shows is that for list-decoding, we get simultaneous high probability guarantees across all Hamming balls, which is a much tighter statement than just finding one good ball.

Nadia: That level of simultaneous control over all structures is exactly what makes this paper so compelling for anyone looking to design more reliable error correction or data retrieval systems.

Elias: If you look at the complexity, they're using a second-moment method and an auxiliary smoothed function to manage the iterative construction sequence, which is a clever way to handle that one-step change in deviation.

Priya: That methodology translates directly into practical guarantees for list recovery over prime fields, ensuring we can recover nearly all codewords from structured lists with high probability.

Nadia: And that’s where the world impact really hits—these results give us the mathematical bedrock to design secret sharing schemes that are much tougher against side-channel leakage attacks in distributed AI systems.

Elias: I think the implication for cryptography is huge because they've managed to push those threshold gaps significantly higher, moving them well beyond the n/two barrier we saw before.

Priya: The data suggests that this new framework provides a concrete way to quantify exactly how much noise or structural complexity we can tolerate before these randomized systems start failing in terms of decoding accuracy.

Nadia: So, while this isn't just about making codes better, it’s fundamentally about creating new cryptographic primitives that are proven to be resilient against specific types of attacks in complex settings.

Elias: And that opens up avenues for analyzing how much noise or structural complexity we can tolerate before these randomized systems start to fail in terms of list recovery or decoding accuracy.

Priya: I think the real excitement is seeing how this discrepancy theory connects with other areas, like synthetic data generation, because the underlying principles of controlling intersection sizes seem transferable across different combinatorial problems.

Nadia: Absolutely, that connection is what makes this paper so relevant for our broader research landscape today and shows us how to tackle complex security challenges using these structured codes.

The paper's summary: Nadia: So, we've seen that the core of this paper is showing that random linear codes exhibit strong discrepancy properties in list-decoding and list-recovery above capacity, which they proved using a smooth construction sequence.

Nadia: And now we’re looking at what the authors suggest as improvements to these results, and it seems like they are focusing on how to tighten those bounds.

Elias: They seem to be pushing for tighter control over the parameters involved in that construction, specifically aiming to refine how the rate R relates to the error eta and n.

Priya: From a privacy angle, I see them suggesting that by leveraging these discrepancy results further, we can potentially find even more robust guarantees for secret sharing schemes against balanced leakage functions.

Nadia: That’s right, they’re trying to take what they have—the resilience against balanced local leakage—and make the thresholds even more favorable in practical terms.

Elias: I think their focus on refining the smoothness of the construction sequence is key to achieving those tighter bounds; if you can control that growth better at each step, the one-step change in deviation gets smaller.

Priya: The data they present suggests that these refinements could allow for even more efficient secret sharing schemes, meaning fewer parties or smaller share sizes might be needed for a given level of security.

Nadia: That’s the kind of improvement we want to hear when it comes to distributed AI where resource constraints are tight; smaller shares mean more participants can join the secure computation.

Elias: If you look at their future work, they seem keen on generalizing these findings beyond just prime fields and looking at other types of test functions, which would be a big step for applicability.

Priya: I think the implication is that this isn't just a theoretical exercise; it’s setting up a path for designing practical cryptographic tools that can handle real-world noise and leakage models effectively.

Nadia: Exactly, so we move from proving existence to defining the exact parameters needed for building deployable security protocols against nuanced threats.

Elias: If they manage to generalize these theorems across different fields of study, it could provide a unified mathematical language for analyzing the security of various structured data systems.

Priya: It’s exciting because it suggests that the structural properties of linear codes are more versatile than we previously thought when applied to problems like privacy protection.

Nadia: So, the next step is figuring out exactly how to translate these tighter mathematical bounds into a concrete algorithm that an AI system can actually run on.

The paper's improvements: Nadia: So, we've seen that the core of this paper is showing that random linear codes exhibit strong discrepancy properties in list-decoding and list-recovery scenarios above capacity, which they then use to construct very resilient secret sharing schemes.

Elias: It’s a solid piece of theoretical work that helps us understand the limits and possibilities when we try to build secure protocols using these structured codes.

Priya: I think the real excitement is seeing how this discrepancy theory connects with other areas, like synthetic data generation, because the underlying principles of controlling intersection sizes seem transferable across different combinatorial problems.

Nadia: Absolutely, that connection is what makes this paper so relevant for our broader research landscape today and shows us how to tackle complex security challenges using these structured codes.

Elias: It definitely gives us a new framework to think about the parameters we should be setting in our cryptographic constructions moving forward and how they relate to noise levels.

Priya: I think this work sets a high bar for designing systems that need to be robust against both random errors and structured leakage, which is a big win for privacy research.

Nadia: We’ve seen that the implications are substantial for building more secure distributed AI environments by giving us new tools to analyze and improve scheme resilience.

Elias: Indeed, the focus on refining those construction parameters suggests that we're moving toward more efficient and mathematically sound cryptographic primitives.

Priya: It really gives us a better way to quantify exactly how much noise or structural complexity we can tolerate before these randomized systems start to fail in terms of decoding accuracy.

Nadia: So, this paper on "Discrepancy for Random Linear Codes" offers a very practical foundation for designing robust protocols that are secure against subtle leakage attacks.

Elias: We'll keep an eye out for how these findings influence the next generation of code-based cryptography research as we move into those more advanced applications.

Priya: I think this work sets a high bar for designing systems that need to be robust against both random errors and structured leakage, which is a big win for privacy research.

Nadia: We’ve seen that the implications are substantial for building more secure distributed AI environments by giving us new tools to analyze and improve scheme resilience.

Conclusion: Nadia: So we've covered the paper "Discrepancy for Random Linear Codes," which essentially shows that random linear codes have strong discrepancy properties in list-decoding and list-recovery above capacity, and these properties are used to build very resilient secret sharing schemes.

Elias: It’s a solid piece of theoretical work that helps us understand the limits and possibilities when we try to build secure protocols using these structured codes.

Priya: I think the real excitement is seeing how this discrepancy theory connects with other areas, like synthetic data generation, because the underlying principles of controlling intersection sizes seem transferable across different combinatorial problems.

Nadia: Absolutely, that connection is what makes this paper so relevant for our broader research landscape today and shows us how to tackle complex security challenges using these structured codes.

Elias: It definitely gives us a new framework to think about the parameters we should be setting in our cryptographic constructions moving forward and how they relate to noise levels.

Priya: I think this work sets a high bar for designing systems that need to be robust against both random errors and structured leakage, which is a big win for privacy research.

Nadia: We’ve seen that the implications are substantial for building more secure distributed AI environments by giving us new tools to analyze and improve scheme resilience.

Elias: Indeed, the focus on refining those construction parameters suggests that we're moving toward more efficient and mathematically sound cryptographic primitives.

Priya: It really gives us a better way to quantify exactly how much noise or structural complexity we can tolerate before these randomized systems start to fail in terms of decoding accuracy.

Nadia: So, this paper on "Discrepancy for Random Linear Codes" offers a very practical foundation for designing robust protocols that are secure against subtle leakage attacks.

Elias: We'll keep an eye out for how these findings influence the next generation of code-based cryptography research as we move into those more advanced applications.

Priya: I think this work sets a high bar for designing systems that need to be robust against both random errors and structured leakage, which is a big win for privacy research.

Dean Doron, Tal Leonov, Jonathan Mosheiff, Henrique Navas†, Nicolas Resch‡], , orgs_list_raw_names_to_expand

Stein Faculty of Computer and Information Science, Ben-Gurion University · Instituto de Telecomunica¸c˜oes and Departamento de Matem´atica, Instituto Superior T´ecnico, Universidade de Lisboa · Informatics Institute, University of Amsterdam

cs.IT, cs.CC, cs.CR, math.CO, math.IT

Submitted: 2026-06-23

Updated: 2026-09-29

Comments: 65 pages. Upgraded results on locally leakage-resilient ramp secret sharing schemes

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: This paper presents two general discrepancy theorems for random linear codes, demonstrating that these codes possess nearly optimal discrepancy-type properties in a broad range of settings.

Key concepts

Discrepancy Theorems
These theorems control how closely a random linear code's intersections with various combinatorial tests (like Hamming balls or Fourier functions) match expected sizes. Small discrepancy means the code behaves like a perfectly random, unstructured code.
List-Decoding and List-Recovery
These are problems where you try to recover multiple possible codewords from noisy or incomplete information. The paper shows that random linear codes perform very well at these tasks when the error rate is above capacity, matching the performance of purely random codes.
Random Linear Codes
These are mathematical structures used in coding theory where codewords are linear combinations of basis vectors over a finite field. The paper analyzes how these randomly generated codes interact with combinatorial tests to establish their good properties.

Terminology

Summary

This paper presents two general discrepancy theorems for random linear codes, demonstrating that these codes possess nearly optimal discrepancy-type properties in a broad range of settings. These results show that random linear codes behave essentially like unstructured random codes for list-decoding from errors above capacity and zero-error list-recovery above capacity. The authors use these theorems to establish the abundance of n-party linear ramp secret sharing schemes over finite fields with specific privacy and reconstruction thresholds, overcoming previous limitations in this area.

Discrepancy Results for Random Linear Codes

The paper establishes two main discrepancy theorems that control the intersection sizes of a random linear code with various combinatorial tests. The first theorem controls all translates of a fixed test function, while the second applies to large families of Fourier-concentrated test functions.

  1. For any constant prime power q and every n ∈ N, if C is a random linear code of rate R = β + η (where β = 1 − 1/n logq B), then with high probability, for every center z ∈ Fnq, the relative deviation of C with respect to the Hamming ball Bρ(z) is small:

δC,Bz ≤ q−omega(ηn). For list-decoding (where B = Bρ(0)), this recovers and significantly strengthens Blinovsky’s covering-radius theorem [Bli87], which only guarantees that every Hamming ball contains at least one codeword.

  1. For a family F of normalized and α-Fourier-concentrated functions, if C is a random linear code of rate R = β + η, then with high probability, for every f ∈ F, the relative deviation is small:

δC,f ≤ q−εn. This result generalizes the above to zero-error list-recovery over prime fields.

Applications to List-Decoding and List-Recovery

The discrepancy theorems are applied directly to list-decoding and zero-error list-recovery problems, showing that random linear codes match the performance of unstructured random codes above capacity.

  1. For list-decoding, a random linear code of rate 1 − 1/n logq Bρ + ε satisfies:

C ∩ Bρ(z) = (1 ± o(1))C · Bρ qn simultaneously for all radius-ρ Hamming balls B in Fnq with high probability.

  1. For zero-error list-recovery over prime fields, a random linear code of rate 1 − logql + ε satisfies:

C ∩ S = (1 ± o(1))C · l qn simultaneously for all combinatorial rectangles S = S1 × … × Sn, where Si = l for all i, with high probability.

Smoothness and Construction Sequence Control

The proof relies on showing that the code construction sequence is smooth, meaning the deviation at each step is controlled.

  1. The paper constructs the code iteratively: C0:= ∅, and Ci:= Ci−1 + spanai, where ui is sampled uniformly at random from Fnq.

  2. The main challenge is to control the growth of intersections Ci ∩ B throughout this construction sequence by showing that a single common event implies all growth rates are adequately controlled.

  3. This is achieved by using a second-moment method and introducing an auxiliary smoothed function, the averaged convolution Ff, whose variance controls the one-step change in deviation: Varu δC′,f = 1/4 δC,Ff.

Improved Resilience of Linear Ramp Secret Sharing Schemes

The discrepancy results are used to prove new existence theorems for leakage-resilient linear ramp secret sharing schemes against balanced local leakage functions.

  1. The translate theorem (Theorem 2.4) is used to show that random linear codes have strong above-capacity discrepancy properties for a broad class of combinatorial tests, which implies new results about leakage-resilient secret sharing.

  2. The zero-error list-recovery result (Theorem 2.5) is applied to show that there exists an n-party linear ramp secret sharing scheme over Fq with privacy threshold approximately n squared log q and reconstruction threshold approximately 5n squared log q that is resilient against balanced local leakage functions.

  3. The final result, Theorem 6.15, shows that for sufficiently large q (as a function of γ), the Massey ramp secret sharing scheme associated with a random linear code of rate slightly above logq 2(1-2γ) will be leakage-resilient against the family of γ-balanced leakage functions with high probability. This result achieves thresholds well below the n/2 barrier seen in prior work.

Improvements for AI systems

Based on the provided scientific paper, here are specific improvements that can be made to AI systems by leveraging its findings:

The research focuses on showing that random linear codes possess nearly optimal discrepancy-type properties in two key areas: list-decoding and zero-error list-recovery, especially when operating above capacity. These properties are then used to build robust secret sharing schemes against leakage attacks.

Here are the specific improvements and capabilities for an AI system:

)1. Improved Robustness in List Decoding (Above Capacity):

The paper proves that random linear codes behave like unstructured random codes for list-decoding from errors above capacity. This means a code of rate 1 − 1/n logqBρ + ε satisfies a nearly optimal intersection property with all Hamming balls with high probability.

  • AI System Capability: The AI can be used to design or analyze error-correcting codes for applications where the noise level exceeds the theoretical capacity threshold.

  • Specific Improvement: Instead of relying on known bounds that might only hold below capacity, the system can utilize this discrepancy theorem to guarantee that a code will achieve near-optimal performance (i.e., minimal list size) even when errors are above capacity. This leads to more reliable error correction in high-noise environments for data transmission or storage.

)2. Enhanced List Recovery Capabilities (Zero Error):

The paper proves that random linear codes behave like unstructured random codes for zero-error list-recovery above capacity over prime fields, controlling intersections with combinatorial rectangles of bounded side lengths.

  • AI System Capability: The AI can be used to analyze data recovery scenarios where the input is provided in a list format rather than a single word, and the error rate is zero.

  • Specific Improvement: The system can guarantee that for any input list of size l, the code will correctly identify (or recover) nearly all codewords that agree with those lists simultaneously with high probability. This increases the reliability of data retrieval when inputs are noisy or partially corrupted in a structured way (combinatorially).

)3. Creation of Leakage-Resilient Secret Sharing Schemes:

The most significant application is using the discrepancy theorems to construct linear ramp secret sharing schemes resilient against balanced local leakage functions. The paper shows that existing state-of-the-art schemes are limited by thresholds around 1/2n, and the new results push this barrier significantly higher (e.g., to thresholds linearly dependent on n).

  • AI System Capability: The AI can be used to design cryptographic protocols for secure multi-party computation (MPC) or distributed data storage where parties must share secrets but are susceptible to side-channel attacks that leak small amounts of information from each share.

  • Specific Improvement: The AI can generate mathematically proven secret sharing schemes with a ramp structure (a gap between reconstruction and privacy thresholds) that are resilient against any balanced leakage function. This is critical for building secure AI training environments or sensitive data analysis pipelines where local leakage is a known threat model, allowing for smaller, more practical share sizes than previously thought possible.

)4. Optimization of Thresholds:

The research demonstrates that the gap between the privacy threshold and reconstruction threshold in these schemes can be controlled to be much larger than in previous work (e.g., achieving gaps proportional to n).

  • AI System Capability: The AI can be used as a design tool for cryptographic protocols where balancing security (privacy) and utility (reconstruction) is key.

  • Specific Improvement: The system can optimize the gap between privacy and reconstruction thresholds to be as large as possible, maximizing the number of parties that can participate while maintaining strong protection against leakage, leading to more efficient and secure distributed AI systems.

In summary, this paper provides a theoretical foundation for designing AI systems that are:

  1. More reliable under high noise/error conditions (List Decoding).

  2. Capable of robust data recovery from structured input lists (List Recovery).

  3. Cryptographically secure against subtle side-channel leakage attacks (Leakage Resilience) using linear ramp secret sharing schemes with improved threshold gaps.

Abstract

We show that random linear codes (RLCs) 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. Two motivating examples follow: First, RLCs behave essentially like unstructured random codes for list-decoding from errors above capacity. More precisely, an RLC C F q n of rate 1 - 1 over n qB ρ + epsilon, where B ρ is the volume of a radius- ρ Hamming ball in F q n, satisfies C B = (1 plus or minus o(1)) C times B over q n simultaneously for all radius- ρ Hamming balls B with high probability. This vastly generalizes the previously best known fact that RLCs of this rate have covering radius at most ρn with high probability (Blinovsky, 1987). Second, over prime fields, RLCs behave essentially like unstructured random codes for zero-error list-recovery, and list-recovery from erasures, above capacity. More precisely, for a prime q>2 and input list size 2 at most at most q-1, an RLC C F q n of rate 1- q + epsilon will satisfy C S = (1 plus or minus o(1)) C times n over q n simultaneously for all combinatorial rectangles S=S 1 times S 2 times times S n, where S i= for all i, with high probability. An analogous result also holds when we can bound S i only for some of the i 's. We use this to show the abundance of locally leakage-resilient n-party linear ramp secret sharing schemes with any linear reconstruction threshold and sublinear threshold gap O(n/ n) over fields of polynomial size q=Θ(n γ) for a constant γ in(0,1/5). Prior work was stuck at reconstruction thresholds above n/2 for both threshold and ramp schemes.

Sources

Related papers