Expanding Codes with Polynomial Stretch

arXiv:2604.10479 · cs.CR · Submitted 2026-04-12 · 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: 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.

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

cs.CR

Submitted: 2026-04-12

Updated: 2026-11-07

Comments: This work subsumes a previous work by the same authors titled "Public Key Encryption from High-Corruption Constraint Satisfaction Problems.'' The abstract is (slightly) abbreviated to fit arXiv's character limit

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

Importance score: 87/100

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)…

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

Summary

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). p. 0

Where the paper says it

Public Key Encryption from High-Corruption Constraint Satisfaction Problems Isaac M Hair * UCSB, UCLA Amit Sahai † UCLA April 14, 2026 Abstract We give a public key encryption scheme with plausible quasi-exponential security based on the conjectured intractability of two constraint satisfaction problems (CSPs), both of which are instantiated with a corruption rate of 1 − o(1). 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.

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. p. 0
Where the paper says it

Public Key Encryption from High-Corruption Constraint Satisfaction Problems Isaac M Hair * UCSB, UCLA Amit Sahai † UCLA April 14, 2026 Abstract We give a public key encryption scheme with plausible quasi-exponential security based on the conjectured intractability of two constraint satisfaction problems (CSPs), both of which are instantiated with a corruption rate of 1 − o(1). 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.

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. p. 0
Where the paper says it

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. 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.

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. p. 0
Where the paper says it

In support of our hardness conjecture for LARP-CSPs, we give a variety of lower bounds, ruling out many natural attacks including all known attacks that exploit non-random factor graphs. Our public key encryption scheme is the first to leverage high corruption CSPs while simultaneously achieving a plausible security level far above quasi-polynomial.

At the heart of our work is a new method for planting cryptographic trapdoors based on the label extended factor graph for a CSP. p. 0

Where the paper says it

Our public key encryption scheme is the first to leverage high corruption CSPs while simultaneously achieving a plausible security level far above quasi-polynomial. At the heart of our work is a new method for planting cryptographic trapdoors based on the label extended factor graph for a CSP.

To achieve this result, we provide the first uniform construction of an error-correcting code that possesses both an expanding, low density generator matrix and allows for efficient decoding from a 1 - o(1) fraction of corruptions. p. 2
Where the paper says it

Arguments based on label extended factor graphs are common in average-case complexity [Ste10, GS11, BCG+12, AL17, CMMV17], but our work is the first to leverage them for buildin cryptographic trapdoors2 . Along the way to designing our trapdoor technique and decryption algorithm, we give the first uniform construction of an error correcting code with an expanding, low density generator matrix that allows for efficient decoding from a 1 − o(1) fraction of corruptions.

This construction is based on low-rate Reed-Muller codes (Section 5. p. 7
Where the paper says it

– Noisy codewords c ′ , where c ′ is sampled by taking a random codeword c ∈ {Gx : x ∈ F n 2 }, erasing each entry with probability α, and then corrupting (replacing with a random value) each remaining entry with probability β. We give an explicit, uniform, unconditional construction of an (α = 1 − o(1), β = 1 − o(1))-decodable expanding code based on low-rate Reed-Muller codes, with our main contribution being an efficient algorithm to sample an expanding generator matrix; see Theorem 1.

1). The construction of the generator matrix G is given by an explicit randomized algorithm Kck cm(1 n) running in time m O(1), and the distinguishing algorithm Distinguish runs in time m O(1). p. 7
Where the paper says it

– Noisy codewords c ′ , where c ′ is sampled by taking a random codeword c ∈ {Gx : x ∈ F n 2 }, erasing each entry with probability α, and then corrupting (replacing with a random value) each remaining entry with probability β. We give an explicit, uniform, unconditional construction of an (α = 1 − o(1), β = 1 − o(1))-decodable expanding code based on low-rate Reed-Muller codes, with our main contribution being an efficient algorithm to sample an expanding generator matrix; see Theorem 1.

Theorem 5.3 demonstrates that G is a (1 - o(1), n 1-o(1)) -expander with probability 1 - o(1). p. 2
Where the paper says it

Along the way to designing our trapdoor technique and decryption algorithm, we give the first uniform construction of an error correcting code with an expanding, low density generator matrix that allows for efficient decoding from a 1 − o(1) fraction of corruptions. A previous work by Oliveira, Santhanam, and Tell [OST18] achieved this goal only non-constructively: they proved the existence of expander graphs that could be interpreted as giving rise to such a code, but did not show how to construct it.

The security proof relies on invoking Conjecture 3. p. 6

Where the paper says it

Our proof techniques are inspired by a work of Applebaum and Lovett [AL16], in which they prove similar lower bounds for Goldreich’s PRG. 2 Random kXOR Below we give our hardness conjecture for random kXOR.

2 (High Corruption kXOR) and Conjecture 3. p. 6
Where the paper says it

Conjecture 1. 2 (High Corruption Random kXOR Conjecture).

1 (High Corruption LARP-CSP). p. 0
Where the paper says it

Public Key Encryption from High-Corruption Constraint Satisfaction Problems Isaac M Hair * UCSB, UCLA Amit Sahai † UCLA April 14, 2026 Abstract We give a public key encryption scheme with plausible quasi-exponential security based on the conjectured intractability of two constraint satisfaction problems (CSPs), both of which are instantiated with a corruption rate of 1 − o(1). 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.

The hybrid argument shows that the advantage of distinguishing between encryptions of '0' and '1' is less than 0.3 by invoking Conjecture 3. p. 0
Where the paper says it

Public Key Encryption from High-Corruption Constraint Satisfaction Problems Isaac M Hair * UCSB, UCLA Amit Sahai † UCLA April 14, 2026 Abstract We give a public key encryption scheme with plausible quasi-exponential security based on the conjectured intractability of two constraint satisfaction problems (CSPs), both of which are instantiated with a corruption rate of 1 − o(1). 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.

2, and less than a threshold of 1/4 by invoking Conjecture 3. p. 6
Where the paper says it

3 Theorem 6. 13, we show that unsatisfiable (H, F, b) tuples do not have polynomial calculus refutations over F2 of size less than exp n 0.

1 [Lemma 4. p. 5
Where the paper says it

The connection between low degree polynomials and efficient algorithms is not merely circumstantial. The best low degree polynomial algorithm for any hypothesis testing problem is the low degree truncation of a certain optimal hypothesis testing algorithm given by the Neyman-Pearson Lemma (see [KWB19] for a discussion).

9]. Lower bounds support these conjectures, showing that any algorithm solving Problem 2 (the corruption-free version of Conjecture 3. p. 4
Where the paper says it

Below we give lower bounds in support of the High Corruption LARP-CSP Conjecture. All of our lower bounds will be for the corruption-free version of the problem in the conjecture.

1) must have at least squared omega(1) lambda time [Theorem 6. p. 5
Where the paper says it

In Theorem 6. 2 we show that all attacks of this form will have distinguishing advantage at most |Σ| −Ω(k) , even for the corruption-free version of the LARP-CSP Conjecture, and even when allowing the adversary unbounded running time to pick the best subset L, to pick the best coordinate-wise embeddings, and to compute the distance to L.

8], and polynomial calculus refutations yield a lower bound of n 0. p. 5
Where the paper says it

Denoting by λ the running time of the algorithms in our PKE scheme, the lower bound becomes exp¶ 2 logΩ(1) λ © . Polynomial Calculus Refutations.

99 advantage for Problem 2 [Theorem 6. p. 5
Where the paper says it

In Theorem 6. 2 we show that all attacks of this form will have distinguishing advantage at most |Σ| −Ω(k) , even for the corruption-free version of the LARP-CSP Conjecture, and even when allowing the adversary unbounded running time to pick the best subset L, to pick the best coordinate-wise embeddings, and to compute the distance to L.

13]. The resulting PKE scheme is shown to be semantically secure by Theorem 2. p. 8
Where the paper says it

To prove the theorem we give a direct construction of a PKE scheme that has a mild notion of correctness and security. From here, we can apply a black-box amplification theorem of Holenstein and Renner [HR05] to get semantically secure PKE.

7, and it is a (0.99, 0.9) -secure PKE scheme by Theorem 4. p. 8
Where the paper says it

To prove the theorem we give a direct construction of a PKE scheme that has a mild notion of correctness and security. From here, we can apply a black-box amplification theorem of Holenstein and Renner [HR05] to get semantically secure PKE.

13, assuming Conjecture 3. p. 7
Where the paper says it

Suppose we have an (α, β)-decodable expanding code. Then assuming Conjecture 1.

1 and Conjecture 3. p. 0
Where the paper says it

Public Key Encryption from High-Corruption Constraint Satisfaction Problems Isaac M Hair * UCSB, UCLA Amit Sahai † UCLA April 14, 2026 Abstract We give a public key encryption scheme with plausible quasi-exponential security based on the conjectured intractability of two constraint satisfaction problems (CSPs), both of which are instantiated with a corruption rate of 1 − o(1). 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.

2 hold with corruption rates alpha and beta respectively [Theorem 4. p. 7
Where the paper says it

1 (High Corruption LARP-CSP) and Conjecture 1. 2 (High Corruption kXOR) both hold.

13].

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Planting Cryptographic Trapdoors using High Corruption CSPs: The system can build a semantically secure public key encryption scheme from constraint satisfaction problems with high corruption rates of one minus o(1), achieving plausibly quasi-exponential security levels far above quasipolynomial bounds.

  2. Efficient Error Correcting Code Construction: The system utilizes the first uniform construction of an error correcting code that has an expanding, low density generator matrix while simultaneously allowing for efficient decoding from a one minus o(1) fraction of corruptions.

  3. Hardness-Based Security Against Known Attacks: The scheme achieves security by relying on the intractability of two specific CSPs: the large alphabet random predicate CSP and the standard kXOR problem, ruling out many natural attacks including all known attacks that exploit structured factor graphs.

  4. Enhanced Decryption Capability via Low Complexity Testing: Decryption is possible because both the matrix G and the predicate wi = xNG(i,1) +... + xNG(i,k) are of low complexity, allowing the algorithm Distinguish to differentiate noisy vectors from totally random vectors with probability one minus o(1).

  5. Complexity-Aware Security Analysis: The system can demonstrate that a degree n 0.99 advantage for the planted kXOR problem is o(1), which implies that combinatorial algorithms running in time exp n 0.99 over logO(1) n are ineffective for solving related problems.

Abstract

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.

Sources

Related papers