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.

Eine Familie von Funktionen ist eine Abbildung F: 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: X \to Y gegeben. 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.  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).