Paper 2025/898

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

Abstract

We give new constructions of pseudorandom functions (PRFs) computable in $\mathsf{NC}^1$ from (variants of the) Learning Parity with Noise (LPN) assumption. Prior to our work, the only $\mathsf{NC}^1$-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 three results: (1) A weak PRF computable in $\mathsf{NC}^1$ from standard LPN. (2) A (strong) encoded-input PRF (EI-PRF) computable in $\mathsf{NC}^1$ 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 $\mathsf{NC}^{1+\epsilon}$ for any constant $\epsilon > 0$, implying a strong PRF computable in $\mathsf{NC}^{1+\epsilon}$. (3) A (strong) PRF computable in $\mathsf{NC}^1$ from a (new, heuristic) seeded LPN assumption. In our assumption, columns of the public LPN matrix are 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 are key-homomorphic, 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 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.