A polynomial-stretch pseudorandom generator (PPRG) in NC$^0$ (i.e., constant parallel time) is one of the most important cryptographic primitives, especially for constructing highly efficient cryptography and indistinguishability obfuscation. The celebrated work (Applebaum, Ishai, and Kushilevitz, SIAM Journal on Computing, 2006) on randomized encodings yields the characterization of sublinear-stretch pseudorandom generators in NC$^0$ by the existence of logspace-computable one-way functions, but characterizing PPRGs in NC$^0$ seems out of reach at present. Therefore, it is natural to ask which sort of hardness notion is essential for constructing PPRGs in NC$^0$. Particularly, to the best of our knowledge, all the previously known candidates for PPRGs in NC$^0$ follow only one framework based on Goldreich's one-way function.

In this paper, we present a new learning-theoretic characterization for PPRGs in NC$^0$ and related classes. Specifically, we consider the average-case hardness of learning for well-studied classes in parameterized settings, where the number of samples is restricted to fixed-parameter tractable (FPT), and show that the following are equivalent:
(i) The existence of (a collection of) PPRGs in NC$^0$.
(ii) The average-case hardness of learning sparse $\mathbb{F}_2$-polynomials on a sparse example distribution and an NC$^0$-samplable target distribution (i.e., a distribution on target functions).
(iii) The average-case hardness of learning Fourier-sparse functions on a sparse example distribution and an NC$^0$-samplable target distribution.
(iv) The average-case hardness of learning constant-depth parity decision trees on a sparse example distribution and an NC$^0$-samplable target distribution.
Furthermore, we characterize a (single) PPRG in $\oplus$-NC$^0$ by the average-case hardness of learning constant-degree $\mathbb{F}_2$-polynomials on a uniform example distribution with FPT samples. Based on our results, we propose new candidates for PPRGs in NC$^0$ and related classes under a hardness assumption on a natural learning problem. An important property of PPRGs in NC$^0$ constructed in our framework is that the output bits are computed by various predicates; thus, it seems to resist an attack that depends on a specific property of one fixed predicate.

Conceptually, the main contribution of this study is to formalize a theory of FPT dualization of concept classes, which yields a meta-theorem for the first result. For the second result on PPRGs in $\oplus$-NC$^0$, we use a different technique of pseudorandom $\mathbb{F}_2$-polynomials.