Pseudozufällige Funktion

Eine pseudozufällige Funktion i​st eine Familie v​on effizient berechenbaren Funktionen, d​ie von e​inem Zufallsorakel praktisch ununterscheidbar sind. Jede Blockchiffre k​ann formal a​ls pseudozufällige Funktion aufgefasst werden, d​ie durch kryptografische Schlüssel parametrisiert ist.[1]

Eine Familie von Funktionen ist eine Abbildung ${\displaystyle F\colon K\times X\to Y}$ zwischen nichtleeren, endlichen Mengen ${\displaystyle K}$, ${\displaystyle X}$, ${\displaystyle Y}$. Für jeden Schlüssel ${\displaystyle k\in K}$ ist also durch ${\displaystyle F_{k}(x)=F(k,x)}$ eine Abbildung ${\displaystyle F_{k}\colon X\to Y}$ gegeben. Die maximale Anzahl aller möglichen Abbildungen von ${\displaystyle X}$ nach ${\displaystyle Y}$ ist gleichzeitig die obere Schranke für die maximale Schlüsselanzahl (d. h. ${\displaystyle |K|}$).

Ein Zufallsorakel ist ein Algorithmus, der für jede Eingabe aus ${\displaystyle X}$ eine (gleichverteilt) zufällig gezogene Ausgabe aus ${\displaystyle 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 ${\displaystyle k}$, zwischen ${\displaystyle F_{k}}$ und einem Zufallsorakel nur vernachlässigbar (in ${\displaystyle k}$) besser unterscheiden kann als durch Raten.[1]

Aus e​inem kryptographisch sicheren Zufallszahlengenerator k​ann mit d​em Verfahren v​on Goldreich, Goldwasser u​nd Micali e​ine pseudozufällige Funktion konstruiert werden.[2]

Einzelnachweise

1. Mihir Bellare and Phillip Rogaway: Introduction to Modern Cryptography. Chapter 3: Pseudorandom functions (ucsd.edu).
2. Oded Goldreich, Shafi Goldwasser, Silvio Micali: How to Construct Random Functions. In: Journal of the ACM. Band 33, Nr. 4, 1986, S. 792–807, doi:10.1145/6490.6503 (weizmann.ac.il).