Expanding Codes with Polynomial Stretch
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 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. – 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. – 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The security proof relies on invoking Conjecture 3. p. 6 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. Conjecture 1. 2 (High Corruption Random kXOR Conjecture). 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. 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. 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. 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). 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. 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. Denoting by λ the running
time of the algorithms in our PKE scheme, the lower bound becomes exp¶
2
logΩ(1) λ
©
. Polynomial Calculus Refutations. 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. 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. 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. Suppose we have an (α, β)-decodable expanding code. Then assuming Conjecture 1. 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. 1 (High Corruption LARP-CSP) and Conjecture 1. 2 (High Corruption kXOR) both hold.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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
-
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.
-
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.
-
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.
-
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). -
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
- Approximating Unique Games Using Low Diameter Graph Decomposition
- Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
- The Quasi-Polynomial Low-Degree Conjecture is False
- Computational Hardness of Certifying Bounds on Constrained PCA Problems
- Algorithms for Sparse LPN and LSPN Against Low-noise
- Low-Degree Hardness of Detection for Correlated Erd\H{o}s-R'enyi Graphs
- Detecting Arbitrary Planted Subgraphs in Random Graphs
- Lower bounds for CSP refutation by SDP hierarchies
Related papers
- From Strategy Search to Policy Learning: MCTS-Guided Adversarial Co-Evolution for LLM Safety Alignment
- Privacy Leakage from Recurrent State in LLM Inference
- Incrementally Verifiable Oracle Aided Computation
- Privilege and confidentiality in generative AI workflows
- BadMoE: Backdooring Mixture-of-Experts LLMs via Routing-Aware Triggers and Task-Underutilized Experts
- CoVault: Secure, Scalable Analytics of Personal Data