文章基本信息

标题：On Learning versus Distinguishing and the Minimal Hardware Complexity of Pseudorandom Function Generators
本地全文：下载
作者：Matthias Krause, Stefan Lucks
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：\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 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}
关键词：Boolean Complexity Theory, Computational Distinguishability, cryptography, learnability, Pseudorandomness