Pseudorandom Functions in $\mathsf{NC}^1$ from LWE/LPN/CDH (Or: How to Build PRFs in $\mathsf{NC}^1$, Generically)

Abstract

We present a new generic transformation from weak PRFs computable in depth $d(n) = \Omega(\log n)$ to strong PRFs computable in depth $O(d(n))$. This construction refines the classical tree-based paradigm of GGM by {tapering} the internal state so the per-level depth decreases geometrically. We complement the above with new depth-efficient weak PRF constructions based on various standard assumptions. As a corollary, we obtain new $\mathsf{NC}^1$-computable PRFs from various classical assumptions, resolving several long-standing open problems. Concretely, for the first time, we obtain $\mathsf{NC}^1$-computable PRFs: (1) from the \textbf{Learning With Errors (LWE)} assumption with a polynomial modulus-to-noise ratio, improving upon prior low-depth constructions that required Ring-LWE with super-polynomial ratios [Banerjee-Peikert-Rosen, EUROCRYPT 2012]; (2)from the standard \textbf{Learning Parity with Noise (LPN)} assumption, removing the need for structured LPN variants [Boyle et al., FOCS 2020], [Ding-Jain-Komargodski, STOC 2025]; (3) from the \textbf{Computational Diffie-Hellman (CDH)} assumption; prior works relied on the stronger Decisional Diffie-Hellman (DDH) or generalized Diffie-Hellman (GDH) assumptions [Naor-Reingold, FOCS'97, J. ACM'04].