# Expanding Codes with Polynomial Stretch

DevFeed: [Expanding Codes with Polynomial Stretch](<https://devfeed.tech/articles/expanding-codes-with-polynomial-stretch-126879.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2604.10479>)

Author: Isaac M Hair, Amit Sahai

Published: 2026-11-10T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Cryptography and Security](<https://devfeed.tech/sources/arxiv-cryptography-and-security.md>)

Topics: [homomorphic encryption](<https://devfeed.tech/topics/homomorphic-encryption.md>), [polynomials](<https://devfeed.tech/topics/polynomials.md>)

Tags: [2016](<https://devfeed.tech/tags/2016.md>), [2018](<https://devfeed.tech/tags/2018.md>), [2026](<https://devfeed.tech/tags/2026.md>), [applications](<https://devfeed.tech/tags/applications.md>), [cryptography](<https://devfeed.tech/tags/cryptography.md>), [cs-cr](<https://devfeed.tech/tags/cs-cr.md>), [dimension](<https://devfeed.tech/tags/dimension.md>), [encryption](<https://devfeed.tech/tags/encryption.md>), [generator](<https://devfeed.tech/tags/generator.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [locality](<https://devfeed.tech/tags/locality.md>), [lower-bounds](<https://devfeed.tech/tags/lower-bounds.md>), [matrix](<https://devfeed.tech/tags/matrix.md>), [noise](<https://devfeed.tech/tags/noise.md>), [public-key](<https://devfeed.tech/tags/public-key.md>), [stretch](<https://devfeed.tech/tags/stretch.md>), [test](<https://devfeed.tech/tags/test.md>), [vector](<https://devfeed.tech/tags/vector.md>), [weight](<https://devfeed.tech/tags/weight.md>), [xor](<https://devfeed.tech/tags/xor.md>)

## AI overview

For each constant ε in (0, 1/2), the authors construct binary matrices with n columns, polynomially many rows, and row weight k = O(ε⁻⁶). Any set of at most n^(1−ε) rows has supports whose union covers at least (1−ε)k times the number of rows. Despite this expansion, a polynomial-time test accepts codewords corrupted on up to a 1/2−ε fraction of coordinates and rejects a uniformly random vector with high probability. Applications include distinguishing Goldreich's XOR-MAJ generator from uniform on nearly lossless constant-locality expanders, and public-key encryption based on stated kXOR, Goldreich, or planted-hypergraph conjectures. The authors also report low-degree and Schur-product dimension-test lower bounds; the planting lower bounds provide evidence for subexponential hardness.

## Source excerpt

arXiv:2604.10479v2 Announce Type: replace 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 $\varepsilon\in(0,1/2)$, we construct binary matrices with $n$ columns and polynomially many rows, each of weight $k=O(\varepsilon^{-6})$, such that the union of the supports of any set of at most $n^{1-\varepsilon}$ rows has size at least $(1-\varepsilon)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-\varepsilon$ 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.