On learning versus distinguishing and the minimal hardware complexity of pseudorandom function generators


Krause, Matthias ; Lucks, Stefan



URL: https://eccc.weizmann.ac.il/report/2000/014/
Additional URL: https://www.researchgate.net/publication/220138771...
Document Type: Working paper
Year of publication: 2000
The title of a journal, publication series: Electronic Colloquium on Computational Complexity : ECCC
Volume: TR00-014
Place of publication: Trier
Publishing house: Universität Trier
ISSN: 1433-8092
Publication language: English
Institution: School of Business Informatics and Mathematics > Theoretische Informatik (Krause)
Subject: 004 Computer science, internet
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}.
Additional information: Online-Ressource

Dieser Eintrag ist Teil der Universitätsbibliographie.




Metadata export


Citation


+ Search Authors in

+ Page Views

Hits per month over past year

Detailed information



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item