Expanding Codes with Polynomial Stretch

summary

The gist

We give a public key encryption scheme with plausible quasi-exponential security based on the conjectured intractability of two constraint satisfaction problems (CSPs)…

In short

This work introduces a public key encryption scheme with plausible quasi-exponential security based on hard constraint satisfaction problems (CSPs) under high corruption rates. The authors conjecture the hardness of a new large alphabet random predicate CSP and the standard kXOR problem when most computations are corrupted. They achieve this by constructing an error-correcting code with specific expansion properties, leading to a scheme secure against distinguishing encryptions.

Key concepts

LARP-CSP
A new type of constraint satisfaction problem defined over a large alphabet and strongly expanding factor graphs. In this setup, the vast majority of the predicate outputs are replaced by random values, making it computationally hard to solve even with significant corruption.
kXOR Problem
The standard kXOR problem is defined over a random factor graph where most parity computations are replaced by random bits. This conjecture forms one of the security foundations for the encryption scheme, suggesting that solving this corrupted version is intractable.
Label Extended Factor Graph
A specific method used to plant cryptographic trapdoors within a CSP structure. This construction is central to creating an error-correcting code with desirable expansion properties, enabling efficient decoding even when a large fraction of the data is corrupt.

Terminology used across episodes

This episode discusses

The paper

Expanding Codes with Polynomial Stretch · Read on arXiv

University of California San Diego · University of California, Los Angeles

We give a polynomial-stretch, constant-arity counterpart to the expanding-code construction of Blasiok, Lou, Rosen, and Sudan (FOCS 2026). For every constant epsilon in(0,1/2), we construct binary matrices with n columns and polynomially many rows, each of weight k=O(epsilon-6), such that the union of the supports of any set of at most n 1-epsilon rows has size at least (1-epsilon)k times the number of rows. Nevertheless, a polynomial-time test accepts every codeword (generated by the columns of this matrix) corrupted in at most a 1/2-epsilon fraction of its coordinates, while rejecting a uniformly random vector with high probability. We give two applications. First, we obtain a family of (nearly lossless) constant locality expanders on which Goldreich's pseudorandom generator with the XOR-MAJ predicate can be distinguished from uniform in polynomial time, well within the small-bias parameter regime and the hard regime for known algebraic-immunity/annihilator attacks and algebraic-degree linearization attacks described by Applebaum and Lovett (STOC 2016, SICOMP 2018). Second, we obtain public key encryption from either the constant-noise k XOR conjecture over random graphs or the Goldreich conjecture with XOR-MAJ over random graphs, together with a new planted-hypergraph conjecture. We prove low-degree lower bounds for the planting conjecture, providing evidence for subexponential hardness, and give lower bounds against dimension tests based on coordinatewise products (Schur products) of public-code vectors. The PKE schemes and lower bounds were discovered by the authors. The code construction was discovered by Codex / ChatGPT 6 Astra Ultra using harness components from the UCLA Moonshot Harness Project, in response to a general strategy suggested by the authors. See the end of the introduction for a discussion.

Transcript

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

Nadia: We're looking at the paper: "Expanding Codes with Polynomial Stretch".

Elias: Here's the gist of the paper. We give a public key encryption scheme with plausible quasi-exponential security based on the conjectured intractability of two constraint satisfaction problems (CSPs), both instantiated with a corruption rate of 1 - o(1).

Nadia: First, we conjecture the hardness of a new large alphabet random predicate CSP (LARP-CSP) defined over an arbitrary but strongly expanding factor graph, where the vast majority of predicate outputs are replaced with random outputs.

Elias: Second, we conjecture the hardness of the standard kXOR problem defined over a random factor graph, again where the vast majority of parity computations are replaced with random bits.

Nadia: Our public key encryption scheme is the first to leverage high corruption CSPs while simultaneously achieving a plausible security level far above quasi-polynomial, specifically squared omega(1) lambda, where lambda = O(1) is the running time of the algorithms in our scheme.

Paper summary: Nadia: So, looking at the whole paper on "Expanding Codes with Polynomial Stretch," the authors are putting forward a public key encryption scheme whose security relies on the conjectured intractability of two problems, LARP-CSP and kXOR, both instantiated with a corruption rate of one minus some little amount.

Elias: The main thrust is that they're using label extended factor graphs to plant trapdoors between these CSPs, which they then use to build an error correcting code structure that has an expanding generator matrix capable of efficient decoding from high corruption.

Priya: It seems like the title itself really captures the essence: expanding codes with polynomial stretch. It suggests that by using this specific construction method, you can achieve a security level that scales way beyond what we've seen with simpler methods.

Nadia: Yeah, it’s about leveraging these high corruption CSPs to hit a security level far above quasi-polynomial, specifically something like exp to the power of two times log Omega of one times lambda. It shows that this is possible without resorting to the assumptions we usually rely on for PKE schemes.

Elias: The work connects the hardness of these specific problems—the LARP-CSP and kXOR with high corruption—to a concrete construction for an error correcting code, which is a significant link between theoretical complexity and practical coding theory.

Priya: For someone who just listens, it means there’s a new family of public key encryption schemes where the security argument isn't based on traditional number-theoretic problems that might be vulnerable to quantum computers.

Nadia: The authors show that even when you corrupt most of the information in these CSPs, you can still get a scheme with plausible security guarantees, provided those underlying conjectures about the hardness of those corrupted problems hold true.

Conclusion: Nadia: So, we're wrapping up on "Expanding Codes with Polynomial Stretch," looking at the title and who wrote this stuff now.

Elias: The authors are tackling public key encryption using a method that relies on planting trapdoors inside these complex constraint satisfaction problems.

Nadia: It seems like they've linked the security of this new encryption scheme directly to how hard it is to solve certain types of random puzzles when most of the information is corrupted.

Elias: Exactly, and they use these puzzles—specifically a large alphabet random predicate constraint satisfaction problem and a standard XOR problem—with a corruption rate that’s almost complete.

Nadia: And what this means for us is that we're looking at security levels that scale way beyond what we usually expect from these kinds of hard problems.

Elias: They claim this pushes the security up to something like exponential squared times the logarithm of one times lambda, where lambda is just some running time parameter.

Nadia: That's a lot of work for a system, and it's based on these conjectures about how hard those corrupted versions of the problems are to solve.

Elias: And they’ve actually connected this complexity result to a concrete method for building an error correcting code that has this expanding generator matrix.

Nadia: It suggests there might be a way to build very strong encryption schemes by exploiting these high corruption scenarios in a structured way.

Elias: It opens up the question of whether we can use these specific, high-corruption problems as a foundation for truly robust cryptography.

More episodes

← Home