ECCC-Report TR00-014https://eccc.weizmann.ac.il/report/2000/014Comments and Revisions published for TR00-014en-usMon, 06 Mar 2000 15:30:49 +0200
Paper TR00-014
| On Learning versus Distinguishing and the Minimal Hardware Complexity of Pseudorandom Function Generators |
Matthias Krause,
Stefan Lucks
https://eccc.weizmann.ac.il/report/2000/014\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}
Mon, 06 Mar 2000 15:30:49 +0200https://eccc.weizmann.ac.il/report/2000/014