Learning Versus Pseudorandom Generators in Constant Parallel Time

Mikito Nanashima (Tokyo Institute of Technology)
Lower Bounds, Learning, and Average-Case Complexity

Abstract
A polynomial-stretch pseudorandom generator (PPRG) in NC0 is one of the most important cryptographic primitives. In the talk, we present a new learning-theoretic characterization for PPRGs in NC0 and related classes by the average-case hardness of learning for well-studied classes in parameterized settings.