Wie man zufällige Funktionen konstruiert

Eine konstruktive Theorie der Zufälligkeit für Funktionen, basierend auf Berechnungskomplexität, wird entwickelt, und ein Generator für pseudorandom Funktionen wird vorgestellt. Dieser Generator ist ein deterministischer Algorithmus mit polynomialer Laufzeit, der Paare (g, r), wobei g eine beliebige Einwegfunktion und r eine zufällige k-Bit-Zeichenkette ist, in polynomiell berechenbare Funktionen ƒ r: 1, …, 2 k → 1, …, 2 k umwandelt. Diese ƒ r können von keinem probabilistischen Algorithmus mit polynomialer Laufzeit, der Werte der Funktion an frei wählbaren Argumenten abfragt und erhält, von zufälligen Funktionen unterschieden werden. Das Ergebnis hat Anwendungen in der Kryptographie, zufälligen Konstruktionen und Komplexitätstheorie.