On Learning versus Distinguishing and the Minimal Hardware Complexity of Pseudorandom Function Generators

摘要

egin{abstract} A set F of n-ary Boolean functions is called a pseudorandom function generator (PRFG) if communicating with a randomly chosen secret function from F cannot be efficiently distinguished from communicating with a truly random function. We ask for the minimal hardware complexity of a PRFG. This question is motivated by design aspects of secure secret key cryptosystems, which on the one hand should have very fast hardware implementations, and on the other hand, for security reasons, should behave like PRFGs. By constructing appropriate distinguishing algorithms we show for a wide range of basic nonuniform complexity classes, induced by depth restricted branching programs and several types of constant depth circuits, that they do not contain PRFGs. Observe that in cite{KL00} we could show that TC30 seems to contain a PRFG. Moreover, we relate our concept of distinguishability to the learnability of Boolean concept classes. In particular, we show that, if membership queries are forbidden, each efficient distinguishing algorithm can be converted into a weak PAC learning algorithm. Finally, we compare distinguishability with the concept of Natural Proofs and strengthen the main observation of {it Razborov} and {it Rudich} in cite{RR97}. end{abstract}