|
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. |
 Suche Autoren in
Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail
Actions (login required)
 |
Eintrag anzeigen |
|
|
