__
TR00-014 | 16th February 2000 00:00
__

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

**Abstract:**
\begin{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 $TC^0_3$ 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}