Cryptography in NC\(^0\).

*(English)*Zbl 1126.94014The authors focus on the parallel time-complexity of two basic cryptographic primitives: one-way functions (OWF) and pseudorandom generators (PRG). They study the possibility of implementing instances of these primitives by NC\(^0\) functions, namely by functions in which each output bit depends on a constant number of input bits. The paper provides strong positive evidence for the possibility of cryptography in NC\(^0\). The main result is that every “moderately easy” OWF (resp., PRG), say computable in NC\(^1\), can be compiled into a corresponding OWF (resp., “low-stretch” PRG) in which each output bit depends on at most 4 input bits. A similar compiler can also be obtained for other cryptographic primitives such as one-way permutations, encryption, signatures, commitment, and collision-resistant hashing. These techniques can also be applied to obtain (unconditional) constructions of “noncryptographic” PRGs. In particular, \(\epsilon\)-biased generators and a PRG for space-bounded computation in which each output bit depends on only 3 input bits could be obtained. These results make use of the machinery of randomizing polynomials [Y. Ishai and E. Kushilevitz, Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS), Redondo Beach, CA 2000, 294–304 (2000)], which was originally motivated by questions in the domain of information-theoretic secure multiparty computation.

Reviewer: Vladimír Lacko (Košice)

##### MSC:

94A60 | Cryptography |

68P25 | Data encryption (aspects in computer science) |

68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |