Low-complexity weak pseudorandom functions in AC0[MOD2]

A weak pseudorandom function (WPRF) is a keyed function fk:{0,1}n→{0,1} such that, for a random key k, a collection of samples (x,fk(x)), for uniformly random inputs x, cannot be efficiently 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 first 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 modified 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.