Conceptio › Archive › arXiv CS

arXiv CSopen access

Public Key Encryption from High-Corruption Constraint Satisfaction Problems

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cryptography, security, privacy, cybersecurity

Public Key Encryption from High-Corruption Constraint Satisfaction Problems Isaac M Hair * UCSB, UCLA

Amit Sahai † UCLA

arXiv:2604.10479v1 [cs.CR] 12 Apr 2026

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. 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. Along the way to achieving our result, we give 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 1 − o(1) fraction of corruptions.

* [email protected] †

[email protected] This research was supported in part from a Simons Investigator Award, DARPA SIEVE award, NTT Research, NSF grant 2333935, BSF grant 2022370, a Xerox Faculty Research Award, a Google Faculty Research Award, an Okawa Foundation Research Grant, and the Symantec Chair of Computer Science. This material is based upon work supported by the Defense Advanced Research Projects Agency through Award HR00112020024.

Introduction

Public key encryption (PKE) [GM84] is a fundamental cryptographic primitive that enables secure transmission of data between two parties over an insecure channel with no prior communication. Despite several decades of research, there are very few sources of computational hardness from which we know how to build PKE, mainly: number-theoretic problems [DH76, RSA78, Rab79], and coding-theoretic/lattice problems [McE78, Ale03, Reg09]. It’s known that the number-theoretic problems are broken by large scale quantum computers [Sho99], which leaves the troublesome possibility that a mathematical breakthrough on the coding-theoretic/lattice problems could render almost all PKE schemes insecure. As such, in the words of Applebaum, Barak, and Wigderson [ABW10], “A major goal of cryptography is to base public-key encryption on assumptions that are weaker, or at least different, than those currently used.” The major challenge in designing any public key encryption scheme is finding methods for planting “trapdoors” that allow for decryption, while still ensuring hardness of breaking the encryption. Despite decades of research, we have few techniques. Developing new techniques, which is the focus of this work, spurs research in both the cryptographic and algorithms communities. The value of research in this direction is multifaceted. First and foremost, finding a broader set of hardness conjectures that imply PKE gives us more confidence in the existence of this primitive, even in a post-quantum world. On a more fundamental level, this type of research gives us a better understanding of the mathematical nature of PKE, and the relationship between PKE and average-case hardness of NP problems. Adopting a high-error CSP Perspective on PKE. In this paper we build a public key encryption scheme from a new source of hardness: very high corruption constraint satisfaction problems (CSPs).1 Constraint satisfaction problems are a foundational topic in average-case complexity (see [KZ17] for a survey), and we have a plethora of lower bounds [BSI99, IPS99, Gri01, Sch08, Nor14, FPV15, AL16, AL16, MW16, KMOW17, CMMV17, WEAM19, Zhu20, MN24] that give a well defined region in which CSPs appear to be computationally intractable. The CSPs of interest to us will take the following form. We are given a set of n variables and a set of m = quasipoly(n) constraints, each of which depends on a size k = polylog(n) subset of the variables. The task is to determine whether there is a hidden “planted” assignment to the variables which satisfies an unusually large number of the constraints, or whether the constraints do not respect any planted assignment. Our CSPs will have a corruption rate of 1−o(1), meaning that (in the case there does exist a planted solution) each constraint is replaced with a corrupted version of itself independently with probability 1 − o(1). The security of our PKE scheme will follow from the intractability of two specific CSPs in this high corruption regime: 1. A new large alphabet, random predicate CSP (LARP-CSP), where the factor graph for constraints and variables is arbitrary but required to be strongly expanding. LARP-CSPs are closely related to Goldreich’s pseudorandom generator [Gol00] and planted hypergraph problems [DMW25]. We give several lower bounds, ruling out many natural attacks on LARP-CSPs including all known attacks which exploit structured factor graphs [OST18]. Intuitively, the conjectured hardness of LARP-CSPs comes from the massive entropy contributed by the random predicates, and LARP-CSPs appear to be computationally intractable even in the corruption-free regime. (But for our PKE scheme all LARPCSPs will have a 1 − o(1) corruption rate.) 1

Our work has led to follow-up work that also uses our perspective [Man26].

2. The standard kXOR problem, where the factor graph for constraints and variables is chosen at random. The main difference between our kXOR problem and more typical versions used for cryptogrpahy is that our corruption rate will be 1 − o(1), as opposed to inverse polynomial. A New Way to Plant Trapdoors. In this paper we introduce the idea of using the label extended factor graph for one CSP to plant a trapdoor in another 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. 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. Beyond Quasi-Polynomial Security. There are a couple existing PKE schemes [ABW10, YZ16] that can be re-framed as relying on the conjectured intractability of high-corruption constraint satisfaction problems. However, all of these schemes achieve a security level of at best λO(log λ) , which is quasi-polynomial. The issue comes from a brute-force decryption barrier. One way to interpret decryption in these schemes is as executing an exponential-time guess-and-check algorithm on a logarithmic size hidden component in the ciphertext. Because the size of the component itself is only logarithmic, an adversary can always guess its location in time λO(log λ) . Our PKE scheme is the first to leverage high-corruption CSPs without resorting to a brute-force-type decryption algorithm, enabling us to achieve a significantly higher security level. In particular, our key ¶ public © Ω(1) log λ , encryption scheme achieves a plausible quasi-exponential (see [Sah26]) security level of exp 2 where λO(1) is the running time of the algorithms in our scheme. This is significantly larger3 than quasipolynomial λO(log λ) and comes close to sub-exponential security, which would be of the form exp{λc } for a constant c ∈ (0, 1). On the “Win-Win” Perspective for Hardness Conjectures for Cryptography. One of the great advances in cryptography that occurred with the advent of probabilistic encryption [GM84] and related breakthroughs is what is known as the “win-win” perspective with regard to hardness assumptions (see, e.g., [GTK15] and references therein). This posits that, ideally, hardness conjectures that are useful for cryptography should be longstanding conjectures in mathematics, like the hardness of integer factorization. When this is so, then either we get a secure cryptosystem, or we refute a longstanding conjecture! This is a beautiful perspective, especially from the point of view of designing cryptosystems with an eye toward real-world deployment. But what about theoretical investigations into foundations of cryptography, like the present research? Indeed, if we look historically, we find that many longstanding mathematical conjectures central to cryptography actually arose from cryptography, perhaps most notably the Diffie Hellman problem, where the Diffie Hellman problem was based on the longstanding conjecture that Discrete Logarithm is hard. Similarly, the Decisional Unbalanced Expansion (DUE) Assumption from [ABW10] had not been posed earlier, and was far from a longstanding conjecture in mathematics, but it too was inspired by the longstanding conjecture that the Densest Subgraph Problem is hard on average. 2

Our work has already led to follow-up work [Man26] that makes use of the label extended factor graph for planting trapdoors in the context of a different CSP. 3 We refer the reader to [Sah26] for a discussion of why quasi-exponential security is a natural notion, and why it is more similar to subexponential security than to quasi-polynomial security.

Nevertheless, we argue that there is a strong “win-win” flavor to these hardness conjectures, including our new large-alphabet random-predicate CSP hardness conjecture, which itself is inspired by the longstanding conjecture that CSPs are hard to solve on average. Namely, by posing these hardness conjectures, that are proven to be useful cryptographically, we create a scientific environment where breaking these conjectures would provide critically needed understanding about what freedom we have in co-designing cryptographic schemes and the hardness conjectures they rely on. Indeed, this is not speculation: the goal of building indistinguishability obfuscation schemes was achieved [JLS21] only through a nearly decade-long research community process of exploring many hardness conjectures that turned out to be broken (e.g. Annihilation Attacks [MSZ16] breaking the hardness conjecture underlying the first cryptographic iO scheme [GGH+ 16]). In our context, one win becomes “deepening our understanding of the hardness of natural average-case problems”, while the other stays “having a secure cryptosystem.” Indeed, recent evidence suggests how useful it can be to posit general recipes for hardness like the low degree conjecture of Hopkins [Hop18] even when the conjecture is subject to attacks [BHJK25]. We believe that adopting this wider “win-win” perspective, already implicitly advocated by [ABW10], is crucial to developing deeper and more diverse algorithmic foundations for cryptography.

1.1

Large Alphabet Random Predicate CSPs

In this subsection we discuss our large alphabet random predicate CSPs, and present several lower bounds. We start with a few basic definitions (see Section 2 for details). An (m, n, k)-matrix is a matrix H ∈ Fm×n 2 such that each row has exactly k nonzero entries. We say that such a matrix is a (γ, t)-expander if for every row-induced submatrix H′ containing t′ rows with 1 ≤ t′ ≤ t, there are at least γkt′ distinct columns containing a nonzero entry of H′ . For values of γ close to 1, this means that every subset of at most t rows has nearly all of its nonzero entries lying in distinct columns, i.e. we have strong boundary expansion. We use NH (i, j) to denote the column index of the jth nonzero entry in the ith row of H. Below we give our hardness conjecture for large alphabet random predicate CSPs. See Section 3 Conjecture 3.1 for a slightly more general form. Conjecture 1.1 (High Corruption LARP-CSP Conjecture). Let H be any (1 − o(1), n1−o(1) )-expanding (m, n, k)-matrix,4 where k = (log n)Θ(1) and m ≤ no(k) , and let α(n) be any function that grows as Θ(1) 1 − o(1). Let Σ, Γ be any alphabets satisfying |Σ| = (nm)log (nm) and |Γ| ≤ |Σ|3k/4 . Sample m random functions fi : Σk → Γ, and let F be the set of all fi .5 Then no poly(|Σ|k ) size algorithm can distinguish, with advantage more than 1/4, between the following two distributions. 1. Null distribution: (H, F, b), where b ∈ Γm is sampled at random. 2. Planted distribution: (H, F, b), where b ∈ Γm is sampled by picking s ∈ Σn at random and setting ® bi =

Random element of Γ, fi (sNH (i,1) , . . . , sNH (i,k) ),

with probability α = 1 − o(1). otherwise.

In other words, the conjecture states that for any highly expanding matrix H, if we sample constraints defined by pairs (fi , bi ) conditioned on obeying a planted assignment, but then corrupt each constraint with 4 For our PKE scheme to be secure, we only need this conjecture to hold for a specific distribution over expanders. We state the conjecture in a more general form to encourage algorithmic research. 5 Technically, our “predicate functions fi ” do not fit the definition of a predicate, because they have non-binary output. But they can be re-phrased in terms of a predicate fi′ by setting fi′ (σ1 , . . . , σk ) = 1 if and only if fi (σ1 , . . . , σk ) = bi . The problem is now to determine if there exists an assignment s ∈ Σn such that approximately a 1 − α fraction of the predicates evaluate to 1.

probability 1 − o(1), the result is indistinguishable from a set of random constraints, for distinguishers of size polynomial in the description of the random functions fi . Note that the domain for each fi will in fact be super-polynomially larger than the size of the factor graph. So the entropy contribution of a single totally random constraint (fi , bi ) is super-polynomially larger than the entropy contribution that would have been present if the entire factor graph had been chosen at random. Observe that Conjecture 1.1 is closely related to Goldreich’s pseudorandom generator (Goldreich’s PRG) [Gol00]. The main differences are that in Goldreich’s PRG the seed s is a Boolean vector, and there is no corruption of the output vector b. We show in Section 6.2 that Conjecture 1.1 can also be viewed in terms of a planted hypergraph problem, where the observed hypergraph is defined over the vertex set [n] × Σ, and we add an edge of arity k to represent for each i ∈ [m] the preimages of bi for the function fi . There are a few papers which explicitly make use of hardness assumptions where the problem is defined over an arbitrary, non-random expanding matrix/hypergraph, albeit in the setting of polynomial stretch. To give a non-exhaustive summary, 1. Applebaum and Raykov ([AR16], Assumption 1) used the existence of local pseudorandom generators with arbitrary expanding factor graphs to get highly efficient constructions of pseudorandom functions. Their assumption remains unbroken in part because of their choice of predicate. 2. Ghosal, Hair, Jain, and Sahai ([GHJS25], Conjecture 1.3) used the assumed hardness of noisy kLIN over arbitrary expanding factor graphs to help build public key encryption from the planted clique conjecture. Their assumption sidesteps known attacks in part because each coefficient of each linear predicate is chosen at random, which injects some extrinsic entropy into the problem. 3. Elimelech and Huleihel [EH25] explore statistical-computational gaps for a variety of planted detection problems, with one of their contributions being a set of lower bounds for detecting arbitrary planted structures in random graphs. 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. Low Complexity Embedding Attacks. Oliveira, Santahnam, and Tell showed that in the setting of quasipolynomial stretch, Goldreich’s PRG is broken when instantiated with a very carefully chosen expanding factor graph [OST18]. Could similar attacks impact Conjecture 1.1? In Section 6.1, we define the notion of a low complexity embedding attack, which captures and generalizes the Oliveira-Santhanam-Tell attacks. Then we show that the entropy of the random functions alone is enough for the decision problem in Conjecture 1.1 to unconditionally resist attacks of this form, even in the errorless regime. As far as are aware, ours is the first formalization of any lower bound against this family of attacks. The Oliveira-Santhanam-Tell family of attacks works as follows. First exhibit a specific expanding matrix H and a specific predicate f such that both are described by a small AC0 [+] circuit. Then no matter the choice of seed, the output b of Goldreich’s PRG when instantiated with H and f will be the truth table of a small AC0 [+] circuit. Using natural property algorithms (see e.g. [Raz87, Smo87, RR94, CIKK16]) we can distinguish such a vector b from a random vector, with at least constant advantage. Another way to view the attacks is as follows. Let L be the set of all truth tables for small AC0 [+] circuits. The distinguisher works by simply measuring the Hamming distance from an observed vector b to the closest member of L and returning “planted” or “null” based on whether the distance is small or large, respectively. In the context of the LARP-CSP Conjecture, we generalize this attack in several ways, the most important of which are:

• We allow the adversary to pick any expanding matrix H along with any subset L against which to compute the distance, with the only requirement being that L is fixed before the functions in F are fixed (without this requirement every assumption would be broken). • We allow the adversary to define any coordinate-wise embeddings that will be applied to an observed vector b before measuring its distance to the closest member of L. Critically, the adversary is allowed to choose the coordinate-wise embeddings after gaining knowledge of the functions in F. 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. Low Degree Polynomial Algorithms. Many efficient algorithms for planted detection problems can be represented in terms of a low degree polynomial over the reals. In fact, low degree polynomials give the best known algorithms for planted clique, sparse PCA, community detection, p-spin optimization, and many versions of the planted constraint satisfaction problem [KWB19]. 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). Recent papers [FGR+ 17, BBH+ 20] suggest a nearly tight correspondence between lower bounds against low degree polynomial algorithms and against statistical query algorithms. Under the Pseudocalibration Conjecture ([HKP+ 17] Conjecture 1.2), lower bounds against low degree polynomial algorithms for certain “well behaved” hypothesis testing problems imply lower bounds against sum-of-squares algorithms with comparable degree. For these reasons, proving lower bounds against low degree polynomials is commonly used to support computational hardness conjectures for problems in average case complexity [BKW19, Kun21, BBK+ 21, Wei22, Wei23, DDL23, KVWX23, YZZ24, LG24, MW25] and cryptography [BKR23, BJRZ24]. In Section 6.2 Theorem 6.8, we rule out degree-n0.99 polynomial algorithms for the problem in the 0.99 polynomials are LARP-CSP Conjecture, even in its corruption-free form. In many ways degree-≤ ¶ © n O(1) 0.99 a proxy for “combinatorial” algorithms that run in time exp n / log n [KWB19], so if degree0.99 ≤ n¶ polynomials©are ineffective for the hypothesis testing problem this gives strong evidence that exp n0.99 / logO(1) n time “combinatorial” algorithms are also ineffective. Denoting by λ the running ¶ © Ω(1) λ . time of the algorithms in our PKE scheme, the lower bound becomes exp 2log Polynomial Calculus Refutations. The polynomial calculus proof system was introduced by Clegg, Edmonds, and Impagliazzo as one way to formalize linear-algebraic algorithms such as Gaussian elimination and basic Gröbner basis computations6 [CEI96]. The ability to model these linear-algebraic algorithms makes polynomial calculus a very different algorithmic framework from e.g. low degree polynomial algorithms, sum-of-squares algorithms, and statistical query algorithms. Lower bounds against polynomial calculus refutations have been used to suggest hardness for various CSPs including Goldreich’s PRG and random SAT instances [BSI99, IPS99, Nor14, AL16, MN24]. For the corruption-free version of the problem in the LARP-CSP Conjecture, the adversary is given a tuple (H, F, b), and the goal is to certify that there does not exist a secret vector s ∈ Σn such that bi = fi (sNH (i,1) , . . . , sNH (i,k) ) for all i ∈ [m], i.e. the system is unsatisfiable. The first step is to initialize a system of polynomials over a finite field (typically F2 ) that encode for all i ∈ [m] the equation bi = 6

In fact, Clegg, Edmonds, and Impagliazzo referred to the polynomial calculus proof system as the “Gröbner proof system.”

fi (sNH (i,1) , . . . , sNH (i,k) ). Then the adversary chooses any sequence of derivations that are permitted by the polynomial calculus proof system. The goal is to derive the equation 1 = 0, which is only possible if the starting system was unsatisfiable. Using this approach we get a distinguisher with one-sided error, because the adversary can return “null distribution” if the refutation is successful and otherwise return “unsure.” This type of one-sided error is present in other common frameworks such as the sum of squares hierarchy. In Section 6.3 Theorem 6.13, we show that unsatisfiable (H, F, b) tuples do not have polynomial 0.99 calculus refutations over F2 of size less than exp n , which translates into a size lower bound of ¶ © Ω(1) log λ exp 2 . This holds even when the adversary is permitted unbounded time to choose the best embedding from Σ to a vector over F2 for each variable representing the vector s. Our proof techniques are inspired by a work of Applebaum and Lovett [AL16], in which they prove similar lower bounds for Goldreich’s PRG.

1.2

Random kXOR

Below we give our hardness conjecture for random kXOR. A slightly more general form is stated in Section 3 as Conjecture 3.2. Conjecture 1.2 (High Corruption Random kXOR Conjecture). Let H be a random (m, n, k)-matrix, where k = (log n)Θ(1) and m ≤ nk/3 , and let β(n) be any function that grows as 1 − o(1). Then no poly(m) size algorithm can distinguish, with advantage more than 1/4, between the following two distributions. 1. Null distribution: (H, b), where b ∈ Fm 2 is sampled at random. n 2. Planted distribution: (H, b), where b ∈ Fm 2 is sampled by picking s ∈ F2 at random and setting

® Random element of F2 , with probability β = 1 − o(1). bi = sNH (i,1) + . . . + sNH (i,k) , otherwise. Constant-corruption kXOR is a classic problem in learning theory for all choices of m, e.g. m = ¶ © O(1) n , and m = exp nO(1) [FGKP06, Val12, CSZ24], and it is widely believed to be nO(1) , m = nlog ¶ © computationally intractable for exp n1−Ω(1) size adversaries. For perspective, the best known algorithms for the related constant-noise LPN problem (which is just kXOR but where the rows of H are dense random vectors) run in barely subexponential time: Blum, Kalai, and Wasserman gave an algorithm running in time 2O(n/ log n) when m = 2Ω(n/ log n) [BKW03], and Lyubashevsky gave an algorithm running in time 2O(n/ log log n) when m = n1+ε [Lyu05]. Lower Bounds for the High Corruption Random kXOR Conjecture. Applebaum, Barak, and Wigderson [ABW10] showed that whenever the matrix H is chosen at random and is of height n(1/2−Ω(1))k (which is the case for our problem), smallest subset of coordinates of b that have any bias towards zero will be ¶ theΩ(1) © λ . This means that the problem in Conjecture 1.2 fools all local algoof size t = nΩ(1) = exp 2log rithms and linear tests. They¶also point out that we can apply a result of Braverman [Bra08] to show that © any AC 0 circuit of size exp no(1) has distinguishing advantage o(1) for the problem in Conjecture 1.2. ¶ © Ω(1) λ on the size of any AC0 [+] circuit with non-vanishing This translates into a lower bound of exp 2log distinguishing advantage. Grigoriev [Gri01], Schoenebeck [Sch08], and Kothari, Mori, O’Donnell, and Witmer [KMOW17] gave successively stronger/more general sum-of-squares lower bounds for CSPs, including random kXOR as an important special case. In our setting, these results show that any sum of squares algorithm for the problem 6

Ω(1) . These algorithms run in in Conjecture ¶ © 1.2 with ¶ constant © distinguishing advantage must have degree n Ω(1) λ time. exp nΩ(1) = exp 2log Wein, El Alaoui, and Moore [WEAM19] gave a unified framework for analyzing belief propagation and approximate message passing algorithms from statistical physics, showing that these algorithms encounter the same barrier as sum-of-squares when applied to random kXOR. As such these results imply that any belief propagation/approximate message passing algorithm that ¶ © has constant distinguishing advantage for Ω(1) λ . Feldman, Perkins, and Vempala [FPV15] the problem in Conjecture 1.2 must run in time exp 2log gave lower bounds for a powerful class of statistical query algorithms that also matches this lower bound.

1.3

Our Results and Techniques

Our main result is to construct a semantically secure public key encryption scheme from CSPs with a corruption rate of 1 − o(1). We prove the following theorem in Section 5.3. Theorem 1.3. Suppose that Conjecture 1.1 (High Corruption LARP-CSP) and Conjecture 1.2 (High Corruption kXOR) both hold. Then there is a semantically secure public key encryption scheme. At the heart of our result is a technique which generically allows us to construct a PKE scheme from a certain type of linear error correcting code that can handle a large fraction of erasures and corruptions. We now give an informal definition of the code; for a formal version see Definition 4.1. Note that all vectors are column vectors unless stated otherwise. Definition 1.4 ((α, β)-Decodable Expanding Code (Informal)). An (α, β)-Decodable Expanding Code is a tuple (MatrixGen, Distinguish, α, β) where MatrixGen and Distinguish are algorithms, α is an erasure rate parameter, and β is a corruption rate parameter. We require that • MatrixGen outputs a generator matrix G for a linear code. We require that G is a (1−o(1), n1−o(1) )expanding (m, n, k)-matrix, where k = logΘ(1) n and m = no(k) . • The algorithm Distinguish7 can differentiate between – Random vectors in Fm 2 where each entry is erased with probability α. – Noisy codewords c′ , where c′ is sampled by taking a random codeword c ∈ {Gx : x ∈ Fn2 }, 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.7 later in this subsection. In Section 4.4 we use such a code to build a PKE scheme (see Theorem 4.13). Theorem 1.5 (Informal). Suppose we have an (α, β)-decodable expanding code. Then assuming Conjecture 1.1 (High Corruption LARP-CSP) holds with corruption rate α, and Conjecture 3.2 (High Corruption kXOR) holds with corruption rate β, there is a semantically secure PKE scheme. Notice that the erasure rate α from the (α, β)-decodable expanding code becomes the corruption rate for the LARP-CSP. The above theorem in fact holds for all choices of α and β, but for our scheme we always assume α = 1 − o(1) and β = 1 − o(1). 7 We only need a distinguisher, as opposed to a decoder. It’s simple to convert from a decoder to a distinguisher, as we explain later in the paper.

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. Below, we give an informal version of the starting PKE scheme; to ensure clarity, some important technical details are omitted. Key Generation 1. Sample a (1 − o(1), n1−o(1) )-expanding (m, n, k)-matrix G using the algorithm MatrixGen. Let Σ be a sufficiently large alphabet, and let Γ be another alphabet of size |Γ| = |Σ|3k/4 .

An example matrix G where m = 5, n = 4, and k = 2. For an actual instantiation of the PKE scheme, all these parameters would of course be significantly larger.

2. Sample random functions f1 , . . . , fm and b from the planted distribution in the High Corruption LARP-CSP Conjecture. That is, we sample a set of random functions F = {fi : Σk → Γ}i∈[m] and a secret s ∈ Σn , then set ® Random element of Γ, with probability α = 1 − o(1). bi = fi (sNG (i,1) , . . . , sNG (i,k) ), otherwise.

b1 =f1 (s1 , s3 ) = f1 (4, 5) b2 = random b3 =f3 (s3 , s4 ) = f3 (5, 7) b4 =f4 (s1 , s2 ) = f4 (4, 2) b5 =f5 (s1 , s4 ) = f5 (4, 7)

Assume we set Σ = {1, . . . , 8} and that s = (4, 2, 5, 7). Every coordinate of b will equal the corresponding function evaluation, except with probability α. The parameter α is supposed to be close to 1, but for this example we take α ≈ 1/5.

3. The public key will be a (m′ ≤ |Σ|k/3 , |Σ|, k)-matrix H defined as follows. For all i ∈ [m] and for all tuples (σ1 , . . . , σk ) ∈ Σk such that fi (σ1 , . . . , σk ) = bi , append the length-|Σ| indicator vector for the tuple (σ1 , . . . , σk ) as a new row in H. Define H to have m′ rows and n′ columns. Notice that when producing H, we ignore all structure coming from the original matrix G. So if we instead sampled b at random, H would be a truly random matrix; this is useful for proving security.

An example matrix H produced using the matrix G from above. We assume that every equation bi = fi (σ1 , σ2 ) has exactly two solutions. For an actual instantiation of the PKE scheme, the number of solutions is approximately |Σ|k /|Γ| = |Σ|k/4 for each constraint.

4. By construction of H, a row-induced column-permuted submatrix G′ of G will appear within H, where G′ is formed by deleting each row of G independently with probability α. The secret key will be a mapping ζ which records the location of G′ in H. Put differently, we know that there exists a subset of the rows of H which generate a punctured version of the original code {Gx : x ∈ Fn2 }, and ζ allows us to identify (in the correct order) the coordinates which correspond to this punctured version. An annotated version of the matrix H. Every row that came from a corrupted constraint pair (bi , fi ) is marked in red, every row that represents a solution to bi = fi (sNG (i,1) , sNG (i,2) ) is marked in blue, and all other rows are marked in gray. The column-permuted submatrix G′ is marked in light and dark blue. Note that within this light/dark blue submatrix, the order of the columns from G is now: (2nd, 1st, 3rd, 4th), and the second row of G was deleted.

Encryption ′

1. To encrypt a bit b = 0, sample a ciphertext v ∈ Fm 2 as in the planted distribution in′ the High ′ n Corruption kXOR Conjecture. That is, sample t ∈ F2 at random and then sample v ∈ Fm 2 as ® vi =

Random element of F2 , with probability β = 1 − o(1). tNH (i,1) + . . . + tNH (i,k) , otherwise. ′

2. To encrypt a bit b = 1, sample a ciphertext v ∈ Fm 2 as in the null distribution in the High Corruption kXOR Conjecture, i.e. sample v at random. Decryption 1. Use the secret key ζ to extract a subvector w ∈ {F2 ∪ “?”}m of the ciphertext v, where “?” is a special erasure symbol. If we encrypted a bit b = 0, then w should be a codeword from {Gx : x ∈ Fn2 }, but where each entry is erased (i.e. replaced with “?”) with probability α, and the remaining entries are corrupted with probability β. The erasure rate α comes from the probability that a row of G is deleted when constructing G′ . The corruption rate β comes from the corruption rate at encryption time.

Above, we give a worked example of setting up the decryption process (in the case of an encrypted bit b = 0) using the matrices G and H from key generation. The coordinates of v that are corrupted are marked in orange, and the coordinates of v corresponding to G are marked in blue. We extract a codeword w from v, which is shown on the right. The (known) erased coordinates are marked in red, and the (unknown) corrupted coordinates are marked in orange8 . 2. Run algorithm Distinguish on w, and determine the encrypted bit based on the result. Intuitively speaking, decryption is possible because both the matrix G and the predicate wi = xNG (i,1) + . . . + xNG (i,k) are of “low complexity,” so we can distinguish noisy vectors w from totally random vectors. In the proof of security, however, we show that an adversary must either solve a CSP where the predicates are of maximum complexity (i.e. break the High Corruption LARP-CSP Conjecture), or where the factor graph is of maximum complexity (i.e. break the High Corruption kXOR Conjecture). Remark 1.6. Applebaum [App12] used an algorithm similar to our key generation algorithm to show hardness of approximation for the densest k-subhypergraph problem, assuming hardness of Goldreich’s PRG. One important difference is that Applebaum constructed the hypergraph instance by sub-sampling local preimages for a (collection of) Goldreich instances, while we construct the public key H by listing all local pre-images for a LARP-CSP instance. This distinction is one key factor that ensures correctness of our decryption algorithm. Instantiating an (α = 1 − o(1), β = 1 − o(1))-Decodable Expanding Code. In Section 5.1 we give an explicit randomized algorithm for MatrixGen that outputs a (1 − o(1), n1−o(1) )-expanding (m, n, k)-matrix G that generates a subcode of a sufficiently low-rate Reed-Muller code: Theorem 1.7. There is an explicit randomized algorithm Kck ,cm (1n ) parameterized by two constants ck , cm cm satisfying cm ≥ 2 and ck ≥ cm + 1, that runs in time 2O((log n) ) and outputs a matrix G, such that: cm

1. G is an (m, n, k)-matrix, where m = 2(⌈log n⌉)

and k = (⌈log n⌉)ck .

2. The code {Gx : x ∈ Fn2 } is a subcode of the Reed-Muller code RM((⌈log n⌉)cm , (⌈log n⌉)2 ). 3. With 1 − o(1) probability over the coins of Kck ,cm , G is (1 − o(1), n1−o(1) )-expanding. Remark 1.8. The running time can also be written as mO(1) , where m is the height of the output matrix G. In fact the running time will be dominated by the time required to write the output G. The above theorem improves upon the expander graphs constructed by Oliveira, Santhanam, and Tell [OST18] in the following ways: First and foremost, our construction is given by an explicit uniform algorithm, whereas Oliveira, Santhanam, and Tell were only able to prove the existence of expander graphs that suit their needs. Our algorithm is also quite simple, whereas the construction of Oliveira, Santhanam, and Tell relies on machinery related to the Nisan-Wigderson pseudorandom generator [NW94]. We leverage an algorithm of Saptharishi, Shpilka, and Volk [SSV16] to make the algorithm Distinguish. Their results shows that any Reed-Muller code of sufficiently low rate can be decoded from a 1 − o(1) fraction of errors, which after some massaging implies a distinguisher in the sense required for our code. Remember that by Theorem 1.5 this (1−o(1), 1−o(1))-decodable expanding code immediately implies a PKE scheme from 1 − o(1) corruption CSPs, from which we deduce Theorem 1.3. 8

Note that, of course, it would be impossible to distinguish w from random in the drawn example, because with only 3 non-corrupted coordinates in w that depend on 3 random inputs in x, in fact all non-erased coordinates of our drawn w will be distributed totally randomly. In an actual decryption instance, the number of non-corrupted coordinates of w will far exceed the dimension of x, since the code G is of vanishing rate.

1.4

Discussion

In this work we present a radically different approach for building public key encryption, motivated by a desire to explore and understand what kinds of hardness conjectures can be used to (explicitly) build publickey encryption. We believe that algorithmic research on LARP-CSPs will be fruitful for the algorithms and complexity communities, because of its connections to cryptography, Goldreich’s PRG, and planted hypergraph problems. Related Public Key Encryption Schemes. Our public-key encryption scheme, especially the way that we plant a trapdoor, is very notably different from all previous public-key encryption schemes. The closest relatives to our scheme appear to be those given in [ABW10, BKR23, GHJS25]. In our paper and all of these papers, there is a similar 2-phase construction that combines a planting assumption at key generation with a planting assumption at encryption time. But the similarities stop here, since our key generation and decryption algorithms make critical use of a novel error correcting code introduced in this paper. We note that the McEliece cryptosystem [McE78] and its relatives do make critical use of a hidden error correcting code. But unlike in the McEliece-type cryptosystems, we have a concrete and natural hardness conjecture related to the average-case hardness of CSPs (the LARP-CSP Conjecture) which allows us to argue that our error correcting code can be hidden, and indeed hidden within the generator matrix of a random linear code. Open Questions. Our work opens several new lines of research with respect to algorithm design, lower bounds, and coding theory. We believe that the following questions are of highest priority: 1. Can we further populate the list of computational lower bounds for LARP-CSPs? What are the parameter regimes in which LARP-CSPs appear to be computationally intractable? 2. Is there a unified framework which captures the known attacks on Goldreich’s PRG? In this paper we give the first framework which captures the attacks of Oliveira, Santhanam, and Tell [OST18], but we believe that significantly more research is warranted. 3. Does there exist a (1 − o(1), 1 − o(1))-decodable expanding code in the polynomial stretch regime? If so, this would imply a PKE scheme with plausibly subexponential security via Theorem 1.5. 4. What is the minimal level of mathematical structure required to build PKE solely from the hardness of 1 − o(1) corruption CSPs? 5. Is it possible to build public-key encryption solely from unstructured hardness conjectures like our LARP-CSP conjecture?

Preliminaries

We use [n] to denote the set {1, . . . , n}. All vectors are column vectors unless stated otherwise. The phrase “sample at random” is shorthand for “sample uniformly at random.” Binom(n, p) is the binomial distribution with n trials and success probability p. For a field F and two vectors b, v ∈ Fm , we use dist(b, v) to denote the number of coordinates on which b and v differ. For a vector b ∈ Fm and a subset L ⊂ Fm , we use dist(b, L) to denote the minimum over all v ∈ L of dist(b, v). All logarithms are taken base 2.

Erasures and Corruptions. We use the term “subjected to erasures of rate α” to refer to the random process which replaces each entry of a given vector with an erasure symbol “?”, independently with probability α. For binary vectors, this is equivalent to transmission over the binary erasure channel (BEC) with erasure rate α. We use the term “subjected to corruptions of rate β” to refer to the random process which replaces each entry of a given vector with a random value, independently with probability β. For binary vectors, this is equivalent to transmission over the binary symmetric channel (BSC) with error rate β2 . The reason for this discrepancy is that the BSC error rate is actually the bit flip probability. Just as a corruption rate of 1 replaces the entire vector with noise, a BSC with error rate 1/2 replaces the entire vector with noise. The reason we use “corruption rate” is that it generalizes directly to non-binary alphabets. Matrices and Expanders. For a vector v ∈ Fn2 , let hw(v) be its Hamming weight, i.e. the number of nonzero entries. For a W matrix M ∈ Fm×n , let Mi ∈ Fn2 be the row of M indexed by i. For vectors 2 v1 , . . . vt ∈ Fn2 , we use i∈t vi to denote their component-wise logical-OR. We now give some definitions related to sparse matrices and their expansion properties. where each row has exactly Definition 2.1 ((m, n, k)-Matrix). An (m, n, k)-matrix is a matrix M ∈ Fm×n 2 k nonzero entries, i.e. hw(Mi ) = k for all i ∈ [m]. Definition 2.2 (Neighbor Function NM (i, j)). For a matrix M ∈ Fm×n , we use NM (i, j) to denote the 2 column index of the jth nonzero entry of Mi . Now we define what it means for a matrix over F2 to be an expander.9 is a (γ, t)-expander if and only if, for all subsets Definition 2.3 ((γ, t)-Expander). A matrix M ∈ Fm×n 2 S ⊆ [m] with 1 ≤ |S| ≤ t, ! _ X hw Mi ≥ γ · hw(Mi ). i∈S

i∈S

If M is an (m, n, k)-matrix, this definition is equivalent to ! _ hw Mi ≥ γk|S|. i∈S

2.1

Public Key Encryption

We start with a definition that captures public key encryption (PKE) schemes which are only “mildly” correct and “mildly” secure. Definition 2.4 (See Definition 8 in [HR05]). A (κ(λ), η(λ))-secure public key encryption scheme is a triple of probabilistic polynomial time algorithms (KeyGen, Enc, Dec) such that 1. KeyGen(1λ ) outputs a pair of strings (pk, sk). 2. Enc(1λ , pk, b ∈ {0, 1}) outputs a string ct. 3. Dec(1λ , sk, ct) outputs a bit b′ ∈ {0, 1}.

This definition is agnostic to the number of nonzero entries in each row, but we will only apply it to (m, n, k)-matrices.

4. (κ(λ)-correctness) For a random bit b ∈ {0, 1}, î ó 1 + κ(λ) Pr (pk, sk) ← KeyGen(1λ ); Dec(1λ , sk, Enc(1λ , pk, b)) = b > , 2 where the probability is taken over the internal coins of KeyGen, Enc, and Dec. 5. (η(λ)-security) For all poly(λ) size non-uniform algorithms A, for a random bit b ∈ {0, 1}, î ó 1 + η(λ) Pr (pk, sk) ← KeyGen(1λ ); A(pk, Enc(1λ , pk, b)) = b < , 2 where the probability is taken over the internal coins of KeyGen, Enc, and Dec. Remark 2.5. Item 5 is equivalent to bounding the advantage of an algorithm as follows:10 For all poly(λ) size non-uniform algorithms A, î ó Pr (pk, sk) ← KeyGen(1λ ); A(pk, Enc(1λ , pk, 1)) = 1 î ó − Pr (pk, sk) ← KeyGen(1λ ); A(pk, Enc(1λ , pk, 0)) = 1 < η(λ). PKE schemes satisfying the standard notion of correctness and security can be defined as follows. Definition 2.6 (Based on [GM84]). A semantically secure public key encryption scheme is a triple of probabilistic polynomial time algorithms (KeyGen, Enc, Dec) such that for all 1 − κ = η ≥ λ−O(1) , (KeyGen, Enc, Dec) is a (κ, η)-secure public key encryption scheme. We make critical use of a theorem by Holenstein and Renner which allows us to amplify from a (κ, η)secure PKE scheme to a standard PKE scheme, assuming κ is sufficiently large with respect to η. Theorem 2.7 (See Theorem 6 in [HR05]). Let κ, η be any constants satisfying κ2 > η. Then there is a black box reduction from any (κ, η)-secure public key encryption scheme to a semantically secure public key encryption scheme.

2.2

Coding Theory

The minimum distance of a code is the number of nonzero entries in a minimum-weight nonzero codeword. The dual of a code C is the code consisting of all vectors c′ such that, for all c ∈ C, the inner product < c′ , c > satisfies < c′ , c >= 0. The dual to a linear code is always a linear code. P d d := ri=0 ≤r . M(d, r) denotes the set of all monomials of degree ≤r d at most r over d variables in F2 . Observe that |M(d, r)| = ≤r , because we always include the constant

Reed-Muller Codes.

We define

monomial “1” in M(d, r). We consider each monomial M ∈ M(d, r) as a function, so that we can write M (p) to denote the evaluation of M on a given point p ∈ Fd2 . Definition 2.8 (Reed-Muller (RM) Code [Ree53, Mul54]). The Reed-Muller code RM(d, r) is a linear code consisting of the length-2d evaluation vectors for all polynomials of degree at most r over Fd2 .

The proof is folklore and uses elementary linear algebraic manipulations.

2d ×( d ) Equivalently, we can define the RM code using an “evaluation matrix” E ∈ F2 ≤r . Each row of E is indexed by a different point p ∈ Fd2 , each column is indexed by a distinct monomial M ∈ M(d, r), and we set Ep,M = M (p). Now we can write

(d) RM(d, r) = {Ex : x ∈ F2≤r }, where x is can be interpreted as the coefficient vector for a degree ≤ r polynomial. We need the following basic lemmas, both of which are well known. Lemma 2.9 (See e.g. [ASY20]). The minimum distance of RM(d, r) is 2d−r . Lemma 2.10 (See e.g. [ASY20]). The dual code to RM(d, r) is RM(d, d − r − 1). Saptharishi, Shpilka, and Volk showed that Reed-Muller codes of sufficiently low rate can be decoded from a 1 − o(1) fraction of random corruptions. Theorem 2.11 (Special case of Corollary 14 in [SSV16]). There is a function γ(d) ≥ 1 − o(1), γ(d) ≤ 1 − d−O(1) and a poly(2d ) time algorithm D that outputs a vector in RM(d, d1/3 ) and behaves as follows. Pick a random codeword c ∈ RM(d, d1/3 ), and sample a noisy version c′ of c: c′i =

Random element of F2 , ci ,

with probability γ(d). otherwise.

Then Pr D(c′ ) = c ≥ 1 − o(1). Remark 2.12. Technically speaking, Corollary 14 in [SSV16] is for a fixed number of random errors. But as pointed out by the authors, results for a fixed number of errors translate to the Bernoulli error case with vanishing parameter loss. (For a discussion of this phenomenon, see [ASW15].) The Bernoulli error case is then equivalent to our corruption model after rescaling parameters. Notational Guidance. Throughout the paper, we use slightly non-standard notation for our codes; for example, we denote the Reed-Muller code as RM(d, r) instead of RM(m, r), we use n for the code dimension, and we use m for the block length. This is so that we can refer to our cryptographic subproblems as involving “m × n” matrices. In general we will default to cryptographic notation.

Our Conjectures

We build a public key encryption scheme whose security is implied by the following conjectures when instantiated with corruption rates of α = 1−o(1) and β = 1−o(1). Recall from Section 1.1 and¶Section © 1.2 o(1) that we have a variety of lower bounds suggesting the conjectures in fact hold against all exp n size adversaries. See the introduction for a more detailed discussion. Conjecture 3.1 (LARP-CSP(α) Conjecture). Let H be any (1 − o(1), n1−o(1) )-expanding (m, n, k)-matrix, Θ(1) where k = (log n)Θ(1) and m ≤ no(k) . Let Σ, Γ be any alphabets satisfying |Σ| = (nm)log (nm) and |Γ| ≤ |Σ|3k/4 . Sample m random functions fi : Σk → Γ, and let F be the set of all fi . Then no poly(|Σ|k ) size algorithm can distinguish, with advantage more than 1/4, between the following two distributions. 1. (H, F, b), where b ∈ Γm is sampled at random. 14

2. (H, F, b), where b ∈ Γm is sampled as follows. Sample s ∈ Σn at random and set ® Random element of Γ, bi = fi (sNH (i,1) , . . . , sNH (i,k) ),

with probability α. otherwise.

Conjecture 3.2 (kXOR(β) Conjecture). Let H be a random (m, n, k)-matrix, where k = (log n)Θ(1) and m ≤ nk/3 . Then no poly(m) size algorithm can distinguish, with advantage more than 1/4, between the following two distributions. 1. (H, b), where b ∈ Fm 2 is sampled at random. n 2. (H, b), where b ∈ Fm 2 is sampled as follows. Sample s ∈ F2 at random and set

® Random element of F2 , with probability β. bi = sNH (i,1) + . . . + sNH (i,k) , otherwise.

From Decodable Expanding Codes to PKE

4.1

The General Framework

We first define an (α, β)-decodable expanding code, which consists of a code generation algorithm MatrixGen and a distinguishing algorithm Distinguish. The name comes from the fact that the error correcting code will have a low density generator matrix (LDGM), and additionally this generator matrix will be strongly expanding. Intuitively, we mandate that Distinguish can differentiate between (i) random vectors subjected to erasures of rate α, and (ii) codewords subjected to erasures of rate α and corruptions (on the non-erased coordinates) of rate β. Definition 4.1 ((α, β)-Decodable Expanding Code). 11 A tuple (MatrixGen, Distinguish, α, β), where MatrixGen and Distinguish are algorithms, and α and β are parameters. The code generation algorithm MatrixGen has the following properties: 1. MatrixGen(1m ) runs in mO(1) time and outputs an (m, n, k)-matrix G, where k = logΘ(1) m and n satisfies m = no(k) . We interpret G as the generator matrix for a linear code over F2 . 2. With 1 − o(1) probability over the coins of MatrixGen(1n ), G is a (1 − o(1), n1−o(1) )-expander. The distinguishing algorithm Distinguish has the following properties: 1. Distinguish(1m , G, w) takes as input an (m, n, k)-matrix G produced by MatrixGen along with a vector w ∈ {F2 ∪ “?”}m , runs in time mO(1) , and outputs a bit b ∈ {0, 1}. 2. Pick a random codeword c ∈ {Gx : x ∈ Fn2 }, and sample a noisy version c′ ∈ {F2 ∪ “?”}m of c:   “?”, ′ ci = Random element of F2 ,   ci , 11

with probability α. with probability (1 − α)β. otherwise.

As mentioned in the introduction, we actually only need a distinguisher, which is simple to construct when given a decoder.

Also sample a random vector r ∈ {F2 ∪ “?”}m : ® “?”, ri = Random element of F2 ,

with probability α. otherwise.

Then Pr Distinguish(1n , G, c′ ) = 0 ≥ 1 − o(1)

and

Pr[Distinguish(1n , G, r) = 1] ≥ 1 − o(1),

where the probability ranges over the choice of G, c′ , and r, as well as the coins of Distinguish.

Given any (α, β)-decodable expanding code with internal parameters m, n, k, we define a public key enΘ(1) cryption scheme as follows. Fix two alphabets Σ, Γ satisfying |Σ| = (nm)log (nm) and |Γ| = |Σ|3k/4 . The security parameter λ is set to the maximum of |Σ|k , the running time of MatrixGen, and the running time of Distinguish. It will be clear from the exposition that all algorithms run in time |Σ|O(k) , so λ = |Σ|O(k) . Remark 4.2. Strictly speaking, we would like to instantiate the PKE scheme by choosing λ first and then setting the other parameters. Because the relationship between n, m, k, |Σ|, |Γ|, and λ is well defined, we can simply fix a target value λ∗ and then calculate values for the parameters so that the actual security parameter λ is within a small slack factor of the target λ∗ . Notice that n, m, |Σ|, and |Γ| will all be of the c form 2log λ for different constants c > 0, and k will be of the form logΘ(1) λ.

Key Generation. (pk, sk) ← KeyGen(1λ ): 1. G ← MatrixGen(1m ). 2. Sample functions f1 , . . . , fm : Σk → Γ at random. 3. Sample b ∈ Γm as follows. Sample s ∈ Σn at random, and set ® Random element of Γ, with probability α. bi = fi (sNG (i,1) , . . . , sNG (i,k) ), otherwise. 4. Define the set ¶ © X := (σ1 , . . . , σk ) ∈ Σk : there exists i ∈ [m] such that fi (σ1 , . . . , σk ) = bi . 5. Delete all tuples from X that contain two or more copies of the same symbol. 6. If at least one of the following holds, output (pk, sk) := (⊥, ⊥) and abort. (a) There exist indices i, j ∈ [n] with i ̸= j such that si = sj . (b) |X | > |Σ|k/3 . |X |×|Σ|

7. Define H ∈ F2

as follows.

(a) Label each column by a distinct σ ∈ Σ.

(b) Label each row by a distinct (σ1 , . . . , σk ) ∈ X . (c) Set H((σ1 ,...,σk ),σ) = 1 if and only if σ equals one of σ1 , . . . , σk . 8. Modify H as follows. (a) Append random rows with exactly k nonzero entries, until the height of H is exactly |Σ|k/3 . (b) Randomly permute the rows of H. î ó 9. Define a function ζ : [m] → |Σ|k/3 ∪ “?” as follows. (a) If bi was not set to a random value in Step 3, then ζ(i) is set to the index of the row representing (sNG (i,1) , . . . , sNG (i,k) ) in H. Such a row is guaranteed to exist by Step 6a. (b) Otherwise, ζ(i) is set to ⊥. 10. Output (pk, sk) := (H, ζ). Encryption. ct ← Enc(1λ , pk, b ∈ {0, 1}): 1. If pk = ⊥, output ct := ⊥ and abort. ′

′

×n , where m′ = |Σ|k/3 and n′ = |Σ|. 2. Otherwise, parse pk as H ∈ Fm 2 ′

′

n 3. If b = 0, sample v ∈ Fm 2 as follows. Sample t ∈ F2 at random and set

® vi =

Random element of F2 , with probability β. tNH (i,1) + . . . + tNH (i,k) , otherwise. ′

4. If b = 1, then sample v ∈ Fm 2 at random. 5. Output ct := v. Decryption. b′ ← Dec(1λ , sk, ct): 1. If ct = ⊥, output b′ := ⊥ and abort. 2. Otherwise, parse ct as v and sk as ζ. 3. Define a vector w ∈ {F2 ∪ “?”}m as follows. (a) If ζ(i) ̸= ⊥, then wi = vζ(i) . (b) Otherwise, wi = “?”. 4. Output b′ := Distinguish(1m , G, w).

Now our plan in Sections 4.2 and 4.3 is to argue κ-correctness and η-security. In particular, we get a 17

(0.99, 0.9)-secure12 PKE scheme, assuming Conjecture 3.1 (LARP-CSP) holds with corruption parameter α and Conjecture 3.2 (kXOR) holds with corruption parameter β. This implies a semantically secure PKE scheme by applying Theorem 2.7. In Section 5 we give an explicit (1 − o(1), 1 − o(1))-decodable expanding code, along with the concrete PKE scheme it implies.

4.2

Correctness

In this subsection we show that b′ = b with sufficiently high probability. More precisely, we prove: Lemma 4.3 (Correctness). Let κ = 0.99,13 and assume λ is sufficiently large. For a random bit b ∈ {0, 1}, î ó 1+κ Pr (pk, sk) ← KeyGen(1λ ); Dec(1λ , sk, Enc(1λ , pk, b)) = b > , 2 where the probability is taken over the internal coins of KeyGen, Enc, and Dec. At its core, the proof is quite simple. The matrix H should contain a homomorphic copy of the original matrix G (but with a 1 − o(1) fraction of the rows deleted), and the secret function ζ describes where this homomorphic copy lies. Because encryption of a bit b = 0 amounts to computing a noisy linear sample using the matrix H, a small portion of the ciphertext will actually correspond to a noisy codeword from the linear code {Gx : x ∈ Fn2 }. The function ζ allows us to extract this noisy codeword, and from here the distinguishing algorithm for the code allows us to determine whether a bit b = 0 or a bit b = 1 was encrypted. Unfortunately, there are several technical details to handle, e.g. the failure conditions in the key generation algorithm. Proof of Lemma 4.3. We start by bounding the probability that KeyGen aborts, i.e. at least one of the two failure conditions in Step 6 is satisfied. Below we argue that it is unlikely for two symbols of the secret s ∈ Σn to be the same. Claim 4.4. The probability that there exists an index pair i, j ∈ [n] with i ̸= j such that si = sj is o(1). Proof. There are O(m2 ) pairs i, j, and the probability that a fixed pair collides is 1/|Σ|. A Markov bound shows that the probability of at least one collision occurring across all pairs is O(m2 |Σ|−1 ). Because m and |Σ| grow with λ, and |Σ| = mω(1) , this quantity is bounded as o(1). Now we argue that the set of tuples X is unlikely to be too large. Claim 4.5. The probability that |X | > |Σ|k/3 is o(1). Proof. Recall that we defined X by taking the set ¶ © (σ1 , . . . , σk ) ∈ Σk : there exists i ∈ [m] such that fi (σ1 , . . . , σk ) = bi and then deleting all tuples that contain two or more copies of the same symbol. Define random variables ¶ © Yi = (σ1 , . . . , σk ) ∈ Σk : fi (σ1 , . . . , σk ) = bi , P and let Y = i∈m Yi . Observe that we always have Y ≥ |X |, so it will be sufficient to show that Y ≤ |Σ|k/3 with probability 1 − o(1). If bi was set to fi (sNG (i,1) , . . . , sNG (i,k) ), we know by the randomness of fi that Yi is distributed as Yi ∼ 1 + Binom(|Σ|k − 1, |Γ|−1 ). 12 13

Technically, the PKE scheme will be (1 − o(1), 34 + o(1))-secure, but the constants 0.99 and 0.9 are easier to work with. In the proof we actually show that we can take κ = 1 − o(1).

In the case that bi was set to a random value, we again know by the randomness of fi that Yi ∼ Binom(|Σ|k , |Γ|−1 ). In both cases, because |Γ| = |Σ|3k/4 , a Chernoff bound shows that î ó Pr[Yi ≥ 2E[Yi ]] ≤ Pr Yi ≥ 2(1 + |Σ|k/4 ) < |Σ|−ω(1) . Applying a Markov bound over these events and assuming λ is sufficiently large (and therefore m, |Σ| are sufficiently large), the probability that a there exists a single Yi which is at least 2(1 + |Σ|k/4 ) is bounded as o(1). But this event is a necessary condition for Y to exceed |Σ|k/3 , because otherwise X Yi ≤ m · 2(1 + |Σ|k/4 ) < |Σ|k/3 , Y = i∈[m]

again assuming λ is sufficiently large and using that |Σ| = mω(1) . Before arguing that Distinguish allows us to decrypt successfully, first consider a modified PKE scheme where we remove Step 5 and Step 6 in algorithm KeyGen. We now demonstrate that the distributions over vectors w in algorithm Dec are within o(1) statistical distance of the distributions over vectors for which we assumed that Distinguish is an effective distinguisher. Claim 4.6. Consider a PKE scheme identical to the one in Section 4.1, but where we remove Step 5 and Step 6 in algorithm KeyGen. Then ζ(i) = ⊥ independently with probability α for all i. Proof. Observe that bi is set to a random value in Γ independently with probability α, for all i. Now in Step 9, we set ζ(i) = ⊥ whenever this event occurs. Otherwise, ζ(i) will map to the appropriate row index of H. Because we removed Step 5 and Step 6, such a row index always exists. Claim 4.7. Consider a PKE scheme identical to the one in Section 4.1, but where we remove Step 5 and Step 6 in algorithm KeyGen. Sample (pk, sk) ← KeyGen(1λ ) and ct ← Enc(1λ , pk, 0), and then run Dec(1λ , sk, ct). Over the random coins of KeyGen and Enc, the distribution over vectors w in algorithm Dec is within o(1) statistical distance of the following distribution over vectors c′ . Sample c ∈ {Gx : x ∈ Fn2 } at random, and then sample c′ :  with probability α.  “?”, ′ ci = Random element of F2 , with probability (1 − α)β.   ci , otherwise. Proof. We first argue that w will always be a noisy version of some codeword from C = {Gx : x ∈ Fn2 }. Consider the matrix G′ defined as follows: 1. If ζ(i) ̸= ⊥, then G′i = Hζ(i) . 2. Otherwise, G′i = 0|Σ| . Then delete all columns of G′ which are not indexed by some symbol si of the secret s as produced in KeyGen, and let the width of G′ be n′′ . Notice that by definition of ζ, we have that G′ is simply a copy of G where: 1. Some rows are replaced with 0. 19

2. The columns are permuted. 3. Some of the columns might be “merged” by taking their coordinate-wise locical-OR. This happens whenever there exist two indices i, j ∈ [n] such that i ̸= j but si = sj . By Claim 4.4, we know that with probability 1 − o(1), none of the columns are merged. In this case the ′′ linear code C ′ = {G′ x : x ∈ Fn2 } is the same as C = {Gx : x ∈ Fn2 }, but where a fixed set of coordinates is set to zero. By definition of Enc and Dec, w will be a corrupted version of a random codeword from C ′ , where the coordinates that are always set to 0 will be replaced with “?”. Now we argue that the erasure and corruption probabilities for w exactly match those in the statement of the claim (regardless of whether some columns of G are merged): 1. By Claim 4.2, we know that ζ(i) = ⊥ independently with probability α for all i. By the construction of w, we know that wi = “?” if and only if ζ(i) = ⊥, so the probability that wi = “?” is exactly α, independently for each coordinate. 2. By definition of Enc, we know that every non-erased coordinate of w will be set to a random value in F2 independently with probability β. Combining this with the erasure probability, we have that the probability a coordinate is not erased but is corrupted will be exactly (1 − α)β, independently for each coordinate. 3. Otherwise, the coordinate will be left un-erased and un-corrupted.

Claim 4.8. Consider a PKE scheme identical to the one in Section 4.1, but where we remove Step 5 and Step 6 in algorithm KeyGen. Sample (pk, sk) ← KeyGen(1λ ) and ct ← Enc(1λ , pk, 1), and then run Dec(1λ , sk, ct). Over the random coins of KeyGen and Enc, the distribution over vectors w in algorithm Dec is identical to the distribution over vectors r ∈ {F2 ∪ “?”}m sampled as follows: ® “?”, with probability α. ri = Random element of F2 , otherwise. Proof. Almost identical to the proof of Claim 4.7. The only difference is to observe that, when b = 1, ′ Enc(1λ , pk, b) will set the ciphertext to a uniformly random vector in Fm 2 . This means that the distribution over vectors w is identical to the distribution over vectors r, as opposed to just being within o(1) statistical distance. Now consider the actual PKE scheme from Section 4.1, i.e. we include Step 5 and Step 6. By Claim 4.4 and Claim 4.5, the probability that KeyGen aborts is o(1). If KeyGen does not abort, we still have that wi = “?” if and only if ζ(i) = ⊥, and furthermore ζ(i) = ⊥ if and only if bζ(i) was set to a random value in Step 3 of algorithm KeyGen. Putting all of this together with Claim 4.7 and Claim 4.8, we have: 1. In the case that we encrypted a bit b = 0, the distribution on vectors w is within o(1) statistical distance of the distribution on vectors c′ for which Pr Distinguish(1n , G, c′ ) = 0 ≥ 1 − o(1) 2. In the case that we encrypted a bit b = 1, the distribution on vectors w is within o(1) statistical distance of the distribution on vectors r for which Pr[Distinguish(1n , G, r) = 1] ≥ 1 − o(1) 20

So for the true PKE scheme, î ó Pr (pk, sk) ← KeyGen(1λ ); Dec(1λ , sk, Enc(1λ , pk, b)) = b ≥ 1 − o(1). Taking λ sufficiently large completes the proof of correctness.

4.3

Security

We use a standard hybrid argument to demonstrate security, by invoking Conjecture 3.1 (LARP-CSP) and Conjecture 3.2 (kXOR). Lemma 4.9 (Security). Let η = 0.9,14 and let λ be sufficiently large. Assume that Conjecture 3.1 (LARPCSP) holds with corruption rate α, and Conjecture 3.2 (kXOR) holds with corruption rate β. Then for all λO(1) -size non-uniform algorithms A, î ó Pr (pk, sk) ← KeyGen(1λ ); A(pk, Enc(1λ , pk, 1)) = 1 î ó − Pr (pk, sk) ← KeyGen(1λ ); A(pk, Enc(1λ , pk, 0)) = 1 < η Proof. Define the following hybrids. 1. H0 (1λ ): (a) Invoke KeyGen(1λ ) to obtain a public key pk. (b) Invoke Enc(1λ , pk, 0) to obtain a ciphertext ct. (c) Output (pk, ct). 2. H0,$ (1λ ): (a) Define KeyGen′ to be an algorithm identical to KeyGen, but where Step 3 in KeyGen sets b to a random vector in Γm . Invoke KeyGen′ (1λ ) to obtain a public key pk. (b) Invoke Enc(1λ , pk, 0) to obtain a ciphertext ct. (c) Output (pk, ct). 3. H1,$ (1λ ): (a) As before, define KeyGen′ to be an algorithm identical to KeyGen, but where Step 3 in KeyGen sets b to a random vector in Γm . Invoke KeyGen′ (1λ ) to obtain a public key pk. (b) Invoke Enc(1λ , pk, 1) to obtain a ciphertext ct. (c) Output (pk, ct). 4. H1 (1λ ): (a) Invoke KeyGen(1λ ) to obtain a public key pk. (b) Invoke Enc(1λ , pk, 1) to obtain a ciphertext ct. (c) Output (pk, ct). Now we argue that an adversary has advantage less than 0.3 to distinguish between each pair of hybrids. 14

We could actually take η = 34 + o(1); the choice η = 0.9 just makes the arguments a bit simpler.

Claim 4.10. Assume that Conjecture 3.1 (LARP-CSP) holds with corruption rate α. Then for all sufficiently large λ, for all λO(1) -size non-uniform algorithms A, î ó î ó Pr A(H0 (1λ )) = 1 − Pr A(H0,$ (1λ )) = 1 < 0.3 Proof. Suppose for contradiction that there exists a λO(1) -size non-uniform algorithm A such that î ó î ó Pr A(H0 (1λ )) = 1 − Pr A(H0,$ (1λ )) = 1 ≥ 0.3. By assumption on MatrixGen, G will be a (1 − o(1), n1−o(1) )-expander with probability 1 − o(1). Thus î ó Pr A(H0 (1λ )) = 1 G is a (1 − o(1), n1−o(1) )-expander î ó − Pr A(H0,$ (1λ )) = 1 G is a (1 − o(1), n1−o(1) )-expander ≥ 0.3 − o(1), and by the averaging principle there must exist a specific (1 − o(1), n1−o(1) )-expander G∗ such that î ó Pr A(H0 (1λ )) = 1 H0 (1λ ) samples G = G∗ î ó − Pr A(H0,$ (1λ )) = 1 H0,$ (1λ ) samples G = G∗ ≥ 0.3 − o(1). By definition of H0 and H0,$ , we can reduce the decision problem in Conjecture 3.1 with matrix G∗ , corruption parameter α, and parameters n, m, k, |Σ|, |Γ| to the problem of differentiating between the outputs of H0 (1λ ) and H0,$ (1λ ), where both H0 (1λ ) and H0,$ (1λ ) are conditioned on sampling G = G∗ . Thus A implies a λO(1) = |Σ|O(k) size algorithm for the problem in Conjecture 3.1 with distinguishing advantage at least 0.3 − o(1). Assuming λ is sufficiently large, this exceeds 1/4, which is a contradiction. Claim 4.11. Assume that Conjecture 3.2 (kXOR) holds with corruption rate β. Then for all λO(1) -size non-uniform algorithms A, î ó î ó Pr A(H0,$ (1λ )) = 1 − Pr A(H1,$ (1λ )) = 1 < 0.3 Proof. Suppose for contradiction that there exists a λO(1) size non-uniform algorithm A such that î ó î ó Pr A(H0,$ (1λ )) = 1 − Pr A(H1,$ (1λ )) = 1 ≥ 0.3. We argue that this directly gives an algorithm contradicting Conjecture 3.2. The only difference between the two hybrids is the sampling procedure for v in algorithm Enc. In fact, conditioning both H0,$ and H1,$ on not aborting, the distribution (pk, ct) ∼ H0,$ (1λ ) is exactly distribution (2) in Conjecture 3.2, and the distribution (pk, ct) ∼ H1,$ (1λ ) is exactly distribution (1), where both distributions are with respect to an m′ × n′ matrix H with m′ = (n′ )k/3 . So given A, we construct a λO(1) = |Σ|O(k) = (m′ )O(1) size distinguisher B(H, b) for Conjecture 3.2 by picking the best choice of randomness for the following procedure: 1. Run H0,$ (1λ ). If the output is (⊥, ⊥) then return A(⊥, ⊥). 2. Otherwise, return A(H, b). B has advantage at least 0.3 > 1/4, which is a contradiction. 22

Claim 4.12. Assume that Conjecture 3.1 (LARP-CSP) holds with corruption rate α. Then for all sufficiently large λ, for all λO(1) -size non-uniform algorithms A, î ó î ó Pr A(H1,$ (1λ )) = 1 − Pr A(H1 (1λ )) = 1 < 0.3 Proof. Identical to the proof of Claim 4.10. Composing Claims 4.10, 4.11, and 4.12 completes the proof of security.

4.4

Conversion to a Semantically Secure PKE

Putting together the ingredients from Sections 4.1, 4.2, and 4.3, we get a semantically secure PKE scheme. Theorem 4.13. Suppose we have an (α, β)-decodable expanding code. Then assuming Conjecture 3.1 (LARP-CSP) holds with corruption rate α, and Conjecture 3.2 (kXOR) holds with corruption rate β, there is a semantically secure public key encryption scheme. Proof. By Lemmas 4.3 and 4.9, the PKE scheme in Section 4.1 instantiated with an (α, β)-decodable expanding code is a (0.99, 0.9)-secure PKE scheme. Because 0.992 = 0.9801 > 0.9, an application of Theorem 2.7 gives us a semantically secure PKE scheme.

Instantiating a (1 − o(1), 1 − o(1))-Decodable Expanding Code

In this section we construct an (α, β)-decodable expanding code, where α = β = 1 − o(1). As discussed in Section 4.4, this gives a semantically secure PKE scheme if we assume that Conjecture 3.1 and Conjecture 3.2 both hold.

5.1

Sampling the Generator Matrix

Here we give a simple probabilistic algorithm that runs in time mO(1) and outputs a generator matrix G ∈ for an expanding code C = {Gx : x ∈ Fn2 }, such that C is a subcode of RM(log m, log2 n). This will Fm×n 2 be the algorithm MatrixGen for our (α, β)-decodable expanding code. Theorem 1.7 (Restated). There is an explicit randomized algorithm Kck ,cm (1n ) parameterized by two cm constants ck , cm satisfying cm ≥ 2 and ck ≥ cm + 1, that runs in time 2O((log n) ) and outputs a matrix G, such that: cm

1. G is an (m, n, k)-matrix, where m = 2(⌈log n⌉)

and k = (⌈log n⌉)ck .

2. The code {Gx : x ∈ Fn2 } is a subcode of the Reed-Muller code RM((⌈log n⌉)cm , (⌈log n⌉)2 ). 3. With 1 − o(1) probability over the coins of Kck ,cm , G is (1 − o(1), n1−o(1) )-expanding. Proof. We propose the following algorithm. (Recall that all logarithms are taken base 2.) G ← Kck ,cm (1n ): cm

1. Set k := (⌈log n⌉)ck , m := 2(⌈log n⌉)

, w := ⌊log(n/k)⌋

2. Sample kw random degree-⌈log n⌉ polynomials m g (1,1) , . . . , g (1,w) , g (2,1) , . . . , g (k,w) : Flog → F2 . 2

3. For all i ∈ [k], we construct a matrix M(i) ∈ Fm×2 as follows. 2 m (a) Each row is indexed by a point p ∈ Flog 2

(b) Each column is indexed by a point q ∈ Fw 2. (i)

(i)

(c) Set Mp,q = 1 if and only if g (i,j) (p) = qj for all j ∈ [w], or equivalently set Mp,q = 1 if and only if the concatenation of the evaluations g (i,1) (p)∥ . . . ∥g (i,w) (p) equals q. î ó 4. Set G = M(1) ∥ . . . ∥M(k) , and then append zero columns until the width is exactly n. 5. Output G. cm

By construction, the algorithm runs in 2O((log n) ) time, and G is a matrix over F2 of width n and height m. To show that every row has exactly k nonzero entries, it suffices to show that each matrix M(i) m has exactly one nonzero entry per row. This follows because, for every point p ∈ Flog , there is exactly 2 (i,j) (p) = q for all j ∈ [w]. one point q ∈ Fw such that g j 2 We now argue that G generates a subcode of RM((⌈log n⌉)cm , (⌈log n⌉)2 ), which amounts to showing that every column is the truth table for a degree ≤ (⌈log n⌉)2 polynomial. Every column coming not coming from a submatrix M (i) is zero and thus of degree zero, so we can ignore these columns. Now fix any choice of i and examine the submatrix M (i) . Observe that Step 3c is equivalent to defining ä Y Ä (i) Mp,q = g (i,j) (p) + qj + 1 . j∈[w]

If we fix any column, this amounts to fixing a choice of point q, and allowing p to range over all points in Fm 2 . This gives the truth table for a polynomial of degree at most X degree(g (i,j) ). j∈[w]

Every g (i,j) is of degree at most ⌈log n⌉ by construction, and w := ⌊log(n/k)⌋ < ⌈log n⌉. So the degree is upper bounded by w⌈log n⌉ < (⌈log n⌉)2 . All that remains is to show that, with probability 1−o(1), G is a (1−o(1), n1−o(1) )-expander. Intuitively, the proof will have three parts: 1. Show that a random matrix with the same parameters will be a (1 − o(1), n1−o(1) )-expander. î ó 2. Show that, on a local level, the matrix M(1) ∥ . . . ∥M(k) is statistically random. î ó 3. Compose these results via a union bound to show that M(1) ∥ . . . ∥M(k) , and hence G, is a (1 − o(1), n1−o(1) )-expander. w

Claim 5.1. Let R(1) , . . . , R(k) ∈ Ft×2 2 î be sampled at órandom, conditioned on each matrix having exactly 1 nonzero entry per row, and let R := R(1) ∥ . . . ∥R(k) . Then assuming n is sufficiently large and 1 ≤ t ≤ √ 2w /(⌈log n⌉)2 , with probability at least 1 − 2−kt/ ⌈log n⌉ , Ñ é » _ hw Ri > 1 − 1/ ⌈log n⌉ · k · t. i∈[t]

Proof. It suffices to bound the probability that Ñ é » _ W = hw Ri ≤ 1 − 1/ ⌈log n⌉ · k · t. i∈[t] (j)

Consider sampling each row of each R(j) one-by-one. The probability that a new row Ri does not increase (j) W is exactly the probability that the nonzero entry in Ri falls into the same column as a previously w sampled nonzero entry. Because each R(j) has t rows, the probability that this event Ä occurspis at mostä t/2 , independently for each i ∈ [t] and j ∈ [k]. There are kt choices for i, j, so W ≤ 1 − 1/ ⌈log n⌉ · k · t p (j) if and only if this event occurs for at least kt/ ⌈log n⌉ rows Ri . This probability is upper bounded as Ç å √ kt p · (t/2w )kt/ ⌈log n⌉ kt/ ⌈log n⌉ » kt/√⌈log n⌉ √ < 3 ⌈log n⌉ (Standard approximation xy < (3x/y)y ) · (t/2w )kt/ ⌈log n⌉ » kt/√⌈log n⌉ kt/√⌈log n⌉ ≤ 3 ⌈log n⌉ · (⌈log n⌉)−2 (t ≤ 2w /(⌈log n⌉)2 ) √ √ −2 kt/ ⌈log n⌉ kt/ ⌈log n⌉ · (⌈log n⌉) (Assuming n is sufficiently large) <⌈log n⌉ √ =⌈log n⌉−kt/ ⌈log n⌉ √ <2−kt/ ⌈log n⌉ (Assuming n is sufficiently large)

m (1) (k) of size 1 ≤ |T | ≤ 2w /(⌈log n⌉)î2 , and then sample Claim 5.2. Fix a subset T ⊂ Flog 2 ó M ,...,M as in the algorithm Kck ,cm , denoting their concatenation as M = M(1) ∥ . . . ∥M(k) . Assuming n is √ sufficiently large, with probability at least 1 − 2−k|T |/ ⌈log n⌉ , Ñ é » _ hw Mp > 1 − 1/ ⌈log n⌉ · k · |T |. p∈[t] m Proof. Recall that every polynomial g (i,j) is a random degree-⌈log n⌉ polynomial g (i,j) : Flog → F2 . 2 (i,j) log m (i,j) (i,j) Thus the length-m vector v defined as vp = g (p), where p ranges over all points in F2 , will be a random member of the Reed-Muller code RM(log m, ⌈log n⌉). Now by Lemma 2.10, the dual code to RM(log m, ⌈log n⌉) is RM(log m, log m − ⌈log n⌉ − 1), and by Lemma 2.9 the minimum distance of this dual code will be 2⌈log n⌉+1 > n. This means that if we fix at most n points and then sample a random polynomial g (i,j) of degree ⌈log n⌉, the evaluation of g (i,j) on each of these points will be independently drawn from Ber(1/2). m Because 2w /(⌈log n⌉)2 = 2⌊log(n/k)⌋ /(⌈log n⌉)2 < n, this means that for a fixed subset T ⊂ Flog of 2 w 2 (i,j) size at most 2 /(⌈log n⌉) , the evaluations of all polynomials g on points in T will be uniformly random. As a result, the distribution over matrices M restricted to the rows indicated by T will be uniformly random, conditioned on each sub-matrix M(i) having exactly one nonzero entry per row. Now the proof is completed by applying Claim 5.1.

From here we just need to union bound over all choices of subsets T . Claim 5.3. With 1 − o(1), for all sufficiently large n, the matrix G produced in algorithm Kck ,cm p probability w is a (1 − 1/ ⌈log n⌉, 2 /(⌈log n⌉)2 )-expander. Proof. Fix a size parameter 1 ≤ t ≤ 2w /(⌈log n⌉)2 ). There are Ç å m ≤ mt t size-t subsets of rows in G, and by Claim 5.2 each subset violates expansion with probability at most √ 2−kt/ ⌈log n⌉ . Union bounding over all choices of rows, the probability that at least one size-t subset violates expansion is at most √ mt · 2−kt/ ⌈log n⌉ √ Ä ä c cm t cm = 2(⌈log n⌉) · 2−((⌈log n⌉) k )t/ ⌈log n⌉ (m := 2(⌈log n⌉) and k := (⌈log n⌉)ck ) Ä ä √ ck cm =2t (⌈log n⌉) −(⌈log n⌉) / ⌈log n⌉ Ä ä √ cm +1 / cm ⌈log n⌉ ≤2t (⌈log n⌉) −(⌈log n⌉) . (ck ≥ cm + 1) c c +1/2 m m ). ≤2t((⌈log n⌉) −(⌈log n⌉)

Assuming n is sufficiently large, this is less than t

cm +1/2

2− 2 (⌈log n⌉)

A final union bound over all choices of t completes the proof. p The above shows that G is a (1 − 1/ ⌈log n⌉, 2w /(⌈log n⌉)2 )-expander with probability 1 − o(1). Observe that 2w /(⌈log n⌉)2 ) =2⌊log(n/k)⌋ /(⌈log n⌉)2 ≥Ω(2log(n/k) /(log n)2 ) =Ω(n/(log n)2+ck ) =n/(log n)O(1) =n1−o(1) . Thus G is a (1 − o(1), n1−o(1) )-expander with probability 1 − o(1), as desired.

5.2

The Distinguishing Algorithm

We use the Reed-Muller decoding algorithm of Saptharishi, Shpilka, and Volk [SSV16] as a starting point for the algorithm Distinguish in our (α, β)-decodable expanding code.

Theorem 2.11 (Due to [SSV16], Restated). There is a function γ(d) ≥ 1 − o(1), γ(d) ≤ 1 − d−O(1) and a poly(2d ) time algorithm D that outputs a vector in RM(d, d1/3 ) and behaves as follows. Pick a random codeword c ∈ RM(d, d1/3 ), and sample a noisy version c′ of c: c′i =

Random element of F2 , ci ,

with probability γ(d). otherwise.

Then Pr D(c′ ) = c ≥ 1 − o(1).

The conversion to a distinguisher goes as follows. Lemma 5.4. There is a function µ(d) ≥ 1 − o(1), µ(d) ≤ 1 − d−O(1) and a poly(2d ) time algorithm E that outputs a vector in RM(d, d1/3 ) and behaves as follows. Let m = 2d . Pick a random codeword c ∈ RM(d, d1/3 ), and sample a noisy version c′ ∈ {F2 ∪ “?”}m of c:  with probability µ.  “?”, ′ ci = Random element of F2 , with probability (1 − µ)µ.   ci , otherwise. Also sample a random vector r ∈ {F2 ∪ “?”}m : ® ri =

“?”, Random element of F2 ,

with probability µ. otherwise.

Then Pr E(c′ ) = 0 ≥ 1 − o(1)

Pr[E(r) = 1] ≥ 1 − o(1). p Proof. Let γ(d) = 1 −o(1) be as in Theorem 2.11, and set µ(d) = 1− 1 − γ(d) = 1 − o(1). Observe that the decoder D from that theorem doubles as a decoder for a noisy version c′ ∈ {F2 ∪ “?”}m of a random codeword c ∈ RM(d, d1/3 ) sampled as follows:  with probability µ.  “?”, ′ ci = Random element of F2 , with probability (1 − µ)µ.   ci , otherwise. and

This is because we can replace every erasure symbol “?” with a random element of F2 and then apply D on the resulting vector, which will have a corruption rate of Ä ä p Ä ä p p µ + (1 − µ)µ = 1 − 1 − γ + 1 − γ 1 − 1 − γ Äp ä Äp ä p p =1 − 1 − γ + 1 − γ − 1−γ · 1−γ =1 − (1 − γ) =γ Now we describe how to convert the decoder into a distinguisher. Since γ(d) ≤ 1 − d−O(1) = 1 − (log n)−O(1) , a concentration bound shows that there is a cutoff value z ∗ satisfying the following conditions. 27

1. Let c be a random codeword from RM(d, d1/3 ), and let c′ be the vector c subjected to corruptions of rate γ. Then c′ disagrees with c on less than z ∗ coordinates with probability 1 − o(1). Consequently D(c′ ) disagrees with c′ on less than than z ∗ coordinates with probability 1 − o(1). 1/3 ), r disagrees with c 2. Let r ∈ Fm 2 be a random vector. With probability 1 − o(1), for all c ∈ RM(d, d on more than z ∗ coordinates. Since D outputs a vector in RM(d, d1/3 ), we have that with probability 1 − o(1), D(r) disagrees with r on more than than z ∗ coordinates.

So the distinguisher just invokes D, counts the number of coordinates on which the input vector and output vector disagree, and accepts or rejects by performing a threshold test on this value.

5.3

Putting it Together

Combining Theorem 4.13 with Theorems 1.7 and 5.4, we have our PKE scheme. Theorem 1.3 (Restated). Suppose that Conjecture 1.1 (High Corruption LARP-CSP) and Conjecture 1.2 (High Corruption kXOR) both hold. Then there is a semantically secure public key encryption scheme. Proof. Recall that Conjecture 1.2 is simply Conjecture 3.2 instantiated with any choice of corruption rate β(n) = 1 − o(1), and similarly Conjecture 1.1 is simply Conjecture 3.1 instantiated with any choice of corruption rate α(n) = 1 − o(1). By Theorem 4.13, it suffices to exhibit an (α, β)-decodable expanding code, where α(n) = β(n) = 1 − o(1). Fix ck = 7 and cm = 6. The matrices G sampled in our (1 − o(1), 1 − o(1))-decodable expanding code 6 will be of width n and height m = 2O((log n) ) , and each row will have k = (⌈log⌉n⌉)7 nonzero entries. 6 By Theorem 1.7, we have a 2O((log n) ) = mO(1) time algorithm K7,6 (1m ) that can be used as the algorithm MatrixGen. Furthermore, for every choice of internal coins, the (m, n, k)-matrix G output by K7,6 (1m ) will generate a subcode C = {Gx : x ∈ Fn2 } of RM(d = (⌈log n⌉)6 , d1/3 = (⌈log n⌉)2 ). We can thus use algorithm E from Lemma 5.4 directly as the algorithm Distinguish, and the running time of this algorithm is 2O(d) = mO(1) . The error rate and corruption rate that this algorithm can tolerate both tend towards 1 as d increases; because d increases with n, they are both 1 − o(1).

Evidence for the LARP-CSP Conjecture

In this section we give a variety of algorithmic lower bounds supporting Conjecture 3.1 (LARP-CSP). In fact, all of our lower bounds will be for the corruption-free version. We formalize this version of the decision problem as follows. Problem 1. Let H be any (1 − o(1), n1−o(1) )-expanding (m, n, k)-matrix, where k = (log n)Θ(1) and Θ(1) m ≤ no(k) . Let Σ, Γ be any alphabets satisfying |Σ| = (nm)log (nm) and |Γ| ≤ |Σ|3k/4 . Sample m random functions fi : Σk → Γ, and let F be the set of all fi . The task is to distinguish between the following two distributions. 1. Null distribution Q: (H, F, b), where b ∈ Γm is sampled uniformly at random. 2. Planted distribution P: (H, F, b), where we sample s ∈ Σn at random and set bi = fi (sNH (i,1) , . . . , sNH (i,k) ). For a given pair (H, F), let QH,F denote the distribution on vectors b as sampled in (1), and PH,F denote the distribution on vectors b as sampled in (2). 28

6.1

Low Complexity Embedding Attacks

As discussed in Section 1.1 of the introduction, there are known counterexamples to the security of Goldreich’s PRG over arbitrary expanders [OST18]. In this subsection we explore and then immediately rule out the possibility of using these attacks to break Problem 1. We start by giving a hypothesis testing framework which significantly generalizes the set of attacks given by Oliveira, Santhanam, and Tell [OST18], and then show that the entropy of the random functions alone is enough for Problem 1 to unconditionally resist all such attacks. The Attack on Goldreich’s PRG. Oliveira, Santhanam, and Tell [OST18] consider the following decision problem,15 which is similar to Problem 1 but uses small alphabets and a single, low complexity predicate. Given a (1 − o(1), n1−o(1) )-expanding (m, n, k)-matrix H and a predicate f : {0, 1}k → {0, 1}, distinguish between the following distributions: 1. (H, f, b), where b ∈ {0, 1}m is sampled at random. 2. (H, f, b), where we sample s ∈ {0, 1}n at random and set bi = f (sNH (i,1) , . . . , sNH (i,k) ).

All of their attacks now assume the same general format. They (non-constructively) prove the existence O(1) n , n, logO(1) n)-matrix H such that the above problem can be solved in quasiof an expanding (nlog polynomial time, assuming the predicate f is of a particular form; both the matrix H and the predicate f must be representable using a sufficiently small AC0 [+] circuit. When these properties hold, they demonstrate that for every choice of seed s, the vector b in distribution (2) will be the truth table of a small (unknown) AC0 [+] circuit. Their attacks then work by leveraging natural property algorithms (see e.g. [Raz87, Smo87, RR94, CIKK16]), which can distinguish with constant advantage between the truth table of any small AC0 [+] circuit and a random vector of the same length. A different way to look at the attacks is as follows. Let L ⊂ {0, 1}m be the set of all truth tables for small AC0 [+] circuits. Use a natural property algorithm to determine if dist(b, L) = 0, and choose to accept or reject based on the result. Recall that dist(b, L) is the Hamming distance between b and the closest vector in L, so dist(b, L) = 0 if and only if b ∈ L. Our Generalized Framework. Here we define the notion of a low complexity embedding game. As we discuss later, this game significantly generalizes the Oliveira-Santhanam-Tell attack. Before giving the game, we define the generalized distance between two vectors u, v ∈ {F ∪ ⊥}m to be dist’(u, v) = i : ui ̸= vi and ui ̸=⊥ and vi ̸=⊥ , i.e. the number of coordinates on which u, v disagree but excluding those coordinates with a “don’t care” symbol ⊥. For a vector u ∈ {F ∪ ⊥}m and a set L ⊆ {F ∪ ⊥}m , we define dist’(u, L) to be the minimum of dist’(u, v) over all v ∈ L. Definition 6.1 (Low Complexity Embedding Game). 16 The game goes as follows. 15 16

The authors phrase this problem in terms of graphs and use slightly different terminology, but our version is equivalent. Technically speaking, the game allows for the adversary to choose more general mappings than just injective embeddings.

1. The challenger fixes parameters m, n, k and alphabets Σ, Γ. She also fixes the description of (a) A null distribution DH,F over vectors b ∈ Γm , ′ (b) A planted distribution DH,F over vectors b ∈ Γm , and (c) A distribution Z over sets of functions F = {fi : Σk → Γ}i∈[m] . ′ Both DH,F and DH,F depend on a (1 − o(1), n1−o(1) )-expanding (m, n, k)-matrix H to be fixed later by the adversary, and a set of functions F = {fi : Σk → Γ} to be sampled later by the challenger. ′ 2. After viewing the descriptions of DH,F , DH,F , and Z, the adversary spends unbounded time to choose 1−o(1) a (1 − o(1), n )-expanding (m, n, k)-matrix H along with a tuple (F, d, L, Ψ), where

(a) F is any finite field, (b) d is an embedding dimension parameter, (c) L ⊆ {F ∪ ⊥}md is any subset of vectors, and (d) Ψ : Fmd → {F ∪ ⊥}md is any transformation. 3. The challenger samples a set of functions F from the distribution Z. ′ 4. Based on H, F, the description of DH,F , and the description of DH,F , the adversary spends unbounded time to fix a tuple (Φ, π, h), where

(a) Φ = {ϕi : Γ → Fd }i∈[m] is any set of (not necessarily injective) functions. (b) π : Fmd → Fmd is any affine transformation. (c) h : {0, . . . , md} → {0, 1} is an acceptance predicate. The adversary wins the game if and only if Pr′

b∼DH,F

−

h i h dist’ Ψ π ϕ(b1 )∥ . . . ∥ϕ(bm ) , L = 1 Pr

b∼DH,F

h i h dist’ Ψ π ϕ(b1 )∥ . . . ∥ϕ(bm ) , L = 1 = Ω(1).

Notice that the adversary fixes some components of the test in advance and other components after gaining knowledge of the functions in F . Intuitively, the first parameters (F, d, L, Ψ) are generic, in the sense that they give the description of a “testing structure” which is meant to be compatible with the adversarially chosen expander H. The parameters (Φ, π, h) fixed after viewing F allow the adversary to perform a best-possible coordinatewise mapping of an observed vector b into a vector over Fmd . The mappings in Φ are not required to be injective, which means that an adversary can choose to aggregate different symbols of the alphabet Γ in an optimal manner. Notice that, while π is “just” an affine transformation, it does have the power to arbitrarily permute coordinates, perform linear computations, and erase coordinates (by setting them equal to a designated constant which is later mapped by Ψ to ⊥). This gives the adversary significant power to massage the vectors b into a form which is compatible with the “testing structure” defined by (F, d, L, Ψ), especially when the alphabet Γ does not have a natural field structure (as is the case in Problem 1). Keep in mind that at every step, we grant the adversary unbounded time to pick the best matrix H, the best tuple (F, d, L, Ψ), and the best tuple (Φ, π, h). We also place no requirements on the time required to compute dist’ Ψ π ϕ(b1 )∥ . . . ∥ϕ(bm ) , L , 30

even though L is an arbitrary structure chosen by the adversary. As of today, we only know of efficient algorithms to perform this distance computation, even approximately, for very specific sets L (e.g. the set of truth tables for small AC0 [+] circuits). Re-Framing the Oliveira-Santhanam-Tell Attack. embedding game: 1. The challenger fixes parameters (m, n, k) = (nlog {0, 1}). She also fixes

We view the attack in terms of a low complexity O(1)

n , n, logO(1) n) and alphabets (Σ, Γ) = ({0, 1},

(a) The null distribution DH,F as the uniform distribution over vectors b ∈ {0, 1}m . ′ (b) The planted distribution DH,F as the distribution over vectors b ∈ {0, 1}m sampled by picking s ∈ {0, 1}n at random and then setting

bi = fi (sNH (i,1) , . . . , sNH (i,k) ). (c) Any distribution Z over sets of functions F = {fi : Σk → Γ}i∈[m] such that for all F drawn from Z: i. For all i, j ∈ [m], we have fi = fj . ii. For all i ∈ [m], the function fi is computable by a sufficiently small AC0 [+] circuit. 2. The adversary constructs a (1 − o(1), n1−o(1) )-expanding (m, n, k)-matrix H that is described by a sufficiently small AC0 [+] circuit. She also fixes a tuple (F, d, L, Ψ), where (a) F := F2 , (b) d := 1, (c) L ⊆ {F2 ∪ ⊥}md is the set of all truth tables for sufficiently small AC0 [+] circuits (the symbol ⊥ is not used). md is the identity transformation (the symbol ⊥ is again not used). (d) Ψ : Fmd 2 → {F2 ∪ ⊥}

3. The challenger samples a set of functions F from the distribution Z. 4. The adversary spends unbounded time to fix a tuple (Φ, π, h), where (a) Every ϕi ∈ Φ just casts from {0, 1} to the field F2 by mapping zero to zero and one to one. (b) π is the identity transformation. (c) h is the function which outputs 1 iff its input is zero. Now because most functions were set to the identity, if we abuse notation and assume that b is already over the field F2 then Pr′

b∼DH,F

−

h i h dist’ Ψ π ϕ(b1 )∥ . . . ∥ϕ(bm ) , L = 1 Pr

b∼DH,F

h i h dist’ Ψ π ϕ(b1 )∥ . . . ∥ϕ(bm ) , L = 1

is the same as Pr′

b∼DH,F

−

h i dist’ b, L = 0 Pr

b∼DH,F

h dist’ b, L = 0 .

The authors showed that this quantity is Ω(1), so the adversary wins the game. Regarding the Adversary’s Strength. Observe that, by allowing the adversary to fix any subset L ⊆ {F ∪ ⊥}md , any problem where the set of functions F does not come from a high entropy distribution is immediately broken. As a simple example, consider the noisy kXOR problem with a random factor graph. Because the predicates fi are all just addition over F2 , and because the adversary has knowledge of the factor graph before fixing L, she can just set L to be the set of all (noiseless) vectors b that could be sampled in the planted distribution. Now if dist’(b, L) is small, we know that the vector b was almost certainly drawn from the planted distribution, and if dist’(b, L) is large then we know that b was almost certainly drawn from the null (totally random) distribution. In this way the adversary is unreasonably powerful. But for the purposes of proving lower bounds, this is only better; we rule out adversaries that capture the known attacks on Goldreich’s PRG [OST18] as well as some attacks on noisy kXOR that are conjectured to be impossible to implement efficiently. 6.1.1

Our Lower Bound Against Low Complexity Embedding Attacks

To keep track of the parameters, recall Problem 1 (which is just the corruption-free version of the decision problem in Conjecture 3.1, the LARP-CSP Conjecture): Problem 1 (Restated). Let H be any (1−o(1), n1−o(1) )-expanding (m, n, k)-matrix, where k = (log n)Θ(1) Θ(1) and m ≤ no(k) . Let Σ, Γ be any alphabets satisfying |Σ| = (nm)log (nm) and |Γ| ≤ |Σ|3k/4 . Sample m random functions fi : Σk → Γ, and let F be the set of all fi . The task is to distinguish between the following two distributions. 1. Null distribution Q: (H, F, b), where b ∈ Γm is sampled uniformly at random. 2. Planted distribution P: (H, F, b), where we sample s ∈ Σn at random and set bi = fi (sNH (i,1) , . . . , sNH (i,k) ). For a given pair (H, F), let QH,F denote the distribution on vectors b as sampled in (1), and PH,F denote the distribution on vectors b as sampled in (2). Now we give a formal statement of the lower bound. Theorem 6.2. Fix any (1 − o(1), n1−o(1) )-expanding (m, n, k)-matrix H, where k = (log n)Θ(1) and Θ(1) m ≤ no(k) . Let Σ, Γ be any alphabets satisfying |Σ| = (nm)log (nm) and |Γ| ≤ |Σ|3k/4 . Also fix any 1. Finite field F of order 2 ≤ |F| ≤ 2|Σ|

o(k)

2. Embedding dimension parameter 1 ≤ d ≤ mO(1) , 3. Subset L ⊆ {F ∪ ⊥}md , and 32

4. Transformation Ψ : Fmd → {F ∪ ⊥}md . ¶ © After this, sample the set of functions F as in Problem 1. Then with probability 1 − exp −|Σ|Ω(k) , the following holds. For all 1. Functions ϕ1 , . . . , ϕm : Γ → Fd , 2. Affine transformations π : Fmd → Fmd , and 3. Acceptance predicates h : {0, . . . , md} → {0, 1}, we have Pr

b∼PH,F

−

h i h dist’ Ψ π ϕ(b1 )∥ . . . ∥ϕ(bm ) , L = 1 Pr

b∼QH,F

h i h dist’ Ψ π ϕ(b1 )∥ . . . ∥ϕ(bm ) , L = 1 ≤ |Σ|−Ω(k) ,

where QH,F and PH,F are the null and planted distributions for Problem 1, respectively. In the proof Theorem 6.2, we need a way to formalize the dependencies between random variables. Definition 6.3 (Dependency Graph). Let X1 , . . . Xs be random variables. The dependency graph for X1 , . . . Xs has one vertex for each random variable, and two variables Xi , Xj are connected by an edge if and only if they are dependent. We also use a concentration bound due to Janson. P Lemma 6.4 ([Jan04], basic version of Corollary 2.2). Let X = i∈[r] Xi be the sum of r random variables X1 , . . . , Xr , each distributed as Bernoulli variables. Let G be the dependency graph for X1 , . . . , Xr . Then ß Å ã™ t2 Pr[X ≥ E[X] + t] ≤ exp −Ω , and (∆(G) + 1)r ß Å Pr[X ≤ E[X] − t] ≤ exp −Ω

t2 (∆(G) + 1)r

ã™ ,

where ∆(G) is the maximum degree of G. Now we are ready to prove the lower bound. Proof of Theorem 6.2. The proof will proceed in two parts: 1. Show that if (F, d, L, Ψ) and (Φ, π, h) are fixed before sampling the random functions in F , there is a sharp tail bound showing that the test almost surely has negligible advantage. 2. Union bound over all choices of (Φ, π, h), showing that with high probability there does not exist a good test even if an adversary is allowed to fix (Φ, π, h) after examining F.

Claim 6.5. Fix an (m, n, k)-graph H and any choice of (F, d, L, Ψ) and (Φ, π, h). Then sample m random (4/5−o(1))k functions fi : Σk → Γ, and let F be the set of all fi . With probability at least 1 − 2−|Σ| over the choice of F, Pr

b∼PH,F

−

h i h dist’ Ψ π ϕ(b1 )∥ . . . ∥ϕ(bm ) , L = 1 Pr

b∼QH,F

h i h dist’ Ψ π ϕ(b1 )∥ . . . ∥ϕ(bm ) , L = 1 < |Σ|−k/10 .

Proof. Let U be the distribution over sets of functions F = {fi : Σk → Γ}i∈[m] where each of the functions fi are sampled at random. Let T be shorthand for the test function h dist’ Ψ π ϕ(b1 )∥ . . . ∥ϕ(bm ) , L , which by definition of h always outputs a value in {0, 1}. It will suffice to show that # " Pr

F ∼U

is at most 2−|Σ|

Pr [T(b) = 1] −

b∼PH,F

b∼QH,F

[T(b) = 1] ≥ |Σ|−k/10

(4/5−o(1))k

. We only prove the upper bound for "Å # ã Pr Pr [T(b) = 1] − Pr [T(b) = 1] ≥ |Σ|−k/10

F ∼U

b∼PH,F

b∼QH,F

(1)

because the other case is nearly identical. First consider the behavior under the null distribution. By definition of T there exists a set S ⊆ Γm (which does not depend on F) such that T(b) = 1 if and only if b ∈ S. Since b is sampled at random in the null distribution, we have |S| Pr [T(b) = 1] = b∼QH,F |Γ|m for all sets of functions F. Thus (1) can be written as # "Å ã |S| ≥ |Σ|−k/10 . Pr Pr [T(b) = 1] − F ∼U b∼PH,F |Γ|m

(2)

Now consider the behavior under the planted distribution. Recall that we sample b ∈ Γm by first sampling s ∈ Σn uniformly at random, and then setting bi = fi (sNH (i,1) , . . . , sNH (i,k) ). Let PH,F (s) be the function which outputs this vector b for a given vector s. Because T always outputs a value in {0, 1} (which we interpret as a real number), and because s ∈ Σn is sampled uniformly at random, (2) can be written as ! # " |S| 1 X −k/10 T(PH,F (s)) − ≥ |Σ| , Pr F ∼U |Σ|n |Γ|m n s∈Σ

which is equivalent to " Pr

F ∼U

|S||Σ|n T(PH,F (s)) − |Γ|m n

X s∈Σ

# ≥ |Σ|−k/10 |Σ|n .

(3)

Let {Xs }P s∈Σn be the set of 0/1 valued random variables defined as Xs = T(PH,F (s)), and denote their sum as X = s∈Σn Xs . By the randomness of the functions in F, for all s ∈ Σn we have EF ∼U [Xs ] = which implies that EF ∼U [X] =

|S| , |Γ|m

|S||Σ|n . |Γ|m

Therefore (3) is equivalent to î ó Pr X ≥ EF ∼U [X] + |Σ|−k/10 |Σ|n .

F ∼U

From here our plan is give a concentration bound. Observe that Xs and Xs′ are independent if and only if, for all i ∈ [m], we have (sNH (i,1) , . . . , sNH (i,k) ) ̸= (s′NH (i,1) , . . . , s′NH (i,k) ). This is because the evaluation of each function fi is independently random on each of its inputs. So the dependency graph G for the n random variables Xs satisfies ∆(G) ≤ m|Σ| . Applying Lemma 6.4, we get k |Σ| Å

|Σ|2n |Σ|−k/5 î ó −Ω −k/10 n |Σ|2n |Σ|−k m Pr X ≥ EF ∼U [X] + |Σ| |Σ| ≤2

F ∼U

≤2−Ω(|Γ| Because |Σ| = mω(1) , this probability is upper bounded as 2−|Σ|

4k/5 /m

(4/5−o(1))k

)

All that’s left is to union bound over the choices for (Φ, π, h). Using that 2 ≤ |F| ≤ 2|Γ| |Γ| ≤ |Σ|3k/4 , and |Σ| = mω(1) , we have 1. (|F|d )m|Γ| ≤ 2|Σ| 2

(3/4+o(1))k

o(k)

2. |F|O((md) ) ≤ 2|Σ| 3. 2md+1 = 2|Σ|

o(1)

, d ≤ mO(1) ,

choices for Φ = {ϕi : Γ → Fd }i∈[m] .

choices for π : Fmd → Fmd .

choices for h : {0, 1, . . . , md} → {0, 1}. (3/4+o(1))k

So the total number of choices for (Φ, π, h) is 2|Σ| . Using Claim 6.5 we know that for a fixed (4/5−o(1))k −|Σ| choice of (Φ, π, h), with probability at least 1 − 2 over the choice of F, Pr

b∼PH,F

−

h i h dist’ Ψ π ϕ(b1 )∥ . . . ∥ϕ(bm ) , L = 1 Pr

b∼QH,F

h i h dist’ Ψ π ϕ(b1 )∥ . . . ∥ϕ(bm ) , L = 1 < |Σ|−k/10 .

Thus with probability at least 1 − 2−|Σ|

(4/5−o(1))k

(3/4+o(1))k

· 2|Σ|

> 1 − 2−|Σ|

Ω(k)

over the choice of F, every choice of (Φ, π, h) satisfies Pr

b∼PH,F

−

6.2

h i h dist’ Ψ π ϕ(b1 )∥ . . . ∥ϕ(bm ) , L = 1 Pr

b∼QH,F

h i h dist’ Ψ π ϕ(b1 )∥ . . . ∥ϕ(bm ) , L = 1 < |Σ|−k/10 .

Low Degree Polynomial Algorithms

In this sub-section we rule out low degree polynomial algorithms for Problem 1, up to a nearly optimal degree cutoff. As in Section 6.1, such a lower bound is possible because of the massive entropy coming from the random functions in F; the signal-to-noise ratio is very small. Input Formulation. Recall Problem 1 (which is just the corruption-free version of the decision problem in Conjecture 3.1, the LARP-CSP Conjecture): Problem 1 (Restated). Let H be any (1−o(1), n1−o(1) )-expanding (m, n, k)-matrix, where k = (log n)Θ(1) Θ(1) and m ≤ no(k) . Let Σ, Γ be any alphabets satisfying |Σ| = (nm)log (nm) and |Γ| ≤ |Σ|3k/4 . Sample m random functions fi : Σk → Γ, and let F be the set of all fi . The task is to distinguish between the following two distributions. 1. Null distribution Q: (H, F, b), where b ∈ Γm is sampled uniformly at random. 2. Planted distribution P: (H, F, b), where we sample s ∈ Σn at random and set bi = fi (sNH (i,1) , . . . , sNH (i,k) ). To analyze this problem in terms of low degree polynomials, we need to find the right input formulation. Indeed if we only examine the pair (H, b) then b is statistically random, because each fi is a random function. We will instead represent the problem using a carefully chosen representation of the set of all tuples (σ1 , . . . , σk ) ∈ Σk such that there exists an i ∈ [m] with fi (σ1 , . . . , σk ) = bi . This succinctly combines the information contained in F and b, and it aligns with the fact that Problem 1 can be viewed equivalently as a planted hypergraph problem. Concretely speaking, via the randomness of the functions fi , Problem 1 is equivalent to the following: Problem 2. Let H be any (1 − o(1), n1−o(1) )-expanding (m, n, k)-matrix, where k = (log n)Θ(1) and Θ(1) m ≤ no(k) . Let Σ, Γ be any alphabets satisfying |Σ| = (nm)log (nm) and |Γ| ≤ |Σ|3k/4 . Define X := {(j1 , . . . , jk ) : ∃i ∈ [m] s.t. the nonzero entries of Hi are in columns j1 , . . . , jk }. Sample a hypergraph K = (V, E) with vertex set V = [n] × Σ, where the edge set E is sampled in one of two ways: 1. Null distribution Q: For all (j1 , . . . , jk ) ∈ X , for all (σj1 , . . . , σjk ) ∈ Σk , add the edge ((j1 , σj1 ), . . . , (jk , σjk )) independently with probability 1/|Γ|. 2. Planted distribution P: Perform the same procedure as in distribution Q. Then sample s ∈ Σk at random, and for all (j1 , . . . , jk ) ∈ X add the edge ((j1 , sj1 ), . . . , (jk , sjk )) if it doesn’t already exist. 36

The task is to determine, given (H, K), which distribution K was sampled from. Remark 6.6. The pair (H, K) contains significantly less information than the tuple (H, F , b), because in Problem 1 we are given the entire truth table for each function fi whereas in this problem we only learn, for all i ∈ [m], the set of all (σj1 , . . . , σjk ) such that fi (σj1 , . . . , σjk ) = bi . But all of the lost information is “irrelevant,” in the sense that we can efficiently solve Problem 2 using an oracle for Problem 1 by just re-sampling the missing truth table entries from an appropriate distribution to simulate the tuple (H, F , b). Interpretation as a Vector Over the Reals. We assume that our low degree polynomial algorithms take as input the real-valued indicator vector for (H, K). In particular, H is represented over the reals by mapping 0 to 0 and 1 to 1, and K is represented as vector with one coordinate for every tuple ((j1 , sj1 ), . . . , (jk , sjk )), where the coordinate is set to 0 if the corresponding hyperedge is not present in K and 1 if the corresponding hyperedge is present in K. This is the natural formulation used to prove lower bounds for planted graph and hypergraph problems [MVW24, DMW25]. Low Degree Polynomial Algorithms. Consider an arbitrary hypothesis testing problem, with a null distribution Q over real vectors Y and a planted distribution P over real vectors Y of the same length. As discussed in [Hop18, KWB19] a standard way to formalize the distinguishing power of a polynomial g is to examine the ratio EY ∼P [g(Y )] − EY ∼Q [g(Y )] p . VarY ∼Q [g(Y )]

(4)

If this ratio is large, then g(Y ) will typically be much larger under the planted distribution than under the null distribution, even after accounting for the random fluctuations in the output of g(Y ) under the null distribution. The degree-d advantage17 is defined as EY ∼P [g(Y )] − EY ∼Q [g(Y )] p . g is a degree ≤d polynomial VarY ∼Q [g(Y )] max

We say that degree-≤ d polynomials fail to distinguish between P and Q when the degree-d advantage is o(1) [Hop18, KWB19]. In many ways degree-≤ d polynomials are a proxy for “combinatorial” algorithms O(1) n [KWB19], so if degree-≤ d polynomials are ineffective for the hypothesis that run in time nd/ log O(1) n time “combinatorial” algorithms are also ineffective, where n testing problem this suggests that nd/ log is the number of coordinates in Y . Now we specialize these ideas for Problem 2. Observe that H is the same in both the null and planted distributions, so we can assume without loss of generality that our polynomial does not depend on H. We know that all tuples ((j1 , σj1 ), . . . , (jk , σjk )) such that (j1 , . . . , jk ) ̸∈ X will never appear as an edge in K, so we can also assume without loss of generality that our polynomial does not depend on these. In light of this, define Y as the length m′ = m|Σ|k real-valued indicator vector for the remaining possible hyperedges, i.e. the tuples ((j1 , σj1 ), . . . , (jk , σjk )) such that (j1 , . . . , jk ) ∈ X . We have one coordinate in Y for each of these tuples; the coordinate is set to 0 if the corresponding hyperedge is not present in K and 1 if the corresponding hyperedge is present in K. We may assume without loss of generality that EY ∼Q [g(Y )] = 0, because if EY ∼Q [g(Y )] ̸= 0 then the polynomial g ′ = g − EY ∼Q [g(Y )] has the same ratio (4) and degree, but satisfies EY ∼Q [g ′ (Y )] = 0. Thus we can rewrite (4) as E [g(Y )] p Y ∼P . EY ∼Q [g(Y )2 ] 17

In some works this is referred to as the “norm of the degree-d likelihood ratio.”

Because every coordinate of Y , even after normalization (see below), will either equal x or y, we can x also assume without loss of generality that g is multilinear. This is because every factor Y((j 1 ,σj1 ),...,(jk ,σjk )) with x ̸= 1 can be replaced with a linear function (aY((j1 ,σj1 ),...,(jk ,σj )) + b), where a and b are chosen so k that the linear function and the original factor agree when Y((j1 ,σj1 ),...,(jk ,σj )) is either x or y. k All of this is to say that, if we want to show that the degree-d advantage for Problem 2 is o(1), it will suffice to prove that EY ∼P [g(Y )] max p = o(1), EY ∼Q [g(Y )2 ] where the optimization ranges over all degree-≤ d multilinear polynomials g such that EY ∼Q [g(Y )] = 0. Normalization. To simplify the behavior of g(Y ) under the null distribution Q, we define a normalization mapping ϕ : 0, 1 → R that will be applied to each coordinate of Y . Recall that under Q, every » coordinate p −1 −1 of Y is sampled independently from Ber(|Γ| ). Setting p := |Γ| , we define ϕ as ϕ(0) := − 1−p and » 1−p ϕ(1) := p . This gives, for all coordinates ((j1 , σ1 ), . . . , (jk , σk )), EY ∼Q [ϕ(Y((j1 ,σj1 ),...,(jk ,σj )) )] = −

…

p · (1 − p) + 1−p

1−p ·p=0 p

(5)

and EY ∼Q [ϕ(Y((j1 ,σj1 ),...,(jk ,σj )) )2 ] = k

p 1−p · (1 − p) + · p = p + (1 − p) = 1. 1−p p

(6)

Let Y (ϕ) be shorthand for the vector obtained by applying ϕ to each coordinate of Y . Normalization is a linear mapping, so we can assume without loss of generality that our polynomials g take as input Y (ϕ) ; any degree d polynomial with input Y can be converted into a degree d polynomial with input Y (ϕ) and identical output distribution. Recall that Y will be of length m′ = m|Σ|k . We make use of the following simple but powerful lemma. Lemma 6.7 (Based on [Hop18, KWB19], specialized to Problem 2). Let Q and P be the null and planted distributions, respectively,qfrom Problem 2, and let ϕ be the normalization mapping defined as ϕ(0) := q Ä ′ ä −1 |Γ|−1 m − 1−|Γ|−1 and ϕ(1) := 1−|Γ| . For any degree cutoff d ≤ m′ , let c be the length- ≤d − 1 vector of |Γ|−1 expected values, under the distribution P, for all multilinear monomials of degree at least 1 and at most d in the coordinates of Y (ϕ) . If ∥c∥2 = o(1), then the degree-d advantage for Problem 2 is o(1). Proof. As established previously, it will suffice to show that ∥c∥2 = o(1) implies EY ∼P [g(Y (ϕ) )] max » = o(1), EY ∼Q [g(Y (ϕ) )2 ] where the optimization ranges over all degree-≤ d multilinear polynomials g such that EY ∼Q [g(Y (ϕ) )] = 0. P ′ Let ĝ be the length- di=1 mi vector of coefficients for a degree-≤ d multilinear polynomial g in the coordinates of Y (ϕ) . By normalization, we know that the expected value for each monomial under Q is zero, so if ET ∼P [g(T (ϕ) )] = 0 then the constant term is zero. As such we omit the constant term from ĝ. 38

By definition of ĝ and c, we have EY ∼P [g(Y (ϕ) )] = ⟨ĝ, c⟩, where ⟨·, ·⟩ is the standard inner product. Now we analyze EY ∼Q [g(Y (ϕ) )2 ]. For a multilinear monomial M ∈ M(m′ , d), we know by normalization that EY ∼Q [M (Y (ϕ) )2 ] = 1. For two monomials M ̸= M ′ , we know that EY ∼Q [M (Y (ϕ) )M ′ (Y (ϕ) )] = 0, because the product must depend linearly on at least one coordinate of Y (ϕ) , and this normalized coordinate has an expected value of zero independently of all other coordinates. Thus if we index ĝ by the non-constant multilinear monomials M ∈ M(m′ , d), X ĝM ĝM ′ EY ∼Q [M (Y (ϕ) )M ′ (Y (ϕ) )] EY ∼Q [g(Y )2 ] = M,M ′ ∈M(m′ ,d) such that M,M ′ ̸=1

2 ĝM

M ∈M(m′ ,d) such that M ̸=1

=⟨ĝ, ĝ⟩. This gives EY ∼P [g(Y (ϕ) )] ⟨ĝ, c⟩ max » = max p . (ϕ) 2 ⟨ĝ, ĝ⟩ EY ∼Q [g(Y ) ] This is maximized when ĝ is a positive scalar multiple of c, in which case the above quantity is ∥c∥2 . So if ∥c∥2 = o(1) then the degree-d advantage is o(1). 6.2.1

The Low Degree Polynomial Lower Bound

Our lower bound may be stated as follows. It’s nearly tight, as there exists a trivial degree-n logO(1) n algorithm that solves Problem 2. Theorem 6.8. The degree-n0.99 advantage for Problem 2 is o(1). In other words, for all degree-≤ n0.99 polynomials g, EY ∼P [g(Y )] − EY ∼Q [g(Y )] p = o(1). VarY ∼Q [g(Y )] ä Ä ′ Proof. By Lemma 6.7, it will suffice to show that ∥c∥2 = o(1), where c is the length- ≤nm0.99 − 1 vector of expected values, under the distribution P, for all multilinear monomials of degree at least 1 and at most ≤ n0.99 in the coordinates of Y (ϕ) . This is equivalent to showing that ∥c∥22 = o(1), or in other words X EY ∼P [M (Y (ϕ) )]2 . (7) M ∈M(m′ ,n0.99 ) such that M ̸=1

is bounded as o(1). We begin by writing the expected value for each monomial in terms of the probability that the planted edges fall entirely within the monomial. Claim 6.9. Let M ∈ M(m′ , n0.99 ) be any non-constant multilinear monomial, and write M as (ϕ)

Π((j1 ,σj1 ),...,(jk ,σj ))∈S Y((j1 ,σj ),...,(jk ,σj )) , k

where S ⊂ ([n] × Σ)k is a subset of the edges represented by Y (ϕ) . Then h i EY ∼P [M (Y (ϕ) )] ≤ |Γ||S|/2 · Pr σjℓ = sjℓ for all ℓ ∈ [k] and ((j1 , σj1 ), . . . , (jk , σjk )) ∈ S . Y ∼P

Proof. We have that EY ∼P [M (Y (ϕ) )] = i h EY ∼P M (Y (ϕ) ) there exists ℓ ∈ [k] and ((j1 , σj1 ), . . . , (jk , σjk )) ∈ S such that σjℓ ̸= sjℓ i h · Pr there exists ℓ ∈ [k] and ((j1 , σj1 ), . . . , (jk , σjk )) ∈ S such that σjℓ ̸= sjℓ Y ∼P i h + EY ∼P M (Y (ϕ) ) σjℓ = sjℓ for all ℓ ∈ [k] and ((j1 , σj1 ), . . . , (jk , σjk )) ∈ S i h · Pr σjℓ = sjℓ for all ℓ ∈ [k] and ((j1 , σj1 ), . . . , (jk , σjk )) ∈ S . Y ∼P

For the first term, we condition on at least one edge in the monomial being outside of the planted set of edges. By Equation (5), the expected value for the variable corresponding to this edge is zero, independently of the other variables. So the first term is zero. For the second term, we condition on all edges in the monomial being inside of the planted set of edges. q 1−|Γ|−1 |Γ| . This gives

Therefore every variable in the monomial will equal ϕ(1) =

h i EY ∼P M (Y (ϕ) ) σjℓ = sjℓ for all ℓ ∈ [k] and ((j1 , σj1 ), . . . , (jk , σjk )) ∈ S =(ϕ(1))|S| =

1 − |Γ|−1 |Γ|−1

|S|

» |S| ≤ |Γ| h i Multiplying this by PrY ∼P σjℓ = sjℓ for all ℓ ∈ [k] and ((j1 , σj1 ), . . . , (jk , σjk )) ∈ S completes the proof. Now we bound the probability that all edges in a given monomial are inside of the planted set of edges. Here we appeal to the expansion of H. Claim 6.10. Let M ∈ M(m′ , n0.99 ) be any non-constant multilinear monomial, and write M as (ϕ)

Π((j1 ,σj1 ),...,(jk ,σj ))∈S Y((j1 ,σj ),...,(jk ,σj )) , k

where S ⊂ ([n] × Σ)k is a subset of the hyperedges represented by Y (ϕ) . Then h i Pr σjℓ = sjℓ for all ℓ ∈ [k] and ((j1 , σj1 ), . . . , (jk , σjk )) ∈ S ≤ |Σ|−(1−o(1))k|S| . Y ∼P

Proof. First we argue that if there exist two distinct ((j1 , σj1 ), . . . , (jk , σjk )), ((j1′ , σj′ ′ ), . . . , (jk′ , σj′ ′ )) ∈ S 1 k such that jℓ = jℓ′ for all ℓ ∈ [k], then h i Pr σjℓ = sjℓ for all ℓ ∈ [k] and ((j1 , σj1 ), . . . , (jk , σjk )) ∈ S = 0 ≤ |Σ|−(1−o(1))k|S| . Y ∼P

This is because, by the distinctness assumption, there must exist an ℓ ∈ [k] such that σjℓ ̸= σj′ ′ . But because ℓ jℓ = jℓ′ , the event in the probability statement only occurs if sjℓ = σjℓ and sjℓ = σj′ ℓ and thus sjℓ ̸= sjℓ , which is not possible. So assume that every tuple ((j1 , σj1 ), . . . , (jk , σjk )) ∈ S has a distinct sub-tuple (j1 , . . . jk ). Now because H is a (1 − o(1), n1−o(1) )-expander, and |S| ≤ n0.99 < n1−o(1) by assumption, the set I = {j : there exists ℓ ∈ [k] and ((j1 , σj1 ), . . . , (jk , σjk )) ∈ S such that j = jℓ } 40

has cardinality at least (1 − o(1))k|S|. Over the randomness of s ∈ Σn , this implies i h Pr sjℓ = σjℓ for all ℓ ∈ [k] and ((j1 , σj1 ), . . . , (jk , σjk )) ∈ S = (1/|Σ|)(1−o(1))k|S| . Y ∼P

Now all that’s left is to compute the sum of squared expectations over all monomials. Start with (7): X EY ∼P [M (Y (ϕ) )]2 M ∈M(m′ ,n0.99 ) such that M ̸=1

and then apply Claim 6.9 (where SM is the set of variables in monomial M ): Å iã2 h X . |Γ||SM |/2 · Pr σjℓ = sjℓ for all ℓ ∈ [k] and ((j1 , σj1 ), . . . , (jk , σjk )) ∈ SM = Y ∼P

M ∈M(m′ ,n0.99 ) such that M ̸=1

By Claim 6.10 this becomes X

|Γ||SM |/2 · |Σ|−(1−o(1))k|SM |

ä2

M ∈M(m′ ,n0.99 ) such that M ̸=1

Each of the terms only depends on the size of the (multilinear) monomial. Because there are m′ = m|Σ|k variables in Y , we can rewrite the above as Ç å ä2 X m|Σ|k Ä t/2 = |Γ| · |Σ|−(1−o(1))kt t 1≤t≤n0.99 ät Ä ä2 X Ä ≤ m|Σ|k |Γ|t/2 · |Σ|−(1−o(1))kt 1≤t≤n0.99

≤

Ä ät Ä ä2 m|Σ|k |Σ|3kt/8 · |Σ|−(1−o(1))kt

(|Γ| ≤ |Σ|3k/4 )

|Σ|(1+o(1))kt |Σ|−((5/4)−o(1))kt

(|Σ| = mω(1) )

1≤t≤n0.99

≤

X 1≤t≤n0.99

≤

|Σ|−((1/4)+o(1))kt

1≤t≤n0.99

≤|Σ|−Ω(k) . Putting everything together, the degree-n0.99 advantage for Problem 2 is o(1). Remark 6.11. The only place in the proof where we use the expansion of H is in Claim 6.10. As such, the same lower bound proof actually works for polynomials of degree all the way up to the expansion cutoff.

6.3

Polynomial Calculus Refutations

In this section we prove lower bounds for Problem 1 against the refutation version of the polynomial calculus proof system. Recall that in this setting, the adversary is given a tuple (H, F , b), and the goal is to certify that there does not exist a secret vector s ∈ Σn such that bi = fi (sNH (i,1) , . . . , sNH (i,k) ) for all i ∈ [m]. Our lower bounds are similar to those given by Applebaum and Lovett [AL16] for Goldreich’s PRG. To get started, recall Problem 1 (which as explained before is just the corruption-free version of the decision problem in Conjecture 3.1, the LARP-CSP Conjecture): 41

Problem 1 (Restated). Let H be any (1−o(1), n1−o(1) )-expanding (m, n, k)-matrix, where k = (log n)Θ(1) Θ(1) and m ≤ no(k) . Let Σ, Γ be any alphabets satisfying |Σ| = (nm)log (nm) and |Γ| ≤ |Σ|3k/4 . Sample m random functions fi : Σk → Γ, and let F be the set of all fi . The task is to distinguish between the following two distributions. 1. Null distribution Q: (H, F, b), where b ∈ Γm is sampled uniformly at random. 2. Planted distribution P: (H, F, b), where we sample s ∈ Σn at random and set bi = fi (sNH (i,1) , . . . , sNH (i,k) ). For the lower bound in this section, we assume that |Σ| is a power of two. Formalizing the Proof System. Polynomial calculus refutations work as follows [CEI96]. We first initialize a system of polynomials g1 (X) = 0, . . . gm (X) = 0 in a set of variables X over some field. A new polynomial equation g(X) = 0 is appended to the system by either 1. Setting g(X) = g ′ (X) + g ′′ (X) for any polynomials g ′ (X), g ′′ (X) already in the system. 2. Setting g(X) = Xi · g ′ (X) for any variable Xi and any polynomial g ′ (X) already in the system. The goal of a refutation is to derive the statement 1 = 0 via these operations; such a derivation is only possible if the original system was unsatisfiable, because the derivation rules cannot derive an unsatisfiable system from a satisfiable one. As in the lower bounds given by Applebaum and Lovett [AL16], we allow an adversary to have nondeterministic power when choosing the derivation steps she would like to perform. So the only measure of complexity of the proof will be its size, i.e. the total number of monomials in the proof after all polynomials are written in expanded form. This is natural in the sense that any algorithm executing a polynomial calculus refutation in the most natural manner will have to, at the very least, write out all of these monomials.18 For most applications, the initial system we’d like to refute already has a natural field structure. But for Problem 1 the functions in F are completely random. To handle this discrepancy, we fix the field F2 and then allow an adversary unbounded time to choose the best embedding from Σ, Γ into vectors over F2 . We restrict ourselves to F2 because the polynomials representing each constraint bi = fi (sNH (i,1) , . . . , sNH (i,k) ) will be of minimal degree when interpreted over F2 as opposed to a field of larger order, which is helpful for an adversary. Moreover, the random functions in F have no affinity for any particular field; indeed the only structured portion of Problem 1 for our cryptographic applications will be the matrix H, which is of low complexity specifically with respect to F2 . Now we formally define polynomial calculus refutations for Problem 1. Recall that we assume |Σ| is a power of two. Definition 6.12 (Polynomial Calculus Refutation for Problem 1). The refutation algorithm proceeds as follows. Let X be a set of n variables over Σ, interpreted as entries of the unknown secret s ∈ Σn , and assume that the adversary has access to the entire tuple (H, F , b). log |Σ|

1. The adversary non-deterministically finds the best (bijective) embeddings ϕ1 , . . . , ϕn : Σ → F2 2 for each variable Xj . Let X′ be a matrix of n log2 |Σ| variables over F2 such that X′j,1 , . . . , X′j,log |Σ| 2 represents Xj . 18

A smarter algorithm could conceivably exploit nontrivial cancellations that occur without needing to fully distribute the polynomials. But it appears that the massive entropy coming from our random functions, in addition to the fact that each one is sampled independently at random, rules out such cancellations. In any case, counting the number of monomials in the polynomials’ distributed form is standard for polynomial calculus lower bounds [AL16].

2. The adversary initializes a polynomial system over X′ by appending, for each i ∈ [m], the constraint fi′ (X′ ) = 0, where fi′ is the unique polynomial over F2 such that (a) fi′ is supported on the variable set X′NH (i,1),1 , . . . , X′NH (i,1),log |Σ| , X′NH (i,2),1 , . . . , X′NH (i,k),log |Σ| . 2

(b) For all (σ1 , . . . , σk ) ∈ Σk such that fi (σ1 , . . . , σk ) = bi , we have fi′ (ϕNH (i,1) (σ1 ), . . . , ϕNH (i,k) (σk )) = 0. (c) For all other inputs, fi′ equals 1. 3. The adversary (non-deterministically) appends a new polynomial g(X′ ) = 0 to the system, by either (a) Setting g(X′ ) = g ′ (X′ ) + g ′′ (X′ ) for any polynomials g ′ (X′ ), g ′′ (X′ ) already in the system. (b) Setting g(X′ ) = X′j,ℓ · g ′ (X′ ) for any variable X′j,ℓ and any polynomial g ′ (X′ ) already in the system. The goal of the adversary is derive the equation 1 = 0, and we measure the size of the proof by the number of nonzero monomials in the distributed form for each polynomial written at each step. 6.3.1

Proving the Lower Bound

As stated before, our techniques are similar to those used by [AL16] to prove polynomial calculus lower bounds for Goldreich’s PRG. Informally speaking, we show that any polynomial calculus refutation for Problem 1 must have size at least exp n0.99 . Theorem 6.13.© Assume that |Σ| is a power of two and that n is sufficiently large. With probability 1 − ¶ Ω(k) exp −|Σ| over the choice of functions in F, there does not exist a polynomial calculus refutation (in the sense of Definition 6.12) for a tuple (H, F, b) drawn from the null distribution Q in Problem 1 0.99 containing less than exp n nonzero monomials. Before proving the theorem, we give a basic definition and import two key lemmas from [IPS99, AR01]. Definition 6.14 (Rational Degree). The rational degree of a polynomial g : Fw 2 → F2 is the smallest integer d such that there exist degree-≤ d polynomials p, q : Fw → F , not both zero, such that pg = q. 2 2 At an intuitive level, a polynomial g with low rational degree can be “converted” into a low degree polynomial for the purposes of a polynomial calculus refutation, even if the degree of g was originally very high. Rational degree will be of central importance in our lower bound, because demonstrating that the polynomials in our system have high rational degree will allow us to apply the following lemma. Lemma 6.15 (Simplified version of Theorem 3.8 from [AR01]). Suppose we have a polynomial system g1 (X) = 0, . . . , gm (X) = 0 over a set X of variables in F2 . Assume that 1. Every polynomial depends on at most k ′ variables. 2. For all subsets G of at least 1 polynomial and at most t polynomials, G depends on at least (1−o(1))tk ′ distinct variables. 3. Every polynomial has rational degree Ω(k ′ ). Then any polynomial calculus refutation of the system g1 (X) = 0, . . . , gm (X) = 0 has at least one monomial of degree Ω(tk ′ ). 43

Remark 6.16. The conditions we impose on the polynomial system in this lemma are equivalent to those in Theorem 3.8 from [AR01], but phrased slightly differently. As stated by Alekhnovich and Razborov [AR01], the lemma actually requires the polynomial system to have strong boundary expansion, but our notion of expansion in Item 2 immediately implies the required boundary expansion. Additionally, [AR01] require the polynomials to satisfy a condition they call immunity, which is implied by our notion of rational degree. We adopt the rational degree perspective because it aligns with the techniques used by [AL16]. The lemma below allows us to say that the existence of a large monomial in the proof implies that the proof itself is very long. Lemma 6.17 ([IPS99] Theorem 6.2). If G is a set of polynomials in n variables, each of degree at most d, and G has a polynomial calculus refutation √ with M nonzero monomials, then G has a polynomial calculus refutation of degree at most max(d, 2 n log M + 1). Now we begin working towards a proof of Theorem 6.13. Below we show that, even though an adversary log |Σ| can choose arbitrary embeddings from Σ to F2 2 for each variable representing the secret s in Problem 1, all of the constraints will have high rational degree with high probability. The lemma just formalizes the intuition that the random functions in F have far too much entropy to be summarized by a low degree polynomial. Lemma 6.18. Let n be a parameter, and let k = (log n)Θ(1) and m ≤ no(k) . Choose any alphabets Σ, Γ Θ(1) 3k/4 . Sample m random functions f : Σk → Γ. Then satisfying |Σ| = (nm)log¶ (nm) and i © |Γ| ≤ |Σ| Ω(k) with probability 1 − exp −|Σ| , there does not exist an index i ∈ [m], a value bi ∈ Γ, and a set of log |Σ|

(bijective) embeddings ϕ1 , . . . , ϕk : Σ → F2 2 fi′ is the unique polynomial over F2 such that

2 |Σ| such that fi′ has rational degree less than k log 100 . Here

1. fi′ is supported on the variable set X′NH (i,1),1 , . . . , X′NH (i,1),log |Σ| , X′NH (i,2),1 , . . . , X′NH (i,k),log |Σ| . 2

2. For all (σ1 , . . . , σk ) ∈ Σk such that fi (σ1 , . . . , σk ) = bi , we have fi′ (ϕNH (i,1) (σ1 ), . . . , ϕNH (i,k) (σk )) = 0. 3. For all other inputs, fi′ equals 1. Proof. First we give a sharp tail bound on the probability that, for a single choice of index i, value bi , embeddings ϕ1 , . . . , ϕk , and low degree polynomials p, q, a random function fi will satisfy pfi = q. Then we union bound over all choices of i, bi , ϕ1 , . . . , ϕk , p, q to complete the proof. Claim 6.19. Fix an index i ∈ [m], a value bi ∈ Γ, a set of (bijective) embeddings ϕ1 , . . . , ϕk : Σ → log |Σ| k log |Σ| 2 |Σ| F2 2 , and two degree-≤ k log polynomials p, q : F2 2 → F2 , at least one of which is nonzero. 100 k → Γ, and define f ′ as in the statement of the lemma. With Then sample a random function f : Σ i ¶ ©i 24 probability 1 − exp −Ω(|Σ| 100 k ) , we have p · fi′ ̸= q. Proof. First consider the case that p is identically zero. Then p·fi′ is identically zero, in which case p·fi′ = q if and only if q is identically zero. This contradicts the assumption in the claim. Now assume that p is nonzero and q is any (potentially identically zero) polynomial, and let S be the set of points for which p equals one. For every point in S, the evaluation of p · fi′ is equal to the evaluation of fi′ , so a necessary condition to have p · fi′ = q is for fi′ to equal q on all points in S.

Because of the degree bound on p, we have that the truth table of p is a member of the Reed-Muller code k log2 |Σ| 2 |Σ| RM(k log2 |Σ|, k log 100 ). By Lemma 2.9, the minimum distance of RM(k log2 |Σ|, 100 ) is 2k log2 |Σ|−

k log2 |Σ| 100

= 2 100 k log2 |Σ| ,

which implies that |S| ≥ 2 100 k log2 |Σ| . Since bi , the (bijective) embeddings ϕ1 , . . . , ϕk , and the polynomial p were all fixed before sampling fi′ , each point in S has the evaluation of fi′ equal to zero independently with probability 1 − 1/|Γ|. Since q was also fixed before sampling fi , the probability that fi′ and q have equal evaluations on all points in S is at most (1 − 1/|Γ|)|S| . Using that |Γ| ≤ |Σ|3k/4 , the assumption that Σ is sufficiently large, and the fact that (1 − 1/x)x < 1/2 for sufficiently large x, the probability that fi and q have equal evaluations for all points in S is upper bounded as 99 k log |Σ| 2

(1 − 1/|Γ|)2 100

99 k log |Σ| 2

≤(1 − |Σ|−3k/4 )2 100 24 k log |Σ| 2

<(1/2)2 100 24 k

=2−|Σ| 100

All that’s left is to union bound over all choices of i ∈ [m], bi ∈ Γ, bijective embeddings ϕ1 , . . . , ϕk : log |Σ| k log |Σ| 2 |Σ| Σ → F2 2 , and degree-≤ k log polynomials p, q : F2 2 →F2 (we also count the extraneous case 100 that both p and q are zero). Using the standard approximation that xy < (3x/y)y , there are 1. m choices for the index i. 2. (|Σ|!)k ≤ |Σ|k|Σ| choices for the embeddings ϕ1 , . . . , ϕk 3. 2 4. 2

k log |Σ| ( k log22 |Σ| ) 100

≤ 2300 ≤ 2300

k log2 |Σ| 100

< 2|Σ| 10 choices for the polynomial p. k

< 2|Σ| 10 choices for the polynomial q.

Using that k = (log n)Θ(1) = (log m)Θ(1) and |Σ| = mω(1) , and assuming |Σ| is sufficiently large, there are k

k/9

m · |Σ|k|Σ| · 2|Σ| 10 · 2|Σ| 10 < 2|Σ|

total choices. So by Claim 6.19 and the definition of rational degree, the probability that there exists an log |Σ| index i ∈ [m], a value bi ∈ Γ, and a set of (bijective) embeddings ϕ1 , . . . , ϕk : Σ → F2 2 such that fi′ k log2 |Σ| has rational degree less than 100 is at most 2|Σ|

k/9

Now we are ready to prove the lower bound on polynomial calculus refutations.

Proof of Theorem 6.13. Condition¶ on the event © in Lemma 6.18 occurring for the set of functions F , which Ω(k) occurs with probability 1 − exp −|Σ| . In this case, every function fi′ derived from each (fi , bi ) pair will have rational degree Ω(k log2 |Σ|), regardless of what the bi values are and regardless of what log |Σ| embeddings ϕ1 , . . . , ϕn : Σ → F2 2 the adversary picks. ′ = 0, which is the system (over F ) for which Now examine the polynomial system f1′ = 0, . . . , fm 2 the adversary wishes to find a short refutation. Because log2 |Σ| = logΘ(1) n, we know that there will be n log2 |Σ| = n logΘ(1) n variables. We know by assumption on the matrix H and by Lemma 6.18 that the polynomial system satisfies the preconditions of Lemma 6.15 for an expansion cutoff t = n1−o(1) , so any polynomial calculus refutation must have at least one nonzero monomial of degree at least n1−o(1) . Now suppose for contradiction that there exists a polynomial calculus refutation for this system having less than exp n0.99 nonzero monomials. Observe that, because we are working over F2 , every polynomial fi′ can have degree at most the number of variables it depends on, which is logΘ(1) n. By Lemma 6.17, all of this taken together with the assumption that the problem size is sufficiently large implies that there is a polynomial calculus refutation of degree at most Å °» § ã Θ(1) Θ(1) 0.99 max log n, 2 n log ·n + 1 = n0.995+o(1) < n1−o(1) , which is not possible.

References

[ABW10]

Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 171–180, 2010. 1, 2, 3, 6, 11

[AL16]

Benny Applebaum and Shachar Lovett. Algebraic attacks against random local functions and their countermeasures. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 1087–1100, 2016. 1, 5, 6, 41, 42, 43, 44

[AL17]

Vedat Levi Alev and Lap Chi Lau. Approximating unique games using low diameter graph decomposition. arXiv preprint arXiv:1702.06969, 2017. 2

[Ale03]

Michael Alekhnovich. More on average case vs approximation complexity. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 298–307. IEEE, 2003. 1

[App12]

Benny Applebaum. Pseudorandom generators with long stretch and low locality from random local one-way functions. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 805–816, 2012. 10

[AR01]

Michael Alekhnovich and Alexander A Razborov. Lower bounds for polynomial calculus: Non-binomial case. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 190–199. IEEE, 2001. 43, 44

[AR16]

Benny Applebaum and Pavel Raykov. Fast pseudorandom functions based on expander graphs. In Theory of Cryptography Conference, pages 27–56. Springer, 2016. 4

[ASW15]

Emmanuel Abbe, Amir Shpilka, and Avi Wigderson. Reed-muller codes for random erasures and errors. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 297–306, 2015. 14

[ASY20]

Emmanuel Abbe, Amir Shpilka, and Min Ye. Reed–muller codes: Theory and algorithms. IEEE Transactions on Information Theory, 67(6):3251–3277, 2020. 14

[BBH+ 20]

Matthew Brennan, Guy Bresler, Samuel B Hopkins, Jerry Li, and Tselil Schramm. Statistical query algorithms and low-degree tests are almost equivalent. arXiv preprint arXiv:2009.06107, 2020. 5

[BBK+ 21]

Afonso S Bandeira, Jess Banks, Dmitriy Kunisky, Christopher Moore, and Alex Wein. Spectral planting and the hardness of refuting cuts, colorability, and communities in random graphs. In Conference on Learning Theory, pages 410–473. PMLR, 2021. 5

[BCG+ 12]

Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, and Yuan Zhou. Polynomial integrality gaps for strong sdp relaxations of densest k-subgraph. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 388–405. SIAM, 2012. 2

[BHJK25]

Rares-Darius Buhai, Jun-Ting Hsieh, Aayush Jain, and Pravesh K Kothari. The quasipolynomial low-degree conjecture is false. arXiv preprint arXiv:2505.17360, 2025. 3

[BJRZ24]

Andrej Bogdanov, Chris Jones, Alon Rosen, and Ilias Zadik. Low-degree security of the planted random subgraph problem. In Theory of Cryptography Conference, pages 255–275. Springer, 2024. 5

[BKR23]

Andrej Bogdanov, Pravesh K Kothari, and Alon Rosen. Public-key encryption, local pseudorandom generators, and the low-degree method. In Theory of Cryptography Conference, pages 268–285. Springer, 2023. 5, 11

[BKW03]

Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM (JACM), 50(4):506–519, 2003. 6

[BKW19]

Afonso S Bandeira, Dmitriy Kunisky, and Alexander S Wein. Computational hardness of certifying bounds on constrained pca problems. arXiv preprint arXiv:1902.07324, 2019. 5

[Bra08]

Mark Braverman. Polylogarithmic independence fools ac 0 circuits. Journal of the ACM (JACM), 57(5):1–10, 2008. 6

[BSI99]

Eli Ben-Sasson and Russell Impagliazzo. Random cnfs are hard for the polynomial calculus. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 415–421. IEEE, 1999. 1, 5

[CEI96]

Matthew Clegg, Jeffery Edmonds, and Russell Impagliazzo. Using the groebner basis algorithm to find proofs of unsatisfiability. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 174–183, 1996. 5, 42

[CIKK16]

Marco L Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Learning algorithms from natural proofs. In 31st Conference on Computational Complexity (CCC 2016), pages 10–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2016. 4, 29

[CMMV17] Eden Chlamtáč, Pasin Manurangsi, Dana Moshkovitz, and Aravindan Vijayaraghavan. Approximation algorithms for label cover and the log-density threshold. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 900–919. SIAM, 2017. 1, 2 [CSZ24]

Xue Chen, Wenxuan Shu, and Zhaienhe Zhou. Algorithms for sparse lpn and lspn against low-noise. arXiv preprint arXiv:2407.19215, 2024. 6

[DDL23]

Jian Ding, Hang Du, and Zhangsong Li. Low-degree hardness of detection for correlated erd\h {o} sr\’enyi graphs. arXiv preprint arXiv:2311.15931, 2023. 5

[DH76]

WHITFIELD DIFFIE and MARTIN E HELLMAN. New directions in cryptography. IEEE TRANSACTIONS ON INFORMATION THEORY, 22(6), 1976. 1

[DMW25]

Abhishek Dhawan, Cheng Mao, and Alexander S Wein. Detection of dense subhypergraphs by low-degree polynomials. Random Structures & Algorithms, 66(1):e21279, 2025. 1, 37

[EH25]

Dor Elimelech and Wasim Huleihel. Detecting arbitrary planted subgraphs in random graphs. arXiv preprint arXiv:2503.19069, 2025. 4

[FGKP06]

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. New results for learning noisy parities and halfspaces. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pages 563–574. IEEE, 2006. 6

[FGR+ 17]

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao. Statistical algorithms and a lower bound for detecting planted cliques. Journal of the ACM (JACM), 64(2):1–37, 2017. 5

[FPV15]

Vitaly Feldman, Will Perkins, and Santosh Vempala. On the complexity of random satisfiability problems with planted solutions. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 77–86, 2015. 1, 7

[GGH+ 16] Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM Journal on Computing, 45(3):882–929, 2016. 3 [GHJS25]

Riddhi Ghosal, Isaac M Hair, Aayush Jain, and Amit Sahai. Using the planted clique conjecture for cryptography: Public-key encryption from planted clique and noisy k-lin over expanders. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1921–1932, 2025. 4, 11

[GM84]

Shafi Goldwasser and Silvio Micali. Probabilistic encryption. In Journal of Computer and System Sciences, volume 28(2), pages 270–299. 1984. 1, 2, 13

[Gol00]

Oded Goldreich. Candidate one-way functions based on expander graphs. 2000. 1, 4

[Gri01]

Dima Grigoriev. Linear lower bound on degrees of positivstellensatz calculus proofs for the parity. Theoretical Computer Science, 259(1-2):613–622, 2001. 1, 6

[GS11]

Venkatesan Guruswami and Ali Kemal Sinop. Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with psd objectives. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 482–491. IEEE, 2011. 2

[GTK15]

Shafi Goldwasser and Yael Tauman Kalai. Cryptographic assumptions: A position paper. In Theory of Cryptography Conference, pages 505–522. Springer, 2015. 2

[HKP+ 17]

Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer. The power of sum-of-squares for detecting hidden structures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 720–731. IEEE, 2017. 5

[Hop18]

Samuel Hopkins. Statistical inference and the sum of squares method. Cornell University, 2018. 3, 37, 38

[HR05]

Thomas Holenstein and Renato Renner. One-way secret-key agreement and applications to circuit polarization and immunization of public-key encryption. In Annual International Cryptology Conference, pages 478–493. Springer, 2005. 8, 12, 13

[IPS99]

Russell Impagliazzo, Pavel Pudlák, and Jiri Sgall. Lower bounds for the polynomial calculus and the gröbner basis algorithm. Computational Complexity, 8(2):127–144, 1999. 1, 5, 43, 44

[Jan04]

Svante Janson. Large deviations for sums of partly dependent random variables. Random Structures & Algorithms, 24(3):234–248, 2004. 33

[JLS21]

Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from well-founded assumptions. In STOC, 2021. 3 49

[KMOW17] Pravesh K Kothari, Ryuhei Mori, Ryan O’Donnell, and David Witmer. Sum of squares lower bounds for refuting any csp. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 132–145, 2017. 1, 6 [Kun21]

Dmitriy Kunisky. Hypothesis testing with low-degree polynomials in the morris class of exponential families. In Conference on Learning Theory, pages 2822–2848. PMLR, 2021. 5

[KVWX23] Pravesh Kothari, Santosh S Vempala, Alexander S Wein, and Jeff Xu. Is planted coloring easier than planted clique? In The Thirty Sixth Annual Conference on Learning Theory, pages 5343–5372. PMLR, 2023. 5 [KWB19]

Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. In ISAAC Congress (International Society for Analysis, its Applications and Computation), pages 1–50. Springer, 2019. 5, 37, 38

[KZ17]

Andrei Krokhin and Stanislav Zivny. The constraint satisfaction problem: Complexity and approximability. Schloss Dagstuhl, 2017. 1

[LG24]

Yuetian Luo and Chao Gao. Computational lower bounds for graphon estimation via lowdegree polynomials. The Annals of Statistics, 52(5):2318–2348, 2024. 5

[Lyu05]

Vadim Lyubashevsky. The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 378–389. Springer, 2005. 6

[Man26]

Breaking the alekhnovich barrier via a combinatorial list recovery conjecture. Unpublished Manuscript, 2026. 1, 2

[McE78]

Robert J McEliece. A public-key cryptosystem based on algebraic. 4244(1978):114–116, 1978. 1, 11

[MN24]

Mladen Mikša and Jakob Nordström. A generalized method for proving polynomial calculus degree lower bounds. Journal of the ACM, 71(6):1–43, 2024. 1, 5

[MSZ16]

Eric Miles, Amit Sahai, and Mark Zhandry. Annihilation attacks for multilinear maps: Cryptanalysis of indistinguishability obfuscation over ggh13. In Annual international cryptology conference, pages 629–658. Springer, 2016. 3

[Mul54]

David E Muller. Application of boolean algebra to switching circuit design and to error detection. Transactions of the IRE professional group on electronic computers, (3):6–12, 1954.

Coding Thv,

[MVW24]

Jay Mardia, Kabir Aladin Verchand, and Alexander S Wein. Low-degree phase transitions for detecting a planted clique in sublinear time. In The Thirty Seventh Annual Conference on Learning Theory, pages 3798–3822. PMLR, 2024. 37

[MW16]

Ryuhei Mori and David Witmer. Lower bounds for csp refutation by sdp hierarchies. arXiv preprint arXiv:1610.03029, 2016. 1

[MW25]

Andrea Montanari and Alexander S Wein. Equivalence of approximate message passing and low-degree polynomials in rank-one matrix estimation. Probability Theory and Related Fields, 191(1):181–233, 2025. 5 50

[Nor14]

Jakob Nordström. A (biased) proof complexity survey for sat practitioners. In International Conference on Theory and Applications of Satisfiability Testing, pages 1–6. Springer, 2014. 1, 5

[NW94]

Noam Nisan and Avi Wigderson. Hardness vs randomness. Journal of computer and System Sciences, 49(2):149–167, 1994. 10

[OST18]

I Oliveira, Rahul Santhanam, and Roei Tell. Expander-based cryptography meets natural proofs. Innovations in Theoretical Computer Science (ITCS), 124, 2018. 1, 2, 4, 10, 11, 29, 32

[Rab79]

Michael O Rabin. Digitalized signatures and public-key functions as intractable as factorization. Technical report, 1979. 1

[Raz87]

Alexander A Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41(4):333–338, 1987. 4, 29

[Ree53]

Irving S Reed. A class of multiple-error-correcting codes and the decoding scheme. Technical report, 1953. 13

[Reg09]

Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6):1–40, 2009. 1

[RR94]

Alexander A Razborov and Steven Rudich. Natural proofs. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 204–213, 1994. 4, 29

[RSA78]

Ronald L Rivest, Adi Shamir, and Leonard Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126, 1978. 1

[Sah26]

Amit Sahai. A note on adversary running times. Cryptology ePrint Archive, 2026. 2

[Sch08]

Grant Schoenebeck. Linear level lasserre lower bounds for certain k-csps. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 593–602. IEEE, 2008. 1, 6

[Sho99]

Peter W Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2):303–332, 1999. 1

[Smo87]

Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 77–82, 1987. 4, 29

[SSV16]

Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk. Efficiently decoding reed-muller codes from random errors. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 227–235, 2016. 10, 14, 26, 27

[Ste10]

David Steurer. On the complexity of unique games and graph expansion. Princeton University, 2010. 2

[Val12]

Gregory Valiant. Finding correlations in subquadratic time, with applications to learning parities and juntas. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 11–20. IEEE, 2012. 6

[WEAM19] Alexander Wein, Ahmed El Alaoui, and Cristopher Moore. The kikuchi hierarchy and tensor pca. Journal of the ACM, 2019. 1, 7 51

[Wei22]

Alexander S Wein. Optimal low-degree hardness of maximum independent set. Mathematical Statistics and Learning, 4(3):221–251, 2022. 5

[Wei23]

Alexander S Wein. Average-case complexity of tensor decomposition for low-degree polynomials. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1685–1698, 2023. 5

[YZ16]

Yu Yu and Jiang Zhang. Cryptography with auxiliary input and trapdoor from constant-noise lpn. In Annual International Cryptology Conference, pages 214–243. Springer, 2016. 2

[YZZ24]

Xifan Yu, Ilias Zadik, and Peiyuan Zhang. Counting stars is constant-degree optimal for detecting any planted subgraph. In The Thirty Seventh Annual Conference on Learning Theory, pages 5163–5165. PMLR, 2024. 5

[Zhu20]

Dmitriy Zhuk. A proof of the csp dichotomy conjecture. Journal of the ACM (JACM), 67(5):1– 78, 2020. 1

Record · ID 10285 · SHA-256 eb1fdfcd30bb4e11
Conceptio Open Knowledge Archive — every document is proof-bundled with source, license, and retrieval metadata.