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.

Eine Familie von Funktionen ist eine Abbildung $F\colon K\times X\to Y$ zwischen nichtleeren, endlichen Mengen $K$, $X$, $Y$. Für jeden Schlüssel $k\in K$ ist also durch $F_{k}(x)=F(k,x)$ eine Abbildung $F_{k}\colon 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.

Aus einem kryptographisch sicheren Zufallszahlengenerator kann mit dem Verfahren von Goldreich, Goldwasser und Micali eine pseudozufällige Funktion konstruiert werden.