Abstract
A polynomialstretch pseudorandom generator (PPRG) in NC⁰ (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 sublinearstretch pseudorandom generators in NC⁰ by the existence of logspacecomputable oneway functions, but characterizing PPRGs in NC⁰ seems out of reach at present. Therefore, it is natural to ask which sort of hardness notion is essential for constructing PPRGs in NC⁰. Particularly, to the best of our knowledge, all the previously known candidates for PPRGs in NC⁰ follow only one framework based on Goldreich’s oneway function.
In this paper, we present a new learningtheoretic characterization for PPRGs in NC⁰ and related classes. Specifically, we consider the averagecase hardness of learning for wellstudied classes in parameterized settings, where the number of samples is restricted to fixedparameter tractable (FPT), and show that the following are equivalent:
 The existence of (a collection of) PPRGs in NC⁰.
 The averagecase hardness of learning sparse ?₂polynomials on a sparse example distribution and an NC⁰samplable target distribution (i.e., a distribution on target functions).
 The averagecase hardness of learning Fouriersparse functions on a sparse example distribution and an NC⁰samplable target distribution.
 The averagecase hardness of learning constantdepth parity decision trees on a sparse example distribution and an NC⁰samplable target distribution. Furthermore, we characterize a (single) PPRG in parityNC⁰ by the averagecase hardness of learning constantdegree ?₂polynomials on a uniform example distribution with FPT samples. Based on our results, we propose new candidates for PPRGs in NC⁰ and related classes under a hardness assumption on a natural learning problem. An important property of PPRGs in NC⁰ 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 metatheorem for the first result. For the second result on PPRGs in parityNC⁰, we use a different technique of pseudorandom ?₂polynomials.
BibTeX  Entry
@InProceedings{hirahara_et_al:LIPIcs.ITCS.2023.70,
author = {Hirahara, Shuichi and Nanashima, Mikito},
title = {{Learning Versus Pseudorandom Generators in Constant Parallel Time}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {70:170:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772631},
ISSN = {18688969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17573},
URN = {urn:nbn:de:0030drops175736},
doi = {10.4230/LIPIcs.ITCS.2023.70},
annote = {Keywords: Parallel cryptography, polynomialstretch pseudorandom generators in NC⁰, PAC learning, averagecase complexity, fixedparameter tractability}
}
Keywords: 

Parallel cryptography, polynomialstretch pseudorandom generators in NC⁰, PAC learning, averagecase complexity, fixedparameter tractability 
Collection: 

14th Innovations in Theoretical Computer Science Conference (ITCS 2023) 
Issue Date: 

2023 
Date of publication: 

01.02.2023 