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

Youlong Ding, Aayush Jain, Ilan Komargodski

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…