A New Approach for LPN-Based Pseudorandom Functions: Low-Depth and Key-Homomorphic

We give new constructions of pseudorandom functions (PRFs) computable in NC1 from (variants of the) Learning Parity with Noise (LPN) assumption. Prior to our work, the only NC1-computable PRF from LPN-style assumptions was due to Boyle et al. (FOCS 2020) who constructed a weak PRF from a new heuristic variant of LPN called variable-density LPN. We give the following results: (1) A weak PRF computable in NC1 from standard LPN, (2) A (strong) encoded-input PRF (EI-PRF) computable in NC1 from sparse LPN (An EI-PRF is a PRF whose input domain is restricted to an efficiently sampleable and recognizable set. The input encoding can be computed in NC1+є for any constant є > 0, implying a strong PRF computable in NC1+є), and (3) A (strong) PRF computable in NC1 from a (new, heuristic) seeded LPN assumption. In our assumption, each column of the public LPN matrix is generated by an n-wise independent distribution. Supporting evidence for the security of the assumption is given by showing resilience to linear tests. As a bonus, all of our PRF constructions are key-homomorphic, an algebraic property that is useful in many symmetric-cryptography applications. No previously-known LPN-based PRFs have this property, even if we completely ignore depth-efficiency. In fact, our constructions support key homomorphism for linear functions (and not only additive), a property that no previously-known PRF satisfies, including ones from LWE. Additionally, all of our PRF constructions nicely fit into the substitution-permutation network (SPN) design framework used in modern block ciphers (e.g. AES). No prior PRF construction that has a reduction to a standard cryptographic assumptions (let alone LPN) has an SPN-like structure. Technically, all of our constructions of PFRs leverage a new recursive derandomization technique for LPN instances, which allows us to generate LPN error terms deterministically. This technique is inspired by a related idea from the LWE literature (Kim, EUROCRYPT 2020) for which devising an LPN analogue has been an outstanding open problem.