💻 computer science

Lower Bounds on Black-Box Constructions of Pseudorandom Functions

Diese Arbeit stellt fest, dass keine vollkommen Black-Box-Konstruktion einer Pseudozufallsfunktion (PRF) aus einem Pseudozufallsgenerator (PRG) $o(n/\log n)$ nicht-adaptive Aufrufe an das PRG erreichen kann, selbst für schwache PRFs mit einbityigen Ausgaben, und liefert damit starke untere Schranken für die Effizienz solcher Konstruktionen und lässt die Möglichkeit einer Konstruktion mit einem einzigen Aufruf als eine bedeutende offene Herausforderung.

Ursprüngliche Autoren: Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam

Veröffentlicht 2026-08-17

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das Dilemma des digitalen Schlossers

Stellen Sie sich vor, Sie sind ein meisterhafter Schlossermeister, der versucht, eine unknackbare Tresortür zu bauen. In der Welt der digitalen Sicherheit ist dieser „Tresor“ eine Pseudozufallsfunktion (PRF). Betrachten Sie eine PRF als eine magische Maschine: Sie füttern sie mit einem geheimen Schlüssel und einer spezifischen Eingabe (wie einer Zimmernummer), und sie spuckt eine Zeichenfolge von Zahlen aus, die für jeden Beobachter vollkommen zufällig aussieht. Wenn Sie jedoch denselben geheimen Schlüssel erneut verwenden, erzeugt sie immer exakt dieselbe „zufällige“ Zeichenfolge. Diese Beständigkeit ist es, was sie nützlich macht, um Ihre E-Mails zu sichern, Ihre Banktransaktionen zu schützen und Ihre Passwörter sicher zu halten.

Um diese magische Maschine zu bauen, nutzen Kryptographen oft etwas Einfacheres, das man als Pseudozufallsgenerator (PRG) bezeichnet. Ein PRG ist wie ein winziger, effizienter Samen, der zu einem massiven, zufällig aussehenden Wald heranwächst. Er nimmt einen kurzen, geheimen String und streckt ihn zu einem viel längeren aus, der für jedes Computerprogramm zufällig aussieht. Die große Frage in der Kryptographie war bisher: Wie oft müssen wir diese „Samen-Streckungs-Maschine“ benutzen, um unsere „Tresortür“ zu bauen?

Seit Jahrzehnten ist das Standardrezept (bekannt als die GGM-Konstruktion) die Verwendung der Samen-Streckungs-Maschine immer und immer wieder in einer baumartigen Struktur, etwa $\omega(\log n)$ mal (wobei $n$ die Größe des Samens ist). Es funktioniert hervorragend, aber es fühlt sich etwas klobig an. Gibt es eine Abkürzung? Könnten wir eine perfekte Tresortür bauen, indem wir die Samen-Streckungs-Maschine nur einmal benutzen? Oder vielleicht nur ein paar Mal? Dieses Paper taucht tief in diese Frage ein und agiert wie ein Detektiv, der zu beweisen versucht, dass man – egal wie clever man ist – eine sichere Tresortür nicht mit zu wenigen Streckungen des Samens bauen kann.

Die große Entdeckung des Papers: Das „Zu wenig“-Problem

Dieses Paper, geschrieben von Bar Alon, Itai Dinur und Muthuramakrishnan Venkitasubramaniam, befasst sich mit der grundlegenden Frage: Was ist die absolute Mindestanzahl an Aufrufen, die wir eines Pseudozufallsgenerators (PRG) tätigen müssen, um eine Pseudozufallsfunktion (PRF) zu bauen?

Die Autoren beweisen, dass für eine spezifische und sehr vernünftige Art von Konstruktion die Antwort „viel mehr, als man hoffen mag“ lautet. Konkret zeigen sie, dass man keine sichere PRF mit einer „vollständig Black-Box“-Methode bauen kann, wenn man den PRG nur eine sehr geringe Anzahl von Malen aufruft – nämlich weniger als etwa $n / \log n$ Mal (wobei $n$ die Länge des Eingabewerts des PRG ist).

Um ihren Beweis zu verstehen, stellen Sie sich ein Spiel namens „Finde den Fake“ vor:

Das Setup: Ein „Reduktion“ (der Erbauer) versucht, eine PRF unter Verwendung eines PRG zu erstellen. Er hat auch einen „Adversary“ (einen Hacker), der versucht zu unterscheiden, ob die PRF echt oder eine Zufallsfunktion ist.
Der Trick: Die Autoren stellen sich ein Szenario vor, in dem der Erbauer „abfragebeschränkt“ (query-bounded) ist. Das bedeutet, der Ersteller kann den Hacker um Hilfe bitten, aber die Anzahl der Male, die er fragen kann, ist begrenzt und explodiert nicht basierend auf der Anzahl der Fragen, die der Hacker stellt.
Der Gegenangriff: Die Autoren konstruieren einen „Realen Adversary“ und einen „Idealen Adversary“.
- Der Ideale Adversary ist ein superstarker, langsamer Computer, der jeden möglichen geheimen Schlüssel prüfen kann, um zu sehen, ob er zu den Daten passt. Er kann leicht erkennen, ob eine Funktion eine PRF oder eine Zufallsfunktion ist.
- Der Reale Adversary ist derjenige, den der Erbauer tatsächlich verwendet. Er besitzt keine Superkräfte; er sieht nur die begrenzten Fragen, die der Erbauer an den PRG gestellt hat.
Die Enthüllung: Die Autoren beweisen, dass der „Reale Adversary“ den „Idealen Adversary“ perfekt imitieren kann, ohne die Sicherheit des PRG zu brechen, wenn der Erbauer zu wenige Aufrufe tätigt. Dies erzeugt ein Paradoxon: Wenn der Erbauer eine sichere PRF mit so wenigen Aufrufen bauen könnte, wäre er auch in der Lage, den PRG selbst mit einer Methode zu brechen, die zu langsam für die Praxis wäre, was der Annahme widerspricht, dass der PRG sicher ist.

Das Hauptergebnis:
Das Paper beweist, dass es für nicht-adaptive Konstruktionen (bei denen der Erbauer alle PRG-Fragen entscheidet, bevor er eine Antwort sieht) unmöglich ist, eine PRF mit weniger als $o(n / \log n)$ Aufrufen des PRG zu bauen. Dies gilt selbst dann, wenn die PRF nur ein einzelnes Bit (eine 0 oder 1) ausgibt und selbst wenn der Hacker darauf beschränkt ist, einfache, zufällige Fragen zu stellen.

Das „Langer-Output“-Ergebnis:
Die Autoren haben auch PRFs untersucht, die lange Datenstränge produzieren (nicht nur ein einzelnes Bit). Sie haben bewiesen, dass selbst wenn der Erbauer „adaptiv“ sein darf (Fragen nacheinander stellt und die Antworten nutzt, um die nächste Frage zu entscheiden), es immer noch eine harte Grenze gibt. Wenn der PRG den Input nur ein kleines Stück streckt, benötigt man mindestens etwa $out / \log n$ Aufrufe. Wenn der PRG den Input um ein großes Maß streckt, benötigt man mindestens $out / r$ Aufrufe.

Was dies für den „Ein-Aufruf-Traum“ bedeutet

Lange Zeit fragten sich Kryptographen, ob eine „Single-Call“-Konstruktion möglich sei – also den Bau einer perfekten PRF durch die einmalige Streckung des Samens.

Für nicht-adaptive Methoden: Dieses Paper schließt dies effektiv aus. Man kann keine sichere PRF mit einer konstanten Anzahl von Aufrufen (wie 1, 2 oder 10) bauen, wenn die Eingabegröße wächst. Die Mathematik lässt dies schlichtweg nicht zu.
Für adaptive Methoden: Das Paper schließt eine „Single-Call“-Konstruktion für alle adaptiven Szenarien nicht aus. Stattdessen zeigt es, dass es für PRFs mit langen Outputs eine Grenze gibt: Die Anzahl der Aufrufe muss mit der Größe des Outputs skalieren. Man kann sich nicht mit einer winzigen, festen Anzahl von Aufrufen begnügen, wenn man einen massiven Tresor mit großem Output bauen will. Die Frage, ob eine Single-Call-adaptive Konstruktion für PRFs mit kurzen Outputs existiert, bleibt offen.

Die Einschränkung der „Abfragebeschränkung“

Die Autoren sind sehr sorgfältig mit ihren Annahmen. Sie konzentrieren sich auf eine Klasse von Reduktionen, die sie „abfragebeschränkt“ (query-bounded) nennen. In einfachen Worten bedeutet dies, dass die Interaktion des Erstellers mit dem Hacker begrenzt ist, sodass sie nicht davon abhängt, wie viele Fragen der Hacker stellt. Die Autoren argumentieren, dass fast jede Konstruktion in der Geschichte der Kryptographie dieser Beschreibung entspricht. Sie räumen ein: Sollte jemand eine seltsame, nicht-standardisierte Methode zur Konstruktion einer PRF erfinden, bei der der Ersteller Millionen von Fragen stellt, nur weil der Hacker eine einzige Frage gestellt hat, greift ihr Beweis möglicherweise nicht. Aber für alle praktischen, standardmäßigen kryptographischen Designs gelten die gefundenen unteren Schranken weiterhin.

Das Fazze

Dieses Paper schlägt nicht nur eine Grenze vor; es liefert einen mathematischen Beweis dafür, dass die „Abkürzung“ zum Bau von PRFs eine Sackgasse ist. Wenn man eine sichere Black-Box-PRF bauen will, kann man die Schritte nicht überspringen. Man muss den Preis zahlen, indem man den PRG so oft aufruft, dass die „Entropie“ (die Unvorhersehbarkeit und Unberechenbarkeit) hoch genug ist, um jeden Hacker zu täuschen. Die berühmte GGM-Konstruktion, die etwa $\omega(\log n)$ Aufrufe nutzt, erweist sich als nahezu optimal. Der Traum, eine Festung mit nur einem einzigen Ziegelstein zu bauen, ist in diesem Kontext mathematisch unmöglich.

Technisches Resümee: Untergrenzen für Black-Box-Konstruktionen von Pseudozufallsfunktionen

Problemstellung

Die Arbeit adressiert eine grundlegende offene Frage in der Kryptographie: Was ist die minimale Anzahl an Aufrufen eines Pseudozufallsgenerators (PRG), die erforderlich ist, um mittels einer vollumfänglichen Black-Box-Konstruktion eine Pseudozufallsfunktion (PRF) zu konstruieren?

Die wegweisende Arbeit von Goldreich, Goldwasser und Micali (GGM) etablierte, dass eine PRF unter Verwendung eines baumbasierten Ansatzes aus einem PRG konstruiert werden kann. In Kombination mit Levins Technik zur Domänenerweiterung erfordert diese Konstruktion $\omega(\log n)$ Aufrufe an den PRG, wobei $n$ die Eingabelänge des PRG ist. Während die jüngere Arbeit von Beimel, Malkin und Mazor bewies, dass GGM für eine spezifische Klasse von „Baumkonstruktionen“ optimal ist, bleibt der allgemeine Fall ungelöst. Insbesondere ist unbekannt, ob eine PRF mit weniger als $\omega(\log n)$ Aufrufen oder sogar mit einem einzigen Aufruf mittels allgemeiner Black-Box-Techniken gebaut werden kann.

Diese Arbeit untersucht diese Frage im Rahmen von vollständigen Black-Box-Konstruktionen, bei denen sowohl die Konstruktion als auch die Sicherheitsreduktion Black-Box-basiert sind. Die Autoren konzentrieren sich speziell auf eine Klasse von Reduktionen, die als abfragebeschränkte Reduktionen (query-bounded reductions) bezeichnet werden, bei denen die Anzahl der Interaktionen der Reduktion mit dem Adversären durch ein Polynom oberhalb begrenzt ist, das unabhängig von der Abfragekomplexität des Adversären ist (vorausgesetzt, der Adversär ist hinreichend erfolgreich).

Methodik

Die Autoren verwenden das Meta-Reduktions-Paradigma, um ihre Untergrenzen zu etablieren. Diese Technik beinhaltet die Konstruktion eines ineffizienten „echten“ Adversären, der einen „idealen“ Adversären (welcher die PRF bricht) simulieren kann, ohne direkten Zugriff auf den zugrunde liegenden PRG zu haben, wodurch der PRG mit weniger Abfragen als zulässig gebrochen wird.

Zentrale technische Komponenten:

Abfragebeschränkte Reduktionen: Die Autoren definieren eine Reduktion als abfragebeschränkt, wenn die Anzahl der Male, die sie den unterscheidenden Adversären abfragt, durch ein Polynom $d(n)$ beschränkt ist, unabhängig davon, wie viele Abfragen der Adversär an sein Orakel tätigt. Diese Klasse erfasst die meisten bekannten Reduktionen in der Literatur, einschließlich der GGM- und Goldreich-Levin-Konstruktionen.
Idealer vs. echter Adversär:
- Idealer Adversär ( $A_{ideal}$ ): Ein ineffizienter Adversär, der exponentiellen Zugriff auf das PRG-Orakel hat. Er versucht, die PRF zu brechen, indem er einen Schlüssel findet, der mit einem großen Anteil an Eingabe-Ausgabe-Paaren konsistent ist.
- Echter Adär ( $A_{real}$ ): Ein ineffizienter Adversär, der keinen Zugriff auf den PRG hat. Stattdessen erhält er die Abfrage-Antwort-Paare, die durch die Interaktion der Reduktion mit dem PRG generiert wurden. Er versucht, $A_{ideal}$ zu simulieren, indem er die Wahrscheinlichkeit schätzt, dass ein Schlüssel mit den beobachteten Ausgaben konsistent ist.
Score-Funktionen und Unabhängigkeit:
- Die zentrale Herausforderung besteht darin, dass die Ausgaben der PRF bei unterschiedlichen Eingaben abhängig sein können, wenn sie gemeinsame PRG-Seeds teilen.
- Die Autoren führen ein Verfahren ein, um „häufige Seeds“ (Seeds, die von vielen Eingaben verwendet werden) zu identifizieren und deren Ausgaben durch feste Werte zu ersetzen. Dies reduziert die Anzahl der aktiven PRG-Aufrufe.
- Für die verbleibenden Eingaben nutzen sie eine kombinatorische Behauptung (Claim 3/6), um zu zeigen, dass entweder eine große Menge an Eingaben disjunkte PRG-Seeds verwendet (was Unabhängigkeitsargumente via Hoeffding-Ungleichung ermöglicht) oder die Anzahl dieser Schlüssel vernachlässigbar ist.
- Um die statistische Distanz zwischen dem idealen und dem echten Adversären zu handhaben, verwenden die Autoren einen randomisierten Schwellenwert (gleichmäßig aus $[0.8, 1]$ gezogen) anstelle eines festen Schwellenwerts. Dies glättet die Entscheidungsgrenze und stellt sicher, dass die Verteilung der Ausgabe des echten Adversären statistisch nah an der des idealen Adversären liegt, sofern die Anzahl der Eingaben $m$ im Verhältnis zur Anzahl der Reduktionsabfragen $d$ ausreichend groß ist.
Entropie-Argumente für lange Ausgaben: Für das zweite Ergebnis (Theorem 2) verwenden die Autoren ein Entropie-basiertes Argument. Sie konstruieren einen spezifischen PRG, der Zufälligkeit nur auf einen kleinen Präfix des Seeds anwendet. Dies begrenzt die Entropie der PRF-Ausgabe signifikant unter die einer wahrhaft zufälligen Funktion, was es einem Distinguier ermöglicht, die Konstruktion zu brechen, falls die Anzahl der Aufrufe zu gering ist.

Zentrale Beiträge und Ergebnisse

1. Untergrenze für nicht-adaptive Aufrufe (Theorem 1)

Das Paper beweist, dass keine vollumfängliche Black-Box-Konstruktion einer PRF aus einem PRG unter Verwendung von nicht-adaptiven Aufrufen und abfragebeschränkten Reduktionen existiert, falls die Anzahl der Aufrufe $c$ folgende Bedingungen erfüllt:
$c = o\left(\frac{n}{\log n}\right) \quad \text{und} \quad c = o\left(\frac{in}{\log in}\right)$
wobei $n$ die Eingabelänge des PRG und $in$ die Eingabelänge der PRF ist.

Geltungsbereich: Dieses Ergebnis gilt selbst für schwache PRFs (bei denen der Adversär auf i.i.d. uniforme Abfragen beschränkt ist) und für PRFs mit Ein-Bit-Ausgabe.
Implikation: Dies schließt die Möglichkeit aus, eine PRF mit einer konstanten Anzahl nicht-adaptiver Aufrufe (z. B. einem einzigen Aufruf) für PRFs mit Eingabelängen $in = \omega(\log n)$ zu konstruieren, was einen spezifischen Fall des offenen Problems für abfragebeschränkte Reduktionen löst.

2. Untergrenze für lange Ausgaben (Theorem 2)

Das Paper etabliert eine Untergrenze für PRFs mit langen Ausgaben ($out$), die auch für adaptive Konstruktionen gilt und keine Voraussetzung für die Abfragebeschränktheit der Reduktion benötigt.

Ergebnis: Es existiert keine vollumfängliche Black-Box-Konstruktion einer PRF mit Ausgabelänge $out$ aus einem PRG mit Stretch $r$ , die weniger als $\frac{out}{\max(r, \omega(\log n))}$ Aufrufe verwendet.
Vergleich zu GGM: Die GGM-Konstruktion (mit Levins Trick) verwendet $\omega(\log n)$ Aufrufe an einen $n$ -Bit Stretch PRG, um eine $n$ -Bit Ausgabe zu erzeugen. Durch Komposition mit einem 1-Bit Stretch PRG (der $\Omega(n/\log n)$ Aufrufe benötigt) beträgt die Gesamtzahl der Aufrufe an einen 1-Bit Stretch PRG $\omega(n)$ . Theorem 2 impliziert eine Untergrenze von $\Omega(n / \omega(\log n))$ und zeigt damit, dass GGM bis auf einen Faktor von $\omega(\log n)$ optimal ist.

Bedeutung und Ansprüche

Das Paper beansprucht, signifikante Fortschritte bei der langjährigen Frage nach der Optimalität von PRF-Konstruktionen aus PRGs gemacht zu haben.

Optimalität von GGM: Während frühere Ergebnisse auf „Baumkonstruktionen“ beschränkt waren, liefert diese Arbeit Untergrenzen für allgemeine Black-Box-Konstruktionen unter spezifischen, aber natürlichen Annahmen (abfragebeschränkte Reduktionen).
Lösung des Einzelfall-Problems: Die Autoren stellen explizit fest, dass ihr Ergebnis die Frage klärt, ob eine PRF mit einem einzigen Aufruf zum PRG für die Klasse der abfragebeschränkten Reduktionen gebaut werden kann. Sie demonstrieren, dass eine solche Konstruktion für PRFs mit Eingabelängen $in = \omega(\log n)$ unmöglich ist.
Robustheit: Die Impossibility-Ergebnisse gelten selbst für schwache PRFs und, im Falle langer Ausgaben, auch für adaptive Konstruktionen.
Limitierungen: Die Autoren räumen bescheiden ein, dass ihr Hauptresultat (Theorem 1) auf der Annahme der „Abfragebeschränktheit“ beruht. Sie merken an, dass es eine offene Frage bleibt, ob diese Untergrenzen auf alle Black-Box-Reduktionen ausgedehnt werden können, da ihr Beweis darauf basiert, dass die Anzahl der Interaktionen der Reduktion unabhängig von der Abfragekomplexität des Adversären ist.

Zusammenfassend zeigt das Paper, dass die GGM-Konstruktion hinsichtlich der Anzahl der erforderlichen PRG-Aufrufe nahezu optimal ist, insbesondere für nicht-adaptive Konstruktionen und solche mit langen Ausgaben, indem es Meta-Reduktionstechniken und eine sorgfältige Entropieanalyse nutzt.