Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-014 | 16th February 2000 00:00

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



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}.

ISSN 1433-8092 | Imprint