Familie der Pseudozufallsfunktionen

In der Kryptographie bezeichnet man als Familie pseudozufälliger Funktionen (PRF ) eine Menge effizient berechenbarer Funktionen , die ein Zufallsorakel folgendermaßen emulieren: Kein effizienter Algorithmus kann (mit signifikantem Vorteil ) zwischen einer zufällig aus der PRF-Familie gewählten Funktion und einem Zufallsorakel (einer Funktion, deren Ausgaben vollständig zufällig festgelegt sind) unterscheiden. Pseudozufällige Funktionen sind unverzichtbare Werkzeuge für die Entwicklung kryptographischer Primitiven , insbesondere sicherer Verschlüsselungsverfahren .

Pseudozufallsfunktionen sind nicht mit Pseudozufallsgeneratoren (PRGs) zu verwechseln. Ein PRG garantiert, dass ein einzelner Ausgabewert zufällig erscheint , wenn die Eingabewerte zufällig gewählt wurden. Eine Pseudozufallsfunktion hingegen garantiert, dass alle ihre Ausgaben zufällig erscheinen, unabhängig davon, wie die zugehörigen Eingabewerte gewählt wurden, sofern die Funktion zufällig aus der Familie der Pseudozufallsfunktionen gezogen wurde.

Eine Familie pseudozufälliger Funktionen lässt sich aus jedem beliebigen Pseudozufallsgenerator konstruieren, beispielsweise mithilfe der von Goldreich , Goldwasser und Micali vorgestellten „GGM“-Konstruktion . ^{[ 1 ]} Obwohl in der Praxis meist Blockchiffren verwendet werden, wenn eine pseudozufällige Funktion benötigt wird, bilden sie im Allgemeinen keine Familie pseudozufälliger Funktionen, da Blockchiffren wie AES nur für eine begrenzte Anzahl von Eingabe- und Schlüssellängen definiert sind. ^{[ 2 ]}

Eine PRF ist eine effiziente (d. h. in Polynomialzeit berechenbare), deterministische Funktion, die zwei verschiedene Mengen (Definitionsbereich und Wertebereich) abbildet und wie eine echte Zufallsfunktion aussieht.

Im Prinzip bestünde eine wirklich zufällige Funktion aus einer Nachschlagetabelle mit gleichverteilten Zufallswerten. In der Praxis erhält eine PRF jedoch eine Eingabezeichenkette aus dem Definitionsbereich und einen internen Zufallswert und wird mehrmals mit derselben Eingabezeichenkette und demselben Wert ausgeführt, wobei immer derselbe Wert zurückgegeben wird. Trotzdem erscheint die Ausgabe bei einer beliebigen Eingabezeichenkette zufällig, wenn der Zufallswert aus einer Gleichverteilung stammt.

Eine PRF gilt als gut, wenn ihr Verhalten von dem einer echten Zufallsfunktion nicht zu unterscheiden ist. Daher sollte es bei gegebener Ausgabe einer echten Zufallsfunktion oder einer PRF keine effiziente Methode geben, um korrekt zu bestimmen, ob die Ausgabe von der echten Zufallsfunktion oder der PRF erzeugt wurde.

Pseudozufallsfunktionen benötigen Eingaben , wobei der Kleene-Stern ist . Sowohl die Eingabe- als auch die Ausgabegröße hängen ausschließlich von der Indexgröße ab . ${\displaystyle x\in \{0,1\}^{*}}$${\displaystyle {}^{*}}$${\displaystyle I=|x|}$${\displaystyle \lambda }$${\displaystyle n:=|s|}$

Eine Funktionsfamilie,

${\displaystyle f_{s}:\left\{0,1\right\}^{I(n)}\rightarrow \left\{0,1\right\}^{\lambda (n)}}$

ist pseudozufällig, wenn die folgenden Bedingungen erfüllt sind:

• Es existiert ein Polynomzeitalgorithmus, der für beliebige und berechnet .${\displaystyle f_{s}(x)}$${\displaystyle s}$${\displaystyle x}$
• Sei die Verteilung der Funktionen, wobei gleichverteilt über ist , und sei die Gleichverteilung über der Menge aller Funktionen von nach . Dann fordern wir, dass und rechnerisch nicht unterscheidbar sind, wobei n der Sicherheitsparameter ist . Das heißt, für jeden Angreifer, der das Orakel einer Funktion abfragen kann, die entweder aus oder stammt, ist der Vorteil, den er dadurch hat, die Art des ihm gegebenen Orakels unterscheiden zu können, in vernachlässigbar . ^{[ 3 ]}${\displaystyle F_{n}}$${\displaystyle f_{s}}$${\displaystyle s}$${\displaystyle \{0,1\}^{n}}$${\displaystyle RF_{n}}$${\displaystyle \{0,1\}^{I(n)}}$${\displaystyle \{0,1\}^{\lambda (n)}}$${\displaystyle F_{n}}$${\displaystyle RF_{n}}$${\displaystyle F_{n}}$${\displaystyle RF_{n}}$${\displaystyle n}$

Bei einer oblivious pseudorandom function (OPRF) werden Informationen vor den beiden an einer PRF beteiligten Parteien verborgen. ^{[ 4 ]} Wenn Alice beispielsweise ihren geheimen Wert kryptografisch hasht, den Hash kryptografisch verschlüsselt, um die Nachricht zu erzeugen, die sie an Bob sendet, und Bob seinen geheimen Wert hinzufügt und das Ergebnis an Alice zurückgibt, die es entschlüsselt, um die endgültige Ausgabe zu erhalten, kann Bob weder Alices geheimen Wert noch die endgültige Ausgabe sehen, und Alice kann Bobs geheime Eingabe nicht sehen. Sie sieht jedoch die endgültige Ausgabe, die eine PRF der beiden Eingaben ist – eine PRF von Alices und Bobs geheimem Wert. ^{[ 5 ]} Dies ermöglicht sichere Transaktionen sensibler kryptografischer Informationen selbst zwischen nicht vertrauenswürdigen Parteien.

Ein OPRF wird in einigen Implementierungen der passwortbasierten Schlüsselvereinbarung verwendet . ^{[ 5 ]}

In der Kennwortüberwachungsfunktion von Microsoft Edge wird eine OPRF-Datei verwendet . ^{[ 6 ]}

PRFs können verwendet werden für: ^{[ 7 ]}

1. Dynamisches perfektes Hashing ; selbst wenn der Angreifer die Schlüsselverteilung in Abhängigkeit von den Werten, die die Hash-Funktion den vorherigen Schlüsseln zugewiesen hat, ändern kann, kann der Angreifer keine Kollisionen erzwingen.
2. Entwicklung deterministischer, speicherloser Authentifizierungsschemata ( basierend auf Message Authentication Codes ), die nachweislich sicher gegen Angriffe mit gewählter Nachricht sind.
3. Verteilung fälschungssicherer Identifikationsnummern , die von Stationen mit nur geringem Speicherplatz lokal verifiziert werden können.
4. Entwicklung von Freund-Feind-Erkennungssystemen .

• Pseudozufällige Permutation

• Goldreich, Oded (2001). Grundlagen der Kryptographie: Grundlegende Werkzeuge . Cambridge: Cambridge University Press. ISBN 978-0-511-54689-1Die
• Pass, Rafael, Ein Kurs in Kryptographie (PDF) , abgerufen am 22. Dezember 2015