Elette Boyle

Geoffroy Couteau

Niv Gilboa

Yuval Ishai

Lisa Kohl

Peter Scholl

Georoy Couteau

Low-Complexity Weak Pseudorandom Functions in AC0[MOD2]

come

Introduction

This work explores the minimal achievable complexity of weak pseudorandom functions. Roughly speaking, a pseudorandom function (PRF) family [START_REF] Goldreich | How to construct random functions (extended abstract)[END_REF] is a collection of eciently computable functions f k (x), such that a random function from the collection induced by a uniform choice of the key k cannot be eciently distinguished from a truly random function. The existence (or nonexistence) of PRFs in low complexity classes is closely related to questions in computational learning theory [START_REF] Valiant | A theory of the learnable[END_REF][START_REF] Kearns | Cryptographic limitations on learning boolean formulae and nite automata[END_REF]: Indeed, any complexity class rich enough threshold gates) under standard cryptographic assumptions [START_REF] Naor | Number-theoretic constructions of ecient pseudo-random functions[END_REF][START_REF] Naor | Pseudo-random functions and factoring (extended abstract)[END_REF][START_REF] Banerjee | Pseudorandom functions and lattices[END_REF]. In contrast, despite some partial results [START_REF] Viola | The communication complexity of addition[END_REF][START_REF] Akavia | Candidate weak pseudorandom functions in AC 0 o MOD2[END_REF][START_REF] Applebaum | Fast pseudorandom functions based on expander graphs[END_REF][START_REF] Boneh | Exploring crypto dark matter: New simple PRF candidates and their applications[END_REF][START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF], the space in between AC0 and TC0 remains a relatively uncharted territory.

Sparse F 2 -polynomials. Sparse polynomials are a natural object of study in several areas, including computational learning theory. We will be interested in sparse n-variate polynomials over F 2 , namely sums of poly(n) monomials. Sparse F 2 -polynomials can be viewed as the subclass of AC0[MOD2] corresponding to depth-2 circuits that take the XOR of ANDs of inputs. A WPRF in this class would show the hardness of learning sparse F 2 -polynomials under the uniform distribution. We briey survey some relevant known results.

A result of Hellerstein and Servedio [START_REF] Hellerstein | On PAC learning algorithms for rich boolean function classes[END_REF] implies an 2 Õ( √ n) -time PAC learning algorithm (applying to any input distribution) for learning sparse F 2 -polynomials.

In the converse direction, a recent work of Daniely and Vardi [START_REF] Daniely | From local pseudorandom generators to hardness of learning[END_REF] shows that sparse F 2 -polynomials are hard to learn in better than quasipolynomial time, albeit only under a specic non-uniform input distribution (a highly biased Bernoulli distribution), under the conjectured existence of polynomial-stretch local pseudorandom generators [START_REF] Goldreich | Candidate one-way functions based on expander graphs[END_REF][START_REF] Ishai | Cryptography with constant computational overhead[END_REF][START_REF] Applebaum | Pseudorandom generators with long stretch and low locality from random local one-way functions[END_REF]. Finally, Boneh et al. [START_REF] Boneh | Exploring crypto dark matter: New simple PRF candidates and their applications[END_REF] put forward a WPRF candidate in ACC0 that implies 2 Ω(n) -hardness of learning sparse F 3polynomials, again under a special input distribution (uniform over {-1, 1} n ).

To our knowledge, no result is currently known that supports the hardness of learning sparse F 2 -polynomials in any hardness regime under the uniform distribution, or in the subexponential hardness regime under any distribution.

The class AC0 • MOD2. The class AC0 • MOD2 of AC0 on top of parities can be seen as a minimal extension of AC0. Despite its apparent simplicity, it is quite poorly understood. In particular, it is open whether the mod-2 innerproduct function is in this class [START_REF] Servedio | On a special case of rigidity[END_REF]. Akavia et al. [START_REF] Akavia | Candidate weak pseudorandom functions in AC 0 o MOD2[END_REF] put forward the question of WPRFs in AC0 • MOD2 as a second-best alternative to WPRFs in AC0. They presented a candidate construction where f k (x) applies a specic DNF formula (the TRIBES function) to a secret linear mapping A k • x of the input x, and proved resistance against several classes of attacks. However, this candidate was later broken by a quasipolynomial-time algebraic attack [START_REF] Bogdanov | Pseudorandom functions: Three decades later[END_REF] exploiting the low rational degree of functions f k in the family. Namely, there exists a low-degree g for which f k • g = 0 or (f k ⊕ 1) • g = 0. This kind of attacks further rules out the possibility of any WPRF with better than quasipolynomial security that can be computed by depth-2 AC0 circuits over XOR.

Our Contribution

Candidate WPRF by sparse F 2 -polynomials. We present a candidate WPRF in the class of sparse F 2 -polynomials that can be conjectured to have subexponential security. More concretely, we conjecture our candidate to be secure against distinguishers of size T = 2 n ε for a constant ε ≥ 1/8, where n is the input size. To our knowledge, this is the rst proposal for a candidate WPRF in this class. We give several kinds of evidence for the security of our candidate.

First, building on previous works, we show that it has high rational degree. This implies that it cannot be broken by a subexponential algebraic attack (the same attack that breaks the candidate of [START_REF] Akavia | Candidate weak pseudorandom functions in AC 0 o MOD2[END_REF] in quasipolynomial time). Second, we reduce its security to a variable-density variant of the Learning Parity with Noise (LPN) [START_REF] Blum | Cryptographic primitives based on hard learning problems[END_REF] assumption. This assumption is similar to (but essentially incomparable) to the variable-density LPN assumption used in the recent work of Boyle et al. [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF] to build a WPRF in the class of XNF formulas (sparse F 2 -polynomials in the inputs and their negations). Finally, we prove that it cannot be broken by any attack that ts into the framework of linear attacks, a general framework that captures in particular all known attacks against the LPN assumption and its variants. Our analysis builds upon the analysis of [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF]; however, our setting involves additional challenges that require to signicantly rene their proof techniques.

Our candidate WPRF provides an explicit distribution D over sparse nvariate F 2 -polynomials such that the following plausibly holds: no circuit of size 2 n 1/8

, given the values of a secret polynomial p ∈ R D on uniformly random inputs, can predict the value of p on a fresh random input with better than 2 -n 1/8 advantage.

As noted above, the recent work of Daniely and Vardi [START_REF] Daniely | From local pseudorandom generators to hardness of learning[END_REF] shows hardness of learning sparse F 2 -polynomials, assuming the existence of local pseudorandom generators. Our results are incomparable (and complementary) to their result:

The result of [START_REF] Daniely | From local pseudorandom generators to hardness of learning[END_REF] only shows the hardness of learning sparse F 2 -polynomials for inputs sampled from a very specic distribution D over strings {0, 1} n , which outputs n independent samples from a highly biased Bernoulli distribution. In contrast, our results hold with respect to the uniform distribution. The result of [START_REF] Daniely | From local pseudorandom generators to hardness of learning[END_REF] fundamentally cannot apply to the subexponential regime.

The core reason is the following: from the existence of a learner for s-sparse polynomials given N examples, [START_REF] Daniely | From local pseudorandom generators to hardness of learning[END_REF] only derives a contradiction to the existence of (log s)-local PRGs which stretch N bits from their input. However, it is known [START_REF] Mossel | On e-biased generators in NC0[END_REF] that logarithmic-locality pseudorandom generators cannot possibly achieve stretch beyond quasipolynomial. Therefore, their result does not apply to the setting where s is polynomial and N is subexponential. In contrast, our result applies even to subexponential-time learning algorithms, in the setting where s is polynomial.

On the other hand, the result of [START_REF] Daniely | From local pseudorandom generators to hardness of learning[END_REF] relies on the existence of local PRGs, which is a relatively well-established assumption. In contrast, our result relies on a new variant of LPN, which we support by proving that it resists a large class of attacks (including in particular all standard attacks against LPN).

Candidate weak PRF in AC0 • MOD2. We revisit the question of Akavia et al. [START_REF] Akavia | Candidate weak pseudorandom functions in AC 0 o MOD2[END_REF]:

Can weak pseudorandom functions exist in the class AC0 • MOD2?

We present a new candidate WPRF in AC0 • MOD2 which follows the high-level template of Akavia et al. [START_REF] Akavia | Candidate weak pseudorandom functions in AC 0 o MOD2[END_REF], but with an alternative choice of AC0 circuit structure. The WPRF candidate of Akavia et al. [START_REF] Akavia | Candidate weak pseudorandom functions in AC 0 o MOD2[END_REF] (hereafter referred to as the ABGKR candidate) is of the form

f s,K (x) = x, s ⊕ g(K • x mod 2) for s ∈ {0, 1} n , K ∈ {0, 1} (n-1)×n , where g(x) = λ i=1 log λ j=1 x ij is a DNF (the so-called TRIBES function). Since f s,K (x) can be written as (¬ x, s ∧g(K •x))∨ ( x, s ∧ ¬g(K • x)), it indeed belongs to AC0 • MOD2.
Notice that this candidate is an instance of the learning parity with simple deterministic noise framework, where g(•) is the noise function. Since the noise function is biased, XORing it with x, s makes the nal function balanced.

Unfortunately, this candidate was broken in [START_REF] Bogdanov | Pseudorandom functions: Three decades later[END_REF] by an algebraic attack. In our candidate, we address this issue by simply adding a layer of OR gates after the parity layer, replacing the noise function with:

g(x) = λ i=1 λ j=1 w k=1 x ijk .
We conjecture that our candidate is a subexponentially secure WPRF. We observe that our candidate resists the same classes of attacks as addressed for the ABGKR candidate. However, we are further able to prove that our candidate construction has high rational degree, thus circumventing the algebraic attacks under which the ABGKR candidate was insecure.

2

We also study the resistance of our candidate against linear attacks, a large class of attacks that includes most state-of-the-art attacks on learning parity problems (such as the learning parity with noise assumption), whose structure bears connections to our candidate. We put forth a conjecture which, if true, implies that our candidate (as well as the WPRF candidates of [START_REF] Akavia | Candidate weak pseudorandom functions in AC 0 o MOD2[END_REF][START_REF] Boneh | Exploring crypto dark matter: New simple PRF candidates and their applications[END_REF]) cannot be broken by linear attacks.

We view our results as providing a strong indication that AC0 • MOD2 may not be learnable under the uniform distribution. We compare our results to known results regarding low-complexity PRFs on Table 1. As shown in the Table, our work lls gaps in our understanding of the complexity of weak PRFs.

On WRPFs in AC0 on top of public parities. The conjectured security of our candidate above relies on the MOD2 portion of the AC0•MOD2 circuit remaining secret, dictated by the secret WPRF key. We further revisit the question:

Can WPRF exist in the class formed by AC0 atop public parities? 2 Formally, high rational degree does not prove resistance to the attack from [START_REF] Bogdanov | Pseudorandom functions: Three decades later[END_REF], which only requires proximity to low rational degree. However, we view this as strong evidence that the attack does not apply to our candidate.

Circuit Class

Reference

Flavor Security Assumption AC0 [START_REF] Blum | Cryptographic primitives based on hard learning problems[END_REF] Weak PRF Quasipolynomial Heuristic [START_REF] Kharitonov | Cryptographic hardness of distribution-specic learning[END_REF][START_REF] Applebaum | Fast pseudorandom functions based on expander graphs[END_REF] Weak PRF Quasipolynomial Factor, RLF [START_REF] Linial | Constant depth circuits, Fourier transform, and learnability[END_REF] No WPRF with better than quasipolynomial sec.

AC0 + O(1) XOR,MAJ [START_REF] Viola | The communication complexity of addition[END_REF] No Strong PRF Sparse F2-polynomials This work Weak PRF Subexponential Heuristic [START_REF] Hellerstein | On PAC learning algorithms for rich boolean function classes[END_REF] No WPRF with input length n and better than 2 Õ( √ n) sec.

XNF formulas [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF] Weak PRF Subexponential Heuristic with XOR gates at all levels, and ACC0 to denote the class AC0 with MODm gates for a xed integer m (m = 6 suces). RLF refers to the conjectured one-wayness of random local functions [START_REF] Goldreich | Candidate one-way functions based on expander graphs[END_REF] and Factor to the intractability of factoring.

That is, we study the (in)existence of WPRFs of the form f k (x) = g k (G•x), where g k ∈ AC0 and G is a public matrix. The existence of such a candidate would imply AC0 is not weakly learnable on all linear distributions (i.e. uniform distributions over linear subspaces of F n 2 ). Note, however, that it does not directly imply strong learnability, as boosting techniques would require the learner to modify the input distribution, an option that is not available for WPRFs.

We put forth a conjecture regarding the heavy Fourier coecients of functions of this form, which implies that no WPRF can exist in AC0 on top of public parities. This is a direct strengthening of a conjecture of [START_REF] Akavia | Candidate weak pseudorandom functions in AC 0 o MOD2[END_REF], which asserts the existence of a heavy Fourier coecient for any function in this class. We conjecture further about the form of a heavy Fourier coecient: namely, its expressibility as G T • b for a low-weight vector b ∈ {0, 1} n . This conjectured form implies that a heavy Fourier coecient can be found within quasipolynomial time, and leveraged to obtain nontritival advantage in distinguishing the function from random.

We demonstrate that both pieces of evidence supporting the (more conservative) conjecture of Akavia et al. [START_REF] Akavia | Candidate weak pseudorandom functions in AC 0 o MOD2[END_REF] apply as well to our strengthened variant.

Namely, the conjecture provably holds for the case of:

Arbitrary g k ∈ AC0 and typical public matrices G, including random matrices with high probability. More concretely, any G for which G • x for uniform inputs x fools AC0.

Arbitrary public G, and g k of polynomial size and depth 2 (i.e., CNF/DNF).

We observe that Akavia et al.'s proof for the former immediately applies to our setting as well; namely, the heavy Fourier coecient they demonstrate already is of the desired form. The latter claim holds via a more subtle extension of the argument of Jackson [START_REF] Jackson | An ecient membership-query algorithm for learning dnf with respect to the uniform distribution[END_REF], beyond the treatment within [START_REF] Akavia | Candidate weak pseudorandom functions in AC 0 o MOD2[END_REF].

Relation between conjectures. We map the relation between the various conjectures posed within this work and beyond (depicted in Section 4.3, Fig-

ure 1).

In particular, we draw a connection between our results and the linear IPPP conjecture of Servedio and Viola [START_REF] Servedio | On a special case of rigidity[END_REF]: we observe that the nonexistence of WPRF in AC0 over public parities (which follows from our conjecture above), together with the existence of a WPRF in AC0 • MOD2 (for which we provide a candidate) implies the Linear IPPP conjecture.

A related but technically incomparable observation was recently made in [START_REF] Filmus | Limits of preprocessing[END_REF],

which proves under a standard cryptographic assumption (namely, the learning with rounding assumption [START_REF] Banerjee | Pseudorandom functions and lattices[END_REF]) that either (1) the known quasipolynomial time learning algorithm for AC0 under the uniform distribution [START_REF] Linial | Constant depth circuits, Fourier transform, and learnability[END_REF] cannot be extended to all F 2 -linear distributions, even with subexponential time, or (2) an IPPP-style hardness conjecture is true, in the sense that AC0 • MOD2 cannot compute inner-products over the integers (as opposed to inner product modulo 2). The paper also achieves related results under the assumption underlying the WPRF candidate of [START_REF] Boneh | Exploring crypto dark matter: New simple PRF candidates and their applications[END_REF]. Our result is incomparable: it relies on new assumptions regarding the security of WPRF candidates in AC0 • MOD2 instead of standard cryptographic assumptions, but applies to the true Linear IPPP conjecture instead of a variant over the integers.

Between Lapland and Cryptomania. Finally, we put forth the study of a new family of LPN-style assumptions, called LPN with simple deterministic noise. Roughly, these assumptions assert that one cannot distinguish pairs (x, x, s ⊕ g k (x)) with random x from random pairs (x, y), where s is a secret vector, and g k is a simple secret function sampled at random from a family.

By simple, we mean that g k should belong to a low complexity class (such as AC0[MOD2]).

To our knowledge, this avor of the learning parity with noise problem has never been studied; it bears some resemblance but is incomparable to the learning parity with structured noise framework of Arora and Ge [START_REF] Arora | New algorithms for learning in presence of errors[END_REF], which consider noise patterns which are not deterministic, but satisfy some structure (typically, being roots of a low degree polynomial). This LPN with simple noise formulation captures the candidate weak PRF of [START_REF] Akavia | Candidate weak pseudorandom functions in AC 0 o MOD2[END_REF], our candidate weak PRF in AC0 • MOD2, and a recent candidate WPRF from [START_REF] Boneh | Exploring crypto dark matter: New simple PRF candidates and their applications[END_REF] that can be viewed as being based on

Learning with Rounding (LWR) [START_REF] Banerjee | Pseudorandom functions and lattices[END_REF] Our approach uses a result of Razborov and Smolensky [START_REF] Razborov | Lower bounds on the size of bounded depth circuits over a complete basis with logical addition[END_REF][START_REF] Smolensky | Algebraic methods in the theory of lower bounds for Boolean circuit complexity[END_REF], who show that any AC0[MOD2] function can be approximated by a low-degree polynomial; we show that the approximation noise itself can be used to dene a learning parity with noise instance that ts our framework. On the other hand, we observe that the Razborov-Smolensky approximation could also be leveraged in a positive sense, for improving eciency when evaluating the PRF homomorphically on ciphtertexts or as part of a secure computation. For more details we refer to [START_REF] Barkol | Secure computation of constant-depth circuits with applications to database search problems[END_REF].

Note that the seeming contradiction of the Razborov-Smolensky approximation being suciently noisy to avoid decoding attacks (as far as we know), but precise enough to be useful for replacing the weak PRF by its approximation in applications, can be explained by the dierent number of input-output pairs considered in both contexts. An attacker attempting to break the security requires at least a quasipolynomial number of samples (because the low-degree multivariate polynomial potentially consists of a quasipolynomial number of terms), thus noise will occur almost certainly, whereas in an honest setting, when only computing a polynomial number of samples, likely the approximation will be perfect on all samples considered.

Since Lapland only has partial overlap with Cryptomania (that is, presently only LPN with low noise rate is known to imply public-key encryption with more than quasi-polynomial security 3 ), one can further ask where in the regime between Lapland and Cryptomania weak PRFs in AC0[MOD2] fall.

We put forward a second framework for variable-density learning parity with noise (VDLPN) assumptions into which the recent candidate weak PRF of [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF] (who coined the term variable-density learning parity with noise for a specic instance of this broader framework) and our weak PRF candidate computed by sparse polynomials fall into. We further observe that any weak PRF candidate within this framework implies an instance of learning parity with simple deterministic noise with noise rate below the bound of [START_REF] Alekhnovich | More on average case vs approximation complexity[END_REF]. This still does not imply public-key encryption, because the framework of [START_REF] Alekhnovich | More on average case vs approximation complexity[END_REF] requires the code distribution to be dense, which is not the case for variable density learning parity with 3 More precisely, by a result of [START_REF] Alekhnovich | More on average case vs approximation complexity[END_REF], random LPN implies public-key encryption if the noise rate is in o( √ M ), where M is the length of the secret.

noise. We still view this as an indication that weak PRFs within this framework morally live in Cryptomania.

To formalize this intuition, we put forward a conjecture, stating that with respect to some xed noise rate, either all codes are eciently decodable, or almost all codes are hard to decode. This is backed-up by the common understanding that LPN is in fact hard for random codes when choosing reasonably dense noise. Based on this conjecture we can indeed prove that candidate weak PRFs within the VDLPN framework imply public-key encryption following the strategy of [START_REF] Alekhnovich | More on average case vs approximation complexity[END_REF]. We are not aware of any such implication for general functions in AC0[MOD2] such as our candidate weak PRF in AC0 • MOD2, even if willing to assume this conjecture, because the avor of learning parity with noise implied by Razborov-Smolensky does not give low enough noise rate. This is particularly interesting in light of recent developments on constructing pseudorandom correlation functions [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF], since candidate constructions of expressive correlations so far all rely on either the VDLPN assumption [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF],

factoring-based assumptions [START_REF] Orlandi | The rise of paillier: Homomorphic secret sharing and public-key silent OT[END_REF], or extremely low-noise LPN [START_REF] Couteau | Breaking the circuit size barrier for secure computation under quasi-polynomial LPN[END_REF], which with our result in mind, all imply public-key encryption.

Preliminaries

We start by recalling some basic properties of Boolean functions. We mostly follow standard notations and terminology (see, e.g., [START_REF] Linial | Constant depth circuits, Fourier transform, and learnability[END_REF][START_REF] O'donnell | Analysis of Boolean Functions[END_REF]), except that we identify parity functions with vectors in {0, 1} n instead of subsets S ⊆ {1, . . . , n}.

Boolean functions. A Boolean function is a function f : {0, 1} n → {0, 1}.

When considering the Fourier coecients of a function f we will consider it as a function f : {0, 1} n → {1, -1} by identifying an output b ∈ {0, 1} with (-1) b .

The set of all real-valued functions on the cube {0, 1} n is a 2 n -dimensional real vector space with an inner product dened by g, f = 2

-n • x∈{0,1} n f (x)•g(x).
The norm of f is dened as f = f, f . Denition 1 (Characters). For y ∈ {0, 1} n , the character χ y is dened as

χ y (x) = (-1) x,y .
Note that {χ y } y∈{0,1} n forms an orthonormal basis of the space of all real-valued functions on {0, 1} n . Further, for all y, z ∈ {0, 1} n it holds that χ y χ z = χ y⊕z .

Denition 2 (Fourier coecients). As {χ y } y∈{0,1} n forms a basis, we can write every real-valued function f on the cube as f = y∈{0,1} n f (y) • χ y , for real-valued coecients f (y), called Fourier coecients.

Note that this is well-dened, as {χ y } forms a basis for all functions f : {0, 1} → R. Further, as {χ y } forms a orthonormal basis, the Fourier coecient corresponding to y ∈ {0, 1} n can be computed as f (y) = f, χ y . For every Boolean function

f we have 1 = f 2 = f, f = y∈{0,1} n f (y) 2 .
Denition 3 (Degree). The degree deg(f ) of a Boolean function f is dened as the maximal Hamming weight of a vector y ∈ {0, 1} n for which f (y) = 0.

It can be shown that the above notion of degree coincides with standard algebraic degree.

Circuit classes. The class AC0 is the class of functions computed by a family of constant-depth, polynomial-size circuits of over AND/OR gates of unbounded fan-in along with negations. The class AC0 • MOD2 is dened similarly, except that one also allows parity (XOR) gates only at the bottom. This can be viewed as applying an AC0 function to an F 2 -linear encoding of the input. We dene the circuit depth to be the length of the longest path from an input to an output, not counting negations. For instance, a DNF formula has depth 2. For AC0 • MOD2 circuits we will consider by default only the depth of the AC0 part, namely ignoring parities. See, e.g., [START_REF] Servedio | On a special case of rigidity[END_REF][START_REF] Akavia | Candidate weak pseudorandom functions in AC 0 o MOD2[END_REF][START_REF] Cheraghchi | Ac 0 •mod 2 lower bounds for the boolean inner product[END_REF] for known facts about AC0 and AC0 • MOD2.

In the context of cryptographic primitives, we will consider AC0 or AC0 • MOD2 circuit families {C λ }, parameterized by a security parameter λ, where the input length n = n(λ) is assumed to be a monotonically-increasing, polynomiallybounded function of λ. We assume by default that such a circuit family is polynomial-time uniform, namely there is a polynomial-time algorithm whose output on input 1 λ is a description of C λ ; however, we drop the uniformity requirement in the context of negative results.

Pseudorandom Functions

We consider here weak PRFs, which relax standard PRFs by only considering distinguishers that get the outputs of the function on uniformly random inputs. We require subexponential security by default, namely security against distinguishers of size 2 n for some > 0. This is the typical level of security achieved by constructions based on the strongest plausible versions of standard cryptographic assumptions. We formally dene this notion below.

Denition 4 ((Weak) pseudorandom function [START_REF] Goldreich | How to construct random functions (extended abstract)[END_REF][START_REF] Naor | Synthesizers and their application to the parallel construction of pseudo-random functions[END_REF]). Let λ ∈ N denote a security parameter and n = n(λ), κ = κ(λ) be monotonically-increasing and polynomially-bounded input length and key length functions, respectively. A (weak) pseudorandom function is syntactically dened by a function family

F = {f λ : {0, 1} κ × {0, 1} n → {0, 1}}
, where the output f λ (k, x) can be computed from (k, x) in polynomial time. Since λ and κ are determined by the input length n, we will sometimes write

f k (x) instead of f λ (k, x).
For T = T (κ) and ε = ε(κ), we say that F is a (T, ε)-secure strong pseudorandom function (PRF), if for every λ ∈ N and every oracle circuit A of size

T (κ), it holds Pr k [A f k (•) = 1] -Pr R [A R(•) = 1] ≤ ε(κ), where κ = κ(λ), k $ ← {0, 1} κ is chosen at random, and R : {0, 1} n → {0, 1} is a truly random function. A T -secure PRF is a (T, 1/T )-secure PRF.
We say that F is a (T, ε)-secure weak PRF (WPRF) or T -secure WPRF if the above holds when A only gets access to samples (x i , f k (x i )), where x i $ ← {0, 1} n are chosen uniformly and independently. We say that F is a (Q, T, ε)secure (strong/ weak) PRF if A only gets access to at most Q (chosen/ random) samples. Finally, we say that a (W)PRF F has polynomial security if it is Tsecure for every polynomial T , and that it has subexponential (resp., quasipolynomial, exponential) security if there exists c > 0 such that it is T -secure for T = 2 κ c (resp., T = κ log c κ , T = 2 κc ).

Our choice of subexponential security as the default level of security is motivated both from a cryptographic perspective and from an algorithmic perspective. From a cryptographic perspective, candidate PRFs with quasipolynomial security are relatively easy to obtain even in very low complexity classes and are considered borderline insecure. Subexponential (rather than exponential) security is typically the best level of security one can get from standard assumptions. From an algorithmic perspective, quasipolynomial-time algorithms (such as the LMN learning algorithm [START_REF] Linial | Constant depth circuits, Fourier transform, and learnability[END_REF]) are considered borderline ecient and hence ruling out such algorithms requires PRFs with better than quasipolynomial security.

Finally, when referring to a (W)PRF F in a circuit complexity class such as AC0 or AC0 • MOD2, the default convention is that for each key sequence k(λ), the induced function family f k is in the class. We note that even when considered as a function of both the input and the key, our candidate constructions remain in AC0[MOD2]. On the other hand, our negative results and conjectures are stronger in that they apply to the xed-key case and do not assume polynomial-time uniformity.

Preliminaries on Probability

Given t distributions (D 1 , • • • , D t ) over F n 2 , we denote by i≤t D i the distribu- tion obtained by independently sampling v i $ ← D i for i = 1 to t and outputting v ← v 1 ⊕ • • • ⊕ v t .
Denition 5 (Bias of a Distribution). Given a distribution D over F n 2 and a vector u ∈ F n 2 , the bias of D with respect to u, denoted bias u (D), is equal to

bias u (D) = 1 2 -Pr v $ ←D [u • v = 1]
. Then, the bias of D, denoted bias(D), is dened as bias(D) = max u =0 n bias u (D).

Algebraic Attacks and Rational Degree

Algebraic attacks have been introduced in [START_REF] Patarin | Cryptanalysis of the matsumoto and imai public key scheme of eurocrypt'88[END_REF] and were extended and abstracted in [START_REF] Courtois | The security of hidden eld equations (hfe)[END_REF][START_REF] Courtois | Algebraic attacks on stream ciphers with linear feedback[END_REF][START_REF] Courtois | Fast algebraic attacks on stream ciphers with linear feedback[END_REF]. In its most basic form, an algebraic attack proceeds as follows: given a function F : {0, 1} n → {0, 1}, it nds low degree multivariate polynomials (g, h) such that F • g = h. If polynomials (g, h) of degree at most d are found, then the function F can be inverted given n Õ(d) random samples (x, F (x)). The hardness of inverting a function with an algebraic attack is measured by its rational degree: Denition 6 (Rational Degree). The rational degree of a boolean function F is dened as the following quantity:

RD(F ) = min g =0 {deg(g) | F g = 0 ∨ (F ⊕ 1)g = 0}.
Observe that the smallest d such that there exist polynomials (g, h) of degree at most d satisfying F • g = h necessarily satises d ≥ RD(F ).

WPRFs by Sparse Multivariate Polynomials

In this section, we put forth a new candidate WPRF in a very low subclass of AC0[MOD2]: the class of sparse multivariate polynomials over F 2 . That is, the key denes a sum of poly(n) monomials in the inputs x 1 , . . . , x n . We conjecture that our candidate achieves subexponential security. To our knowledge, this is the rst proposal for a WPRF in this class with plausible subexponential security.

In more detail, our candidate is inspired by a WPRF candidate from [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF], which belongs to the class of XNF formulas, i.e., sparse polynomials in the inputs and their negations. Multivariate polynomials are an important object of study in learning theory. Our candidate WPRF provides an explicit distribution D over sparse n-variate F 2 -polynomials such that the following plausibly holds: there is a constant ε > 0 such that no 2 n ε -time algorithm, given the values of a polynomial p sampled from D on uniformly random inputs, can predict the value of p on a fresh random input with better than 2 -n ε advantage. In contrast, the candidate of [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF] only implies hardness of learning sparse polynomials under a somewhat articial input distribution: the distribution over vector pairs (x, y) where y is the bitwise negation of x. To our knowledge, the only previous results in this setting are limited to showing quasi-polynomial hardness of learning sparse F 2polynomials under the uniform distribution [START_REF] Daniely | From local pseudorandom generators to hardness of learning[END_REF]. Our candidate complements the results of [START_REF] Hellerstein | On PAC learning algorithms for rich boolean function classes[END_REF], which imply a 2 Õ( √ n) -time learning algorithms for sparse F 2 -polynomials.

To support the conjectured subexponential security of our new candidate, we rst observe that known results imply that it cannot be broken by algebraic attacks, as dened in Section 2. Furthermore, we show that its security can be formulated as an LPN-style assumption, which closely resembles (but is technically incomparable to) the variable-density learning parity with noise assumption of [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF]. We provide support for the security of the candidate by proving that it cannot be broken in subexponential time by any linear attack, a large class of attacks which captures essentially all known attacks against LPN and its variants. Our analysis builds upon, but does not follow from, the analysis of [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF]. In the full version we elaborate on the specic challenges that arise when trying to extend the analysis of [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF] to our candidate.

Our Candidate

Our candidate builds upon the candidate of [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF], which was carefully crafted as a XOR of variable-size terms (products of variables and negated variables),

where the purpose of terms of size i is to defeat all linear attacks that depend on (approximately) 2 i samples. In [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF], the set of input variables in each term is xed in advance; the WPRF key simply tells, for each variable in each term, whether to use the input or its negation. To conne our candidate to the subclass of sparse F 2 -polynomials, we must refrain from using negations of inputs. This suggests a very natural variant: instead of selecting between bits x and 1 -x, the key is used to randomly select one out of b random bits x 1 • • • x b for each variable of each monomial. When b is large enough, since the fraction of zeroes and ones in random b-bit strings is tightly concentrated around 1/2, this intuitively provides security guarantees comparable to that of [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF]. We formally introduce the candidate below.

Input domain:

x ∈ {0, 1} n with n = w • D • (D -1) • b/2. We view x
as a concatenation of D blocks (x i ) i≤D , where block x i contains w subblocks x i,1 , • • • , x i,w , and each sub-block x i,j is composed of i b-bit strings (x i,j, ) ≤i . Given a string x i,j, , we write x i,j, [k] to denote its k-th bit.

Key domain:

K = (K i,j, ) i≤D,j≤w, ≤i ∈ [b] s with s = w • D i=1 i.
Candidate:

F K (x) = D i=1 w j=1 i =1 x i,j, [K i,j, ]
Security against algebraic attacks. The security of our candidate against algebraic attacks [START_REF] Courtois | Algebraic attacks on stream ciphers with linear feedback[END_REF] follows directly from a known bound on the rational degree of triangular functions.

Lemma 7. For any K ∈ [b] s , an algebraic attack in the sense of [START_REF] Courtois | Algebraic attacks on stream ciphers with linear feedback[END_REF] requires (time and) number of samples lower bounded by n Ω(D) = 2 Ω(D log(D+w+b)) .

Lemma 7 follows readily from the fact that our candidate weak PRF has high rational degree: for any K ∈ {0, 1} s , it holds that RD(F K ) ≥ D. The proof follows immediately from [START_REF] Méaux | Towards stream ciphers for ecient FHE with low-noise ciphertexts[END_REF]: for any xed choice of key K, F K is a direct sum of w independent triangular functions of degree D, each evaluated on distinct portions of the input, where (denoting D = D(D -1)/2) the triangular function of degree D is the function

T D (x 1 , • • • , x D ) = x 1 ⊕ x 2 x 3 ⊕ • • • ⊕ D =D -D x . By Lemma 3 of [42]
, the rational degree of a direct sum of functions is at least the largest rational degree of its components, and by Lemma 6 of [START_REF] Méaux | Towards stream ciphers for ecient FHE with low-noise ciphertexts[END_REF], the rational degree of T D is exactly D.

Variable-Density LPN Formulation

We now show that the security of our weak PRF candidate follows from a VDLPN-style assumption, in the spirit of [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF]. We note, however, that the concrete assumption is not directly comparable to that of [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF]: while the corresponding noise distributions are similar, the variable-density matrix distribution in our work is very dierent. In the following, for each (i, j) ∈ [D] × [w], it is convenient to view K i,j = (K i,j, ) ≤i as a single integer from the set [b i ], via the natural embedding. Then, let u(K i,j ) denote the unit length-b i vector with a 1 at position K i,j and 0's elsewhere. We can rewrite F K as

F K (x) = D i=1 w j=1 i =1 x i,j, , u(K i,j ) = x 1,1, || • • • || D =1 x D,w, , u(K 1,1 )|| • • • ||u(K D,w ) = h(x) , e(K)
where h : and outputting e(K). Clearly, breaking the security of our candidate given N samples is equivalent to breaking the (H, N )-dualLPN assumption. This variant of the dual LPN assumption is very close in spirit to the regular VDLPN assumption from [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF]: the noise distribution is the same up to setting b = 2. The matrix distribution, on the other hand, is quite dierent, but satises the same sparsity condition: the matrix H is divided into D submatrices H i , and the average sparsity of the rows of H i is (w

x → (x 1,1,1 || • • • || D =1 x D,w, ) and e : K → (u(K 1,1 )|| • • • ||u(K D,w )). Now,
• (b/2) i )/(w • b i ) = 1/2 i .
The matrix distribution in [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF] satises the same variable density structure, which motivated the name variable-density LPN. Therefore, we view our new candidate as belonging to the same family of LPN variants.

Security Against Linear Attacks

We turn to consider the class of linear attacks, which in the context of pseudorandom generators captures the notion of small-bias generators [START_REF] Naor | Small-bias probability spaces: Ecient constructions and applications[END_REF]. Linear attacks capture, intuitively, every attack where the distinguisher is restricted to compute a linear function of the LPN samples, the identity of which can be arbitrarily determined from the public LPN matrix and inputs. This captures essentially all known attacks against standard variants of LPN, such as those based on Gaussian elimination, statistical decoding, information set decoding, and BKW-style attacks. The work of [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF] provided support for their VDLPN conjecture by proving subexponential security against such linear attacks.

In the context of a WPRF, a linear distinguisher is rst given N random inputs x 1 , . . . , x N , and then must choose a subset of indices S ⊂ {1, . . . , N } such that the distribution i∈S f k (x i ), for a random choice of k, is biased towards 0 or 1. More formally, we use the following notion of an (ε, δ, N )-biased WPRF, which naturally extends the standard notion of an ε-biased pseudorandom generator. Denition 8 ((ε, δ, N )-biased weak PRF family, [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF]). A function family

{F K : F n(λ) 2 → F 2 } K∈F s(λ) 2 is (ε, δ, N )-biased if for every large enough λ ∈ N, letting D λ,N (x) (for some x ∈ (F n(λ)

2

) N ) denote the distribution which samples

K $ ← F s(λ) 2
and outputs y = (F K (x (1) ),

• • • , F K (x (N ) )), it holds that Pr x (1) ,••• ,x (N (λ)) $ ←F n(λ) 2 [bias(D λ,N (x)) > ε(λ)] ≤ δ(λ).
Notation and theorem statement. Theorem 9 (Low bias). Fix a security parameter λ. There exist constants 0 < β, ν, µ < 1 such that for any parameters (D, w, b,

N ) satisfying w = poly(λ), b = poly(λ), D 2 ≤ β • w, D ≤ √ b 2λ + 1, and N ≤ 2 D , letting H = H(D, w, b, N ), it holds that Pr H←H [bias(D out (H)) > µ w ] ≤ ν D + ν λ 2 .
For example, using the choice of parameters (D, w, b, N ) = (λ, λ 2 /β, 4λ 4 , 2 λ ), our candidate is (2 -Ω(λ 2 ) , 2 -Ω(λ) , 2 λ )-biased with inputs of length O(λ 8 ), and keys of length Õ(λ 4 ).

To facilitate comparison with the analysis of [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF], we let H and N denote respectively the matrix and noise distributions for the VDLPN variant of [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF],

where a sample H ← H can also be broken into

D matrices H i = H i,1 || • • • ||H i,w
where the H i,j are independent matrices; we denote by H i the distribution over H i induced by H ← H for any i ≤ D.

High level overview. At a high level, the security analysis follows the same approach as the analysis in [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF] (which should come as no surprise due to the similarities between the candidates); however, the analysis is signicantly more involved due to the more complex structure of the matrix distribution for our candidate. Fix i ≤ D. The analysis of [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF] proceeds roughly as follows.

1. Using a strong concentration bound (McDiarmid's bounded dierence inequality), it shows that for any xed attack vector v ∈ F N 2 whose Hamming weight is between 2 i-1 and 2 i , except with probability at most exp(-Ω(w

• 2 i )), a random matrix H i ← H i satises HW(v •H i,j )/ |v • H i,j | ∈ [ε, 1-ε],
where ε is some constant (that is, v • H i,j has a fraction of ones bounded by a constant, and bounded away from 1 by a constant), for a fraction at least w/2 of the w submatrices H i,j of H j . Such a matrix H i is called good with respect to v.

2. From a union bound over all vectors v of weight between 2 i-1 and 2 i , it follows that, except with probability at most exp(-Ω((log N -w) • 2 i )), a random matrix H i ← H i will be good with respect to all vectors v in this weight range. When w is suciently larger than log N , this probability is bounded by exp(-Ω(w)) for any i ≤ D. 3. By a union bound over all i ≤ D, with probability at least 1-D•exp(-Ω(w)) = 1 -exp(-Ω(w)), a random matrix H ← H satises the following: for every nonzero vector v, there is an i * ≤ D such that H i * is good with respect to v. Then, for any such matrix H, H • e for e ← N is the vector obtained by sampling a uniformly random column from each (H i,j ) i≤D,j≤w and XORing them all. Since H i * is good with respect to v, H • e will include at least w/2 terms sampled randomly and independently from bitstrings v • H i * ,j with a fraction of ones in [ε, 1 -ε]. It follows that, with probability at least 1 -exp(-Ω(w)) over the random choice of H ← H , the distribution of H • e for e ← N has bias with respect to v at most (1 -ε) w/2 /2 = 2 -Ω(w) , for any possible nonzero vector v.

Looking ahead, our security analysis will follow the same three steps as above, and the steps 2 and 3 will be the same as in [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF]. However, while the rst step also consists in proving a similar bound, the actual analysis turns out to be much more involved due to the dierent matrix structure. Due to space limitations, the proof of Theorem 9 is deferred to the full version.

WPRFs in AC0 • MOD2

In this section we present a candidate construction of a weak PRF in AC0 • MOD2 (recall, unlike AC0[MOD2], here the parity gates must lie at the input layer of the circuit). We follow the high-level template of Akavia et al. [START_REF] Akavia | Candidate weak pseudorandom functions in AC 0 o MOD2[END_REF]. Their construction, referred to as ABGKR, is of the form

f s,K (x) = x, s ⊕ g(K • x mod 2)
for s ∈ {0, 1} n , K ∈ {0, 1} (n-1)×n , where g(x) = λ i=1 log λ j=1 x ij is a DNF (the so-called TRIBES function). Since f s,K (x) can be written as (¬ x, s ∧ g(K

• x)) ∨ ( x, s ∧ ¬g(K • x)), it indeed belongs to AC0 • MOD2.
The rationale behind the design of Akavia et al. is the following: even when picking a very simple function g (in their case, a DNF), the function g K (x) = g(K • x) can already not be distinguished from a random c-unbalanced function (i.e. a random function f with Pr x [f (x) = 1] = c for some constant c = 1/2) for various natural attacks (e.g. correlations with small function families and closeness to low-degree polynomial). Then, this function g k is XORed with x, s to make the nal function balanced.

From unbalanced WPRFs to standard WPRFs. We observe that this transformation does actually provably turn an unbalanced WPRF into a standard WPRF, under the LPN assumption. The proof of this observation is straightforward; for details we refer to the full version. In spite of its simplicity, this observation had to our knowledge never been made.

We further note that there exists an alternative, unconditional transformation from a c-unbalanced WPRF in AC0 • MOD2 into a standard WPRF in AC0 • MOD2 which relies on the Von Neumann randomness extractor: assume w.l.o.g. that c < 1/2. Use (say) 2n parallel instances of the c-unbalanced WPRF on independent inputs and keys, grouped into n pairs. Then, take the rst pair of distinct output bits (since c is a constant, there is one such pair with overwhelming probability 1 -2 -O(n) ): if it is 01, dene the output of the WPRF to be 0; else, dene it to be 1. It is relatively straightforward to prove that if g k is a c-unbalanced WPRF, the resulting function is a WPRF. This process can be executed in AC0, hence the resulting function is in AC0 • MOD2.

Our approach. The above discussion justies focusing on the task of building unbalanced WPRFs in AC0 • MOD2, since the latter imply standard WPRFs in the same class through simple transformations. The ABGKR candidate instantiates this unbalanced WPRF with a DNF on top of parities; however, the attack of [START_REF] Bogdanov | Pseudorandom functions: Three decades later[END_REF] allows to distinguish any depth-2 AC0 circuit on top of parities from unbalanced random functions, since any such function must have low rational degree. Therefore, any unbalanced WPRF in AC0 • MOD2 must have at least three layers of AND/OR gates. With the goal of nding the simplest possible modication of the ABGKR candidate which can retain subexponential security, we ask:

Is there a subexponentially secure unbalanced WPRF computable by a depth-3 AC0 circuit on top of parities?

Our candidate. We put forth the following candidate unbalanced WPRF:

g k (x) = g(K • x), with g(x) = λ i=1 λ j=1 w k=1 x ijk , (1)
where λ is a security parameter (i.e., we will bound the complexity of various attacks on our candidate as a function of λ) and m, w are chosen such that w = log λ-log log λ and m = λ 2 w. That is, we simply add a single layer of ORs after the parity layer, with parameters chosen to guarantee that Pr x [g(x) = 1] is constant. Note that choosing the fan-in of the gates more carefully, one can actually obtain bias 1 = 2 + o n [START_REF] Akavia | Candidate weak pseudorandom functions in AC 0 o MOD2[END_REF]. In this case the function g(x), which replaces the TRIBES function in ABGKR, corresponds to the degree-3 Sipser function.

For more details, we refer to [START_REF] Håstad | Almost optimal lower bounds for small depth circuits[END_REF][START_REF] Rossman | An average-case depth hierarchy theorem for boolean circuits[END_REF].

We conjecture that this candidate achieves subexponential security. Observe that since the attack of [START_REF] Bogdanov | Pseudorandom functions: Three decades later[END_REF] distinguishes any depth-2 AC0 circuit on top of par-ities from unbalanced random functions, our candidate actually enjoys optimal depth. 4

Provable Resistance to Algebraic Attacks

Algebraic attacks are a general class of cryptanalytic algorithms that aim to either invert a function or distinguish it from random, by obtaining many samples and using these to derive a system of linear equations over the secret inputs. This class of attack was rst developed by the applied cryptographic community and used to break public-key encryption schemes and stream ciphers [START_REF] Patarin | Cryptanalysis of the matsumoto and imai public key scheme of eurocrypt'88[END_REF][START_REF] Courtois | The security of hidden eld equations (hfe)[END_REF][START_REF] Courtois | Algebraic attacks on stream ciphers with linear feedback[END_REF]. It generalizes in particular the correlation attacks [START_REF] Johansson | Improved fast correlation attacks on stream ciphers via convolutional codes[END_REF] that have been developed

for attacking LFSRs. Correlation attacks have been considered in the theory community in the context of constructing local pseudorandom generators [START_REF] Mossel | On e-biased generators in NC0[END_REF].

The resistance of a WPRF f k : {0, 1} n → {0, 1} to algebraic attacks can be measured by its rational degree, that is, the smallest d for which there exist non-zero polynomials p and q of algebraic degree at most d, such that

f k (x) • p(x) = q(x), ∀x ∈ {0, 1} n . (2)
Applebaum and Lovett [START_REF] Applebaum | Algebraic attacks against random local functions and their countermeasures[END_REF] formally studied algebraic attacks of local functions, and showed that if a predicate has large rational degree then it provably resists a natural class of algebraic attacks.

On the other hand, if a WPRF candidate f k has low rational degree d, then it can be distinguished from random via a simple algebraic attack, which obtains O(n d ) samples and tests whether (2) holds for each of them. This is exactly the type of attack that Bogdanov and Rosen [START_REF] Bogdanov | Pseudorandom functions: Three decades later[END_REF] observed breaks the candidate of Akavia et al. [START_REF] Akavia | Candidate weak pseudorandom functions in AC 0 o MOD2[END_REF] in quasipolynomial time, since it has rational degree O(log λ).

We, on the other hand, show that our candidate has rational degree λ. Even though, formally, this does not rule out the attack of [START_REF] Bogdanov | Pseudorandom functions: Three decades later[END_REF], which only requires proximity to low rational degree, we view this as strong evidence that the attack does not apply to our candidate.

To analyze the rational degree of our candidate, we rst give a general method for determining the exact rational degree of any function in AC0 that can be expressed as alternating layers of AND and OR gates that each depend on disjoint subsets of the input. We then use this to compute the rational degree of our noise function, and nally our candidate unbiased WPRF.

Towards understanding our techniques, we rst briey recall the attack of Bogdanov and Rosen [START_REF] Bogdanov | Pseudorandom functions: Three decades later[END_REF]. To that end, note that the rational degree can be characterized as the minimal d such that there exists a polynomial p = 0 of algebraic degree d such that f • p = 0 or (f ⊕ 1) • p = 0 (also referred to as the algebraic immunity in the literature). The attack of Bogdanov and Rosen [START_REF] Bogdanov | Pseudorandom functions: Three decades later[END_REF] 4 However, transforming our candidate into a standard WPRF, e.g. using the LPN- based transformation, results in a candidate computed by a depth-4 AC0 circuit on top of parities. It is an interesting question whether the optimal depth can be achieved for standard WPRFs, i.e., whether there exists subexponentially-secure standard WPRFs computable by depth-3 AC0 circuit on top of parities.

builds on the observation that f = f i always has rational degree at most min i deg f i , as f i (x) = 1 implies f (x) = 1 and thus (f ⊕ 1) • f i = 0. Therefore, for any DNF either all inner conjunctions have high algebraic degree (and thus the DNF is highly biased towards 0), or the function is susceptible to rational degree attacks.

We observe that while a disjunction does not increase the rational degree of a function, it does have an eect that can be leveraged. Namely, consider a function p = 0 of minimal algebraic degree such that f • p = 0. We will prove that if p i are the minimal annihilating functions for f i (and all functions depend on disjoint parts of the input), p must have algebraic degree at least i p i . Now, using that conjunctions behave in a dual way, alternating between conjunctions and disjunctions allows to increase the rational degree while keeping the function's bias constant. In order to prove this, we introduce the notion of primal and dual rational degree. Denition 10 (Primal and dual rational degree). For f : {0, 1} n → {0, 1}, we dene the primal rational degree ρ as the minimal ρ such that there exists a polynomial p = 0 with algebraic degree ρ and f • p = 0. Further, we dene the dual rational degree ρ of f as the primal rational degree of its negation. Namely, we dene the dual rational degree as the minimal ρ such that there exists a polynomial p = 0 with algebraic degree ρ and (f ⊕ 1) • p = 0. Note that the rational degree of f is d = min(ρ, ρ ).

With the notion of primal and dual rational degree we can distill our main observation in the following lemma, which we prove in the full version. Lemma 11. Let f, h : {0, 1} n → {0, 1} be Boolean functions that depend on disjoint parts of the input 5 , where f and h have primal rational degree ρ f and ρ h and dual rational degree ρ f and ρ h , respectively. Then: (i) The primal rational degree of f ∨ h is lower bounded by ρ f + ρ h . (ii) The dual rational degree ρ of f ∨ h is lower bounded by min(ρ f , ρ h ).

With this, it is straightforward to compute the exact rational degree of a disjunction, where all terms depend on disjoint parts of the input. Similarly, we can also apply this to compute the rational degree of a conjunction, since s

i=1 f i = s i=1 (f i ⊕ 1) ⊕ 1.
Put together, and applied to our candidate, we obtain the following.

Lemma 12. Let m = m(λ) ∈ N, let g : {0, 1} m → {0, 1} be as in Equation 1, let n = m + 1, and let s ∈ {0, 1} n , K ∈ {0, 1} m×n be such that the map x → ( x, s , K • x) mod 2 is invertible. Then, our candidate weak PRF f s,K : {0, 1} n → {0, 1} dened via

f (x) → x, s + g(K • x mod 2)
has rational degree at least λ.

For further details and discussion, we refer the reader to the full version. 5 We say that f depends on the i-th index of the input, if xi appears with a non-zero coecient in some term in f .

We also consider the natural question of the existence of a simpler class of

WPRF of the form f k (x) = g k (G • x)
, where G is a public matrix. Note that if G is removed (or surjective) then f k could be learned by the algorithm of Linial, Mansour and Nisan [START_REF] Linial | Constant depth circuits, Fourier transform, and learnability[END_REF] for learning AC0 under the uniform distribution. While Akavia et al. [START_REF] Akavia | Candidate weak pseudorandom functions in AC 0 o MOD2[END_REF] conjectured that any function in AC0 • MOD2 has a large Fourier coecient, we take this further by suggesting that, in the case of a public matrix G, the heavy Fourier coecient of f k stems from a low-order coecient of g k (in the following referred to as Conjecture II). This would imply that the high-weight Fourier coecient can be used to distinguish the function from random in quasipolynomial time even given only access to random samples, and therefore allows to conclude that there cannot exist a weak PRF in AC0 on top of public parities (in the following referred to as Conjecture III).

We prove Conjecture II for the case when g k is a family of DNFs, by extending the work of Jackson [START_REF] Jackson | An ecient membership-query algorithm for learning dnf with respect to the uniform distribution[END_REF] to show that the coecient is of the right form. The idea of Jackson is that any DNF correlates with a parity of its term that is most likely to be satised, which implies a heavy Fourier coecient. We further observe that this means the function is either biased, or the term can contain only a few non-correlated variables. Since an AND clause is only satised for exactly one setting of inputs, if there are too many independent terms in the DNF then the function is biased. Otherwise, there are many dependencies between the individual terms, which we show implies the heavy Fourier coecient comes from a vector of the form a = G v for some low-weight v.

We further prove Conjecture II for arbitrary g k ∈ AC0 if the matrix G is random (or, more generally, denes a polylog-wise independent map).

We present the formal Conjectures I, II and III as well as the proof of Conjecture II for the above mentioned special cases in the full version.

Linear IPPP and Relations Between Conjectures Finally, in the full version, we also elaborate on the relations between our conjectures, and previous conjectures in the literature including the Linear IPPP conjecture [START_REF] Servedio | On a special case of rigidity[END_REF], asserting that mod-2 inner product is not in AC0 • MOD2. These connections are illustrated in Fig. 1.

Between Lapland and Cryptomania

In this section we present two abstract frameworks. We rst introduce the notion of learning parity with simple deterministic noise, which captures our candidate weak PRF in AC0 • MOD2 from Section 4. Further, we show that every weak PRF candidate in AC0[MOD2] implies some form of learning parity with simple deterministic noise.

Next, we introduce an abstract framework that captures variable-density learning parity with noise style assumptions such as the candidate weak PRF of [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF] and our candidate weak PRF from Section 3.

Further, if one believes that either no code is hard to decode or almost all codes are hard to decode with respect to some noise level, then we show that each candidate that ts into the VDLPN framework lives in Cryptomania. We are not aware of any similar implications for functions that can be cast as learning parity with AC0[MOD2]-noise more generally.

Learning Parity with Simple Deterministic Noise

We observe that the Akavia et al. [START_REF] Akavia | Candidate weak pseudorandom functions in AC 0 o MOD2[END_REF] candidate as well as our own candidate in AC0 • MOD2 can be cast as a form of new LPN-style assumption, that we refer to as LPN with simple deterministic noise. This can be viewed as a generic method to transform a biased weak PRF into a weak PRF. Formally, we dene learning parity with simple noise as follows.

Denition 13 (Learning parity with simple deterministic noise). Let n = n(λ), κ = κ(λ) ∈ N and let G = {g k : {0, 1} n → {0, 1} | k ∈ {0, 1} κ } be a family of keyed functions in a low-complexity class. We say a function family

F = {f s,k : {0, 1} n → {0, 1} | s ∈ {0, 1} n , k ∈ {0, 1} κ } is an instance of learning parity with simple deterministic noise from G, if f s,k : {0, 1} n → {0, 1} is of the form f s,k (x) = x, s ⊕ g k (x).
In this paper by simple we usually refer to noise functions in AC0

[MOD2]. Note that if G is in AC0[MOD2],
then so is F. Further note that f s,k can be written as

f s,k (x) = (¬ x, s ∧ g k (x)) ∨ ( x, s ∧ ¬g k (x)).
This shows that for g k ∈ AC0 • MOD2 we also have f s,k ∈ AC0 • MOD2 (where we consider the key as xed). Note that this transformation from a biased weak PRF g k to a weak PRF f s,k is not depth-preserving, however.

This framework can be extended to capture more general input distributions as follows.

Denition 14 (Extension to general input distributions).

Let n = n(λ), κ = κ(λ), M = M (λ) ∈ N, let G = {g k : {0, 1} n → {0, 1} | k ∈ {0, 1}
κ } be a family of keyed functions in a low-complexity class, and let h : {0, 1} n → {0, 1} M a function. We say that a function family

F = {f s,k : {0, 1} n → {0, 1} | s ∈ {0, 1} M , k ∈ {0, 1} κ
} is an instance of learning parity with simple deterministic noise from G with respect to the input distribution generated by h, if

f s,k : {0, 1} n → {0, 1} is of the form f s,k (x) = h(x), s ⊕ g k (x).
Of course not every class of noise functions gives rise to a candidate weak PRF. In the full version we make progress on studying learning parity with simple noise by presenting a combinatorial conjecture about properties that the family of noise functions G has to satisfy (informally speaking, these are the properties of being balanced and having high-degree), that we believe are sucient in order to resist all linear attacks. However, note that as the attack by Bogdanov and Rosen [START_REF] Bogdanov | Pseudorandom functions: Three decades later[END_REF] showed, satisfying these properties is still not sucient to be a weak PRF, because other classes of attacks such as algebraic attacks might apply.

Weak PRFs in AC0[MOD2] Live in Lapland

The results on circuit lower bounds by Razborov and Smolensky [START_REF] Razborov | Lower bounds on the size of bounded depth circuits over a complete basis with logical addition[END_REF][START_REF] Smolensky | Algebraic methods in the theory of lower bounds for Boolean circuit complexity[END_REF] show that every function in AC0[MOD2] can be approximated by a polynomial of polylogarithmic degree. More formally, their result can be stated as follows.

Theorem 15 (Razborov-Smolensky [START_REF] Razborov | Lower bounds on the size of bounded depth circuits over a complete basis with logical addition[END_REF][START_REF] Smolensky | Algebraic methods in the theory of lower bounds for Boolean circuit complexity[END_REF]). Let

(x) = 1] ≤ 2 -log c κ .
Note that the Razborov-Smolensky result does not make any guarantees as to the distribution over the approximating low-degree polynomial for the functions in the PRF family, corresponding to distribution over the secret s in the LPN instance. However, the corresponding LPN instance reduces to the case of average-case s. While it is known that the decoding of some linear codes and even structured codes such as Reed-Solomon codes for certain noise rates is NP-hard [START_REF] Berlekamp | On the inherent intractability of certain coding problems (corresp.)[END_REF][START_REF] Gandikota | On the np-hardness of bounded distance decoding of reed-solomon codes[END_REF],

we are not aware of similar result for (punctured) Reed-Muller codes as the one described above. Also, to our knowledge known results on NP-hardness of computing and approximating the minimum distance of codes [START_REF] Vardy | The intractability of computing the minimum distance of a code[END_REF][START_REF] Dumer | Hardness of approximating the minimum distance of a linear code[END_REF] do not apply to our example. We leave it as an interesting open question to nd a more natural implication from weak PRFs in AC0[MOD2] to the hardness of decoding linear codes.

A Framework for VDLPN Assumptions

In [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF], a candidate weak PRF in AC0[MOD2] was given, with security based on a specic variable-density learning parity with noise assumption. In the following we give a framework of variable-density learning parity with noise that captures the weak PRF candidate of [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF] and also our candidate based on sparse polynomials presented in Section 3 in AC0[MOD2]. Note that the VDLPN framework is not restricted to functions in AC0[MOD2]. And, on the other hand, not all function families in AC0[MOD2] fall within this framework. Therefore, the conditional public-key implication that we give in the following only applies to candidates such as the one given in [START_REF] Boyle | Correlated pseudorandom functions via variable-density LPN[END_REF] and our candidate based on sparse polynomials, but not our candidate weak PRF in AC0 • MOD2. We say that the variable-density learning parity with noise (VDLPN) assumption with respect to (h, e) is (Q, T, )-hard, if f k (x) := h(x), e(k) is a (Q, T, )-weak PRF.

Note that even though not directly falling into the framework of learning parity with simple noise VDLPN implies an instance thereof. To see this consider a VDLPN tuple (h, e). Now, let h 0 : {0, 1} n → {0, 1} n and h 1 : {0, 1} n → {0, 1} N -n such that h(x) = (h 0 (x), h 1 (x)) for all x ∈ {0, 1} n , and similarly let e 0 : {0, 1} κ → {0, 1} n , e 1 : {0, 1} κ → {0, 1} N -n , such that e(k) = (e 0 (k), e 1 (k)) for all k ∈ {0, 1} κ . Let G = {g k : {0, 1} n → {0, 1} | k ∈ {0, 1} κ }, where g k (x) = h 1 (x), e 1 (k) , and let f s,k = h 0 (x), s ⊕ g k (x). Now, if VDLPN with respect to (h, e) is hard, then so is learning parity with simple deterministic noise G with respect to the input distribution generated by h 0 , due to the same reduction of LPN with arbitrary secret s * to a uniform secret s mentioned in a comment following Corollary 16.

Connections of VDLPN to Cryptomania

In the following we outline why VDLPN morally implies LPN with low noise and therefore public-key encryption. We cannot show a direct PKE implication, because the Alekhnovich construction [START_REF] Alekhnovich | More on average case vs approximation complexity[END_REF] does not apply directly if the matrix is also sparse, since the dual LPN assumption (i.e. the assumption that the pair (H, v) for a matrix H that generates the dual code and v = H • e for a sparse noise vector e is indistinguishable from (H, r) for a uniformly random vector r ) cannot hold true in this case, as v will be biased towards 0.

What we mean by morally is that the noise rate itself is suciently low to imply PKE, and because typically LPN is considered to be hard on average for random codes (if the noise is suciently dense). In order to formalize this observation we formulate a conjecture stating that if there exists a code that is hard to decode with respect to some noise rate (where the noise itself can depend on the generator matrix of the code), then almost all codes are hard to decode with respect to this noise rate. In order to deal with the fact that the noise might depend on the matrix (and therefore replacing the matrix might in fact trivially render LPN insecure), we simultaneously replace the noise by noise that is Bernoulli distributed at the same rate. Note that relaxing the success probability of the adversary to + 2 -λ c is necessary, because there obviously exist some codes that are easy to distinguish from random for any non-trivial noise rate (e.g. A chosen as the all zero matrix).

In order to further weaken the conjecture, allowing for the possibility that there exist some codes that are signicantly harder to decode than random codes, one can require that the input the generated by h (i.e. obtained by sampling x $ ← {0, 1} n and outputting h(x)), have min-entropy at least polylog(λ). This weaker conjecture is still sucient to prove the PKE implication of VDLPN.

In the full version, we prove the following. Lemma 20. Let n = n(λ), N = N (λ), κ = κ(λ) ∈ N, h : {0, 1} n → {0, 1} N and e : {0, 1} κ → {0, 1} N . Let T = T (λ) ∈ N and Q = Q(λ) such that Q ∈ λ ω (1) . Then, if Conjecture 19 holds and VDLPN is (Q, 2 λ c , 2 -λ c )-hard for (h, e) for some constant c > 0, then public-key encryption with quasipolynomial running time and subexponential security exists. Remark 21. Note that the noise rate implied by Razborov-Smolensky does not suce to construct public-key encryption via Alekhnovich [START_REF] Alekhnovich | More on average case vs approximation complexity[END_REF] (even under the random LPN is the hardest conjecture), because the noise rate implied by the Razborov-Smolensky approximation is ω(1/ √ M ). In addition, constructions of PKE from LPN with constant noise, e.g., [START_REF] Yu | Cryptography with auxiliary input and trapdoor from constantnoise LPN[END_REF], have quasi-polynomial running time and security. We are therefore not aware of any public-key implications for general weak PRFs in AC0[MOD2].

  given a bound N on the number of samples, we let H = H(D, w, b, N )denote the distribution over matrices H in F N ×(w• D i=1 b i ) 2whose N rows are sampled as h(x) for independent samples x $ ← {0, 1} n . Furthermore, we let N = N (D, w, b) denote the distribution over vectors e in F

  s

Denition 18 (

 18 A framework for VDLPN). Let n = n(λ), N = N (λ), κ = κ(λ) ∈ N. Let h : {0, 1} n → {0, 1} N and e : {0, 1} κ → {0, 1} N . We say that (h, e) denes an instance of variable-density learning party with noise, if f k (x) := h(x), e(k) is eciently computable, and there existζ i = ζ i (λ), η i = η i (λ) ∈ [0, 1] for all i ∈ [N ], such that 1. for all i ∈ [N ] it holds: Pr x [h(x) i = 1] = ζ i and P r k [e(k) i = 1] = η i , 2. for all i ∈ [N ] it holds: ζ i ≥ ζ i+1 and η i ≥ η i+1 ,3. there exist polynomials p = p(λ), q = q(λ) ∈ N such that: N i=1 ζ i ≤ p and N i=1 η i ≤ q.

Conjecture 19 (

 19 Random LPN is the hardest). Let n = n(λ), Q = Q(λ), κ = κ(λ), M = M (λ) ∈ N, let G = {g k : {0, 1} n → {0, 1} | k ∈ {0, 1} κ} be a family of keyed functions and let h : {0, 1} n → {0, 1} M such that learning parity with simple noise G is (Q, T, )-hard for the input distribution generated by h. Then, we conjecture that the standard LPN problem with noise with rate η is (Q, T, )hard. More precisely, we conjecture that if A $ ← {0, 1} Q×M , s $ ← {0, 1} M are both sampled uniformly at random, and a noise vector e is sampled according to the Bernoulli distribution over {0, 1} Q with rate η ≥ Prx $ ←D,k $ ←{0,1} κ [g k (x) = 1],then then there exists a constant c > 0 such that the distribution of (A, As + f ) is (T, + 2 -λ c )-indistinguishable from the uniform distribution.

Table 1 :

 1

Comparison of positive and negative results for low-depth PRFs. We consider the complexity of computing the output for any xed key, where security level is with respect to the key length (see

Denition 4)

. We write AC0[MOD2] to denote the class AC0

  We rst introduce some notation. Recall that a sample H from H is a concatenation of D matrices H i , where each matrix H i is itself a concatenation of w submatrices H i,j ∈ F N ×b i =1 x i,j, , where the (x i,j, ) ≤i are i uniformly random independent b-bit strings. For any xed matrix H in the support of H, we let D out (H) denote the distribution induced by sampling e ← N and outputting H • e.

	form	i	2	whose rows are of the

  n, d, S ∈ N. If f : {0, 1} n → {0, 1} can be computed by depth-d, size-S circuit with MOD2 gates, then for any integer ε > 0, there exists a polynomial p(x) ∈ F 2 [x 1 , . . . , x n ] of degree at most(log(S/ε)) d such that Pr x [f (x) = p(x)] ≤ ε. theorem implies that if there is a weak PRF in AC0[MOD2], then learning parity with noise is hard, where the code is a punctured Reed-Muller code of quasipolynomial dimension (i.e. the row corresponding to an input x consists of the of all low-degree monomials evaluated on x), the secret corresponds to the coecient of the polynomial that approximates the weak PRF, and the noise corresponds to the approximation error. In other words, the existence of a weak PRF in AC0[MOD2] says that this kind of punctured Reed-Muller codes are hard to decode for some nontrivial noise rate.

	The

Corollary 16. Let n = n(λ), κ = κ(λ) ∈ N. If there exists a (Q, T, ε)-weak PRF in AC0[MOD2], then there exists c, C ∈ N with c < C, a family of keyed functions G = {g k : {0, 1} n → {0, 1} | k ∈ {0, 1} κ } and a function h : {0, 1} n → {0, 1} M where M = 2 log C κ , such that the learning parity function f s,k = h(x), s ⊕ g k (x)

with deterministic noise g k ∈ G respective to the input distribution generated by h is a (Q, O(T ), )-weak PRF. Further, for the corresponding noise rate we have that Pr x,k [g k

  Namely, samples x, s * ⊕ g k (s) for arbitrary s * can be generically converted to consistent samples for uniform secret s * + s , by osetting each sample by x, s . Note that having a superpolynomial secret in Corollary 16 only scales down the LPN security when expressed as a function of the secret size, and in the subexponential regime the resulting guarantee remains meaningful. More explicitly, the corollary can be understood as follows: If there exists a weak PRF in AC0[MOD2] with subexponential security 2 κ δ , then there exists an instance of deterministic LPN that has secret length M = 2 log C κ and security in the orderof 2 κ δ = 2 2 δ•log 1/C M. Thus, the existence of weak PRF candidates in AC0[MOD2] implied by Razborov-Smolensky is above the minimal distance of the corresponding (punctured) Reed-Muller code of low-degree multivariate polynomials, therefore unique decoding will in general not be possible. That is, we expect many low-degree multivariate polynomials p(x) to agree with a given function f k in AC0[MOD2] up to this noise rate. Identifying any such p(x) constitutes an attack on the pseudorandomness of f k , as it provides a low-error prediction of f k evaluations. Note that the number of (punctured) Reed-Muller codewords within this distance is bounded: in particular, for Q = 2 κ δ , the probability that a random word in the space {0, 1} Q will be within Hamming distance ∆ = 2 κ δ -log c κ of a codeword will be negligible. Thus, we can conclude that the existence of a weak PRF in AC0[MOD2] implies that the punctured Reed-Muller code is hard to decode in some non-unique decoding regime. We formalize this in the following corollary.Corollary 17. Suppose for every c, C ∈ N with c ≤ C, there is an algorithm A running in time 2 n o(1) such that, given a generating matrix G of a punctured RM code over F 2 with parameters (log C n, n) and corrupted codeword y, A nds a codeword which is within relative distance 2 -log c n from y. Then there are no WPRFs in AC0[MOD2].

	with subexponential security implies what can be viewed as an instance of de-
	terministic LPN with subsubexponential hardness in the secret length (which
	lies strictly between quasipolynomial and subexponential).
	Consider a hardness of decoding interpretation of Corollary 16. Observe that
	the noise rate ε

Acknowledgements

We thank Andrej Bogdanov, Nicolas Resch, and the anonymous Crypto reviewers for helpful discussions and suggestions. E. Boyle supported by ISF grant 1861/16, AFOSR Award FA9550-21-1-0046, a Google Research Award, and ERC Project HSS (852952). G. Couteau supported by the ANR SCENE. N. Gilboa supported by ISF grant 2951/20, ERC grant 876110, and a grant by the BGU Cyber Center. Y. Ishai supported by ERC Project NTSC (742754), NSF-BSF grant 2015782, BSF grant 2018393, and ISF grant 2774/20. L. Kohl is funded by NWO Gravitation project QSC. Research of L. Kohl was done in part while at Technion, supported by ERC Project NTSC (742754). P. Scholl supported by the Danish Independent Research Council under Grant-ID DFF-6108-00169 (FoCC) and an Aarhus University Research Foundation starting grant. Low-Complexity Weak Pseudorandom Functions in AC0[MOD2]

Authors Suppressed Due to Excessive Length [START_REF] Feldman | On agnostic learning of parities, monomials, and halfspaces[END_REF] AC0 can be learned on all linear distributions Conjecture III: WPRF in AC0 on top of public parities Conjecture I:

Fig. 1: Relation between dierent assumptions/ conjectures. A → B means that A implies B. By a linear distribution we mean the uniform distribution over a linear subspace V ⊆ {0, 1} n , where dotted implications were already observed by [START_REF] Akavia | Candidate weak pseudorandom functions in AC 0 o MOD2[END_REF].

On Resistance to Linear Attacks

We also consider the resistance of our candidate to linear attacks, as was done for our other candidate in Section 3. While we have not been able to prove resistance of linear attacks for this candidate, we formulate a combinatorial conjecture which states, informally, that if the deterministic noise function is c-unbalanced for some constant c and far from all low-degree polynomials, then no attack from the linear attack framework can break the corresponding LPN with simple noise assumption. If true, this conjecture would imply that our candidate, the ABGKR candidate, as well as the LWR mod 6 candidate from [START_REF] Boneh | Exploring crypto dark matter: New simple PRF candidates and their applications[END_REF], cannot be broken by any of the above attacks. We provide preliminary observations regarding the plausibility of the conjecture; we view proving or disproving this conjecture as an interesting open question. For more details we refer to the full version

On WPRFs in AC0 with Public Parities

In this work we give a candidate construction of a weak PRF in AC0 • MOD2,

where the parities are secret. In particular, we conjecture that such a weak PRF exists (this is in the following referred to as Conjecture I).