Pseudozufällige Funktion

Eine pseudozufällige Funktion ist eine Familie von effizient berechenbaren Funktionen, die von einem Zufallsorakel praktisch ununterscheidbar sind. Jede Blockchiffre kann formal als pseudozufällige Funktion aufgefasst werden, die durch kryptografische Schlüssel parametrisiert ist.

Pseudozufällige Funktionen werden definiert als eine Familie von Funktionen $F:K\times X\to Y$ zwischen nichtleeren, endlichen Mengen $K$, $X$, $Y$, welche durch einen effizienten Algorithmus, üblicherweise eine deterministische Turingmaschine mit polynomieller Laufzeit und Speicher, berechnet wird. Für jeden Schlüssel $k\in K$ ist also durch $F_k(x)=F(k,x)$ eine Abbildung $F_k:X\to Y$ gegeben. Die maximale Anzahl aller möglichen Abbildungen von $X$ nach $Y$ ist gleichzeitig die obere Schranke für die maximale Schlüsselanzahl (d. h. $|K|$).

Ein Zufallsorakel ist ein Algorithmus, der für jede Eingabe aus $X$ eine (gleichverteilt) zufällig gezogene Ausgabe aus $Y$ zurückgibt, mit der Einschränkung, dass ein einmal bestimmter Funktionswert festliegt, also bei gleicher Anfrage auch die gleiche Antwort gegeben wird. Eine solche Funktionsfamilie F heißt pseudozufällig, wenn jeder effiziente Algorithmus, für ein (gleichverteilt) zufällig gezogenes und ihm nicht bekanntes $k$, zwischen $F_k$ und einem Zufallsorakel nur vernachlässigbar (in $k$) besser unterscheiden kann als durch Raten.

Zusammenhang mit anderen kryptographischen Primitiven

Durch Goldreich, Goldwasser und Micali wurde gezeigt, dass es möglich ist, aus einem kryptographischen Pseudozufallsgenerator eine pseudozufällige Funktion zu konstruieren. Umgekehrt kann auch eine solche pseudozufällige Funktion verwendet werden, um einen Pseudozufallsgenerator zu konstruieren, indem mehrere Auswertungen einer pseudozufälligen Funktion konkateniert werden.