Low-Complexity Weak Pseudorandom Functions in $\mathtt {AC}0[\mathtt {MOD}2]$

A weak pseudorandom function (WPRF) is a keyed function f k : 0, 1 n → 0, 1 such that, for a random key k, a collection of samples (x, f k (x)), for uniformly random inputs x, cannot be eciently distinguished from totally random input-output pairs (x, y). We study WPRFs in AC0[MOD2], the class of functions computable by AC0 circuits with parity gates, making the following contributions.

WPRF by sparse polynomials. We propose the rst WPRF candidate that can be computed by sparse multivariate polynomials over F2. We prove that it has subexponential security against linear and algebraic attacks. WPRF in AC0 • MOD2. We study the existence of WPRFs computed by AC0 circuits over parity gates. We propose a modied version of a previous WPRF candidate of Akavia et al. (ITCS 2014), and prove that it resists the algebraic attacks that were used by Bogdanov and Rosen (ECCC 2017) to break the original candidate in quasipolynomial time. We give evidence against the possibility of using public parity gates and relate this question to other conjectures. Between Lapland and Cryptomania. We show that WPRFs in AC0[MOD2] imply a variant of the Learning Parity with Noise (LPN) assumption. We further show that WPRFs in a subclass of AC0[MOD2]

that includes a recent candidate by Boyle et al. (FOCS 2020) imply, under a seemingly weak additional conjecture, public-key encryption. Authors Suppressed Due to Excessive Length to contain PRFs is inherently unlearnable, even when membership queries are allowed. In this light, understanding the feasibility of low-complexity PRFs corresponds to exploring the border between the learnable and the unlearnable. More broadly, the study of low-complexity PRFs has proven to be a rich and fruitful research direction, motivated by many connections with circuit lower bounds [54,43,56], derandomization [49,61], and high-end cryptographic applications [2,42,17,14,8,15]. We focus on the existence of weak pseudorandom functions (WPRFs) in AC0[MOD2], the class of polynomial-size, constant-depth circuits over AND, OR, XOR gates and negations. 1 Informally, a WPRF relaxes a PRF by restricting the distinguisher to only get input-output pairs for uniformly random inputs x, as opposed to chosen inputs x. WPRFs imply hardness results for learning (without membership queries) under the uniform distribution, and can serve as useful building blocks for most symmetric cryptographic primitives, such as private-key encryption and message authentication [46]. As a result, minimizing their complexity can lead to improving the complexity of these primitives.

Levels of security. We say that a WPRF has quasipolynomial, subexponential, or exponential security when the distinguisher's circuit size is bounded by a corresponding function of the key length. Concretely, there exists c > 0 such that every circuit of size T = n log c n , T = 2 n c , or T = 2 cn (respectively) has at most 1/T distinguishing advantage between f k and a random function, for all suciently large key lengths n, given unlimited access to examples on uniformly random inputs. In the case of quasipolynomial and subexponential security, we can equivalently let n be the input length, since the key length and input length are polynomially related. In this work we consider subexponential security by default. This is typically the best level of security achieved by constructions from standard cryptographic assumptions.

WPRFs in low complexity classes. We return to the question of WPRFs in AC0 [MOD2]. At the lower end, much is known about the power and limitations of AC0. This includes unconditional circuit lower bounds (e.g. AC0 cannot compute parity [28,32]), derandomization (e.g. AC0 cannot distinguish any polylog-wise independent distribution from the uniform distribution [16]), and learning algorithms (e.g. AC0 can be learned from quasipolynomially many samples under the uniform distribution [41]). The latter imply, in particular, that AC0 cannot contain a WPRF with better than quasipolynomial security. Slightly above AC0[MOD2], the picture is also relatively clear: strong PRFs with subexponential security exist in the class TC0 (of polynomial-size constant-depth circuits with 1 More precisely, AND/OR/XOR gates can have an unbounded fan-in, and depth is dened to be the length of the longest path from an input to the output, not counting negations. As is common in the study of constant-depth PRFs, we consider the complexity of mapping the input to the output when the key is xed.