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

Youlong Ding, Aayush Jain, Ilan Komargodski

We obtain new ${\mathsf{NC}}^1$-computable pseudorandom functions (PRFs) from various standard assumptions, resolving several long-standing open problems. Concretely, for the first t…