Pseudozufällige Funktion

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.[1]

Eine Familie von Funktionen ist eine Abbildung F: K \times X \to Y zwischen nichleeren, 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: 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.[1]

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

Einzelnachweise[Bearbeiten]

  1. a b  Mihir Bellare and Phillip Rogaway: Introduction to Modern Cryptography. Chapter 3: Pseudorandom functions (http://cseweb.ucsd.edu/~mihir/cse207/).
  2.  Oded Goldreich, Shafi Goldwasser, Silvio Micali: How to Construct Random Functions. In: Journal of the ACM. 33, Nr. 4, 1986, S. 792-807, doi:10.1145/6490.6503 (http://www.math.weizmann.ac.il/~/oded/ggm.html).