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/
Weitere URL: https://www.researchgate.net/publication/220138771...
Dokumenttyp: Arbeitspapier
Erscheinungsjahr: 2000
Titel einer Zeitschrift oder einer Reihe: Electronic Colloquium on Computational Complexity : ECCC
Band/Volume: TR00-014
Ort der Veröffentlichung: Trier
Verlag: Universität Trier
ISSN: 1433-8092
Sprache der Veröffentlichung: Englisch
Einrichtung: Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Theoretische Informatik (Krause 1996-)
Fachgebiet: 004 Informatik
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}.
Zusätzliche Informationen: Online-Ressource




Dieser Eintrag ist Teil der Universitätsbibliographie.




Metadaten-Export


Zitation


+ Suche Autoren in

+ Aufruf-Statistik

Aufrufe im letzten Jahr

Detaillierte Angaben



Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail


Actions (login required)

Eintrag anzeigen Eintrag anzeigen