Welcome to the resource topic for 2025/898
Title:
A New Approach for LPN-based Pseudorandom Functions: Low-Depth and Key-Homomorphic
Authors: Youlong Ding, Aayush Jain, Ilan Komargodski
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.
ePrint: https://eprint.iacr.org/2025/898
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .