💻 computer science

Pseudorandom Functions in $\mathsf{NC}^1$ from LWE/LPN/CDH (Or: How to Build PRFs in $\mathsf{NC}^1$ , Generically)

Diese Arbeit führt eine generische Transformation ein, die schwache PRFs in starke PRFs mit minimalem Tiefen-Overhead konvertiert und somit die Konstruktion von $\mathsf{NC}^1$ -berechenbaren PRFs unter Standardannahmen einschließlich LWE, LPN und CDH ermöglicht, wodurch langjährige offene Probleme in der Low-Depth-Kryptographie löst.

Ursprüngliche Autoren: Youlong Ding, Aayush Jain, Ilan Komargodski

Veröffentlicht 2026-08-27

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Youlong Ding, Aayush Jain, Ilan Komargodski

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

In der digitalen Welt beruht Sicherheit oft auf einer speziellen Art mathematischer Werkzeuge, den sogenannten pseudozufälligen Funktionen. Stellen Sie sich eine Maschine vor, die einen geheimen Code und ein Stück Daten entgegennimmt und dann eine Zahlenfolge ausgibt, die für jeden Beobachter vollkommen zufällig aussieht. Wenn die Maschine korrekt arbeitet, kann niemand den Unterschied zwischen ihrer Ausgabe und einer wirklich zufälligen Sequenz feststellen, selbst wenn er die Maschine bereits viele Male hat arbeiten sehen. Diese Werkzeuge sind die unsichtbaren Schlösser und Schlüssel, die alles von Online-Banking bis hin zu privaten Nachrichten schützen. Seit Jahrzehnten versuchen Forscher, diese Maschinen so zu bauen, dass sie so schnell wie möglich laufen, insbesondere indem sie sie in sehr wenigen Schritten arbeiten lassen. In der Sprache der Informatik bedeutet dies, sie mit einem Schaltkreis zu bauen, der sehr flach ist, sodass die Berechnung fast augenblicklich auf modernen Prozessoren erfolgen kann. Je schneller und einfacher diese Werkzeuge sind, desto effizienter können sie in komplexen Systemen wie sicheren Wahlen oder dem Austausch privater Daten eingesetzt werden.

Lange Zeit gab es eine hartnäckige Lücke in unserer Fähigkeit, solche schnellen, flachen Maschinen zu bauen. Wir wussten, wie wir sie unter Verwendung sehr starker, komplexer mathematischer Annahmen erstellen konnten, aber diese erforderten tiefe, langsame Schaltkreise. Umgekehrt konnten wir flache Schaltkreise bauen, aber nur, wenn wir uns auf schwächere, weniger bewährte Annahmen oder sehr spezifische, starre mathematische Strukturen verlassen mussten. Es war, als hätte man einen Schlüssel, der eine Tür öffnet, aber zu schwer zum Tragen ist, oder einen Schlüssel, der leicht ist, aber nur in ein einziges, seltsames Schloss passt. Das Ziel war es, einen leichten Schlüssel zu finden, der jede Tür öffnen kann, und zwar unter Verwendung der am weitesten verbreiteten, zuverlässigsten Schlösser. Diese Herausforderung bestand seit fast dreißig Jahren und schränkte die Effizienz ein, mit der wir die digitale Welt absichern konnten.

Ein Team von Forschern hat diese Lücke nun mit einer neuen, allgemeinen Methode geschlossen, die ein schwächeres, leichter zu bauendes Werkzeug in ein starkes, sicheres umwandelt, ohne es zu verlangsamen. Ihre Arbeit, veröffentlicht in einem Paper mit dem Titel „Pseudorandom Functions in NC1 from LWE/LPN/CDH“, zeigt, dass es möglich ist, diese schnellen, flachen Maschinen unter Verwendung drei der grundlegendsten und am weitesten verbreiteten und vertrauenswürdigsten Annahmen der Kryptografie zu konstruieren. Die Forscher erreichten dies durch die Verfeinerung einer alten Idee namens GGM-Konstruktion, die eine komplexe Funktion aufbaut, indem sie durch einen Baum kleinerer Berechnungen wandert. Die traditionelle Art, dies zu tun, war wie das Wandern durch einen langen Flur, bei dem jeder Schritt die gleiche Menge an Anstrengung erforderte, was die gesamte Reise lang und langsam machte. Die neue Methode verändert die Form des Flurs. Während der Prozess tiefer in den Baum vordringt, schrumpft die Menge der erforderlichen Arbeit bei jedem Schritt geometrisch. Die ersten Schritte sind schwer, aber die nachfolgenden Schritte werden immer leichter und leichter – so schnell, dass die gesamte Anstrengung gering bleibt. Diese „Tapering“-Technik (Verjüngungstechnik) ermöglicht es den Forschern, den gesamten Prozess innerhalb der Grenzen eines flachen, schnellen Schaltkreises zu halten.

Um zu beweisen, dass diese neue Methode funktioniert, wandte das Team sie auf drei spezifische mathematische Probleme an, die als schwer zu lösen gelten. Das erste ist das Problem des „Learning With Errors“ (Lernen mit Fehlern), bei dem es darum geht, ein verborgenes Muster in einem verrauschten Datensatz zu finden. Frühere Versuche, schnelle Maschinen aus diesem Problem zu bauen, erforderten eine spezifischere, komplexere Version der Mathematik, die sehr große Zahlen verwendete. Die neue Arbeit zeigt, dass die Standardversion mit viel kleineren Zahlen ausreichend ist. Das zweite Problem ist „Learning Parity with Noise“ (Lernen der Parität mit Rauschen), das sich mit dem Finden eines verborgenen Musters in einem Strom von Bits befasst, bei denen Bits zufällig umgekehrt wurden. Die Forscher zeigten, dass ihre Methode mit der Standardversion dieses Problems funktioniert und die Notwendigkeit spezialisierter, strukturierter Versionen aufhebt. Das dritte Problem ist die „Computational Diffie-Hellman“-Annahme, ein Eckpfeiler der modernen Internet-Sicherheit, der zum Austausch geheimer Schlüssel verwendet wird. Jahrzehntelang basierte der einzige bekannte Weg, schnelle Maschinen aus dieser Annahme zu bauen, auf einer stärkeren, restriktiveren Version des Problems. Die neue Konstruktion beweist, dass die Standardversion ausreilt.

Die Bedeutung dieser Arbeit liegt in ihrer Allgemeingültigkeit und in der Tatsache, dass sie auf Standardannahmen basiert. Indem sie zeigen, dass ein schwaches, flaches Werkzeug zu einem starken, sicheren aufgewertet werden kann, ohne die Tiefe zu erhöhen, haben die Forscher die Fähigkeit freigeschaltet, schnelle, sichere Funktionen aus den grundlegendsten und am besten untersuchten mathematischen Problemen zu bauen. Dies löst mehrere langjährige Fragen auf dem Gebiet und liefert einen neuen, flexiblen Bauplan für zukünftige kryptografische Systeme. Die Forscher haben nicht nur angedeutet, dass dies möglich sein könnte; sie haben eine konkrete, schrittweise Konstruktion und einen strengen Beweis geliefert, dass sie funktioniert. Sie haben demonstriert, dass die Tiefe der resultierenden Maschine im Wesentlichen der Tiefe des Ausgangswerkzeugs entspricht, wodurch der Geschwindigkeitsvorteil beibehalten wird, während die notwendige Sicherheit gewonnen wird.

Diese Errungenschaft bedeutet, dass wir erstmals in der Lage sind, diese essenziellen Sicherheitswerkzeuge unter Verwendung der gängigsten und vertrauenswürdigsten mathematischen Grundlagen zu bauen, ohne dabei die Geschwindigkeit zu opfern. Es macht die Notwendigkeit spezialisierter, komplexer Varianten dieser Probleme, die zuvor als notwendig für die Effizienz erachtet wurden, überflüssig. Das Ergebnis ist ein robusteres und vielseitigeres Fundament für die digitale Sicherheit der Zukunft, das es ermöglicht, schnellere und effizientere Verschlüsselungsmethoden über ein breites Spektrum von Technologien hinweg einzusetzen. Die Arbeit steht als definitiver Beweis dafür, dass die Barriere zwischen schwachen, schnellen Werkzeugen und starken, schnellen Werkzeugen durchbrochen wurde und den Weg in eine neue Ära des effizienten kryptografischen Designs ebnet.

Technisches Resümee: Pseudozufällige Funktionen in NC1 aus LWE/LPN/CDH

1. Problemstellung

Die Konstruktion von pseudozufälligen Funktionen (PRFs) mit geringer paralleler Komplexität (speziell innerhalb der Klasse NC1, berechenbar durch Schaltkreise mit polynomieller Größe und logarithmischer Tiefe) ist ein langjähriges offenes Problem in der Kryptographie. Obwohl PRFs generisch aus Pseudozufälligen Generatoren (PRGs) via der Goldreich-Goldwasser-Micali (GGM)-Transformation konstruiert werden können, ist diese Methode inhärent sequentiell. Selbst wenn der zugrunde liegende PRG in logarithmischer Tiefe berechenbar ist, erfordert die resultierende PRF eine Tiefe von $\omega(\log n)$ , was sie außerhalb von NC1 platziert.

Vor dieser Arbeit waren bekannte in NC1 berechenbare PRFs selten und stützten sich auf hochspezifische algebraische Strukturen oder starke Annahmen:

Naor-Reingold (1, 2004): Konstruierten PRFs in $TC_0 \subseteq NC1$ aus Decisional Diffie-Hellman (DDH) und Faktorisierung.
Banerjee-Peikert-Rosen (2012): Konstruierten PRFs in $TC_0$ aus Ring-LWE, erforderten jedoch ein superpolynomiales Modulus-zu-Rauschen-Verhältnis.
Ding-Jain-Komargodski (2025): Konstruierten PRFs aus strukturierten Varianten von Learning Parity with Noise (LPN), wie z. B. SeededLPN oder Ring-LPN.

Die zentrale Herausforderung besteht darin, NC1-berechenbare PRFs aus Standard-Annahmen (LWE mit polynomiellem Modulus-zu-Rauschen-Verhältnis, Standard-LPN und Computational Diffie-Hellman) zu konstruieren, ohne sich auf strukturierte Varianten oder superpolynomielle Parameter zu verlassen.

2. Methodik

Die Arbeit führt einen zweigleisigen Ansatz ein: eine generische tiefenerhaltende Transformation von schwachen PRFs (WPRFs) zu starken PRFs sowie neue tiefeneffiziente Konstruktionen von WPRFs (oder Synthesizern) aus Standard-Annahmen.

2.1 Tapering-GGM: Eine generische Transformation

Die Autoren schlagen eine neuartige Anpassung der GGM-Baumkonstruktion vor, bezeichnet als Tapering-GGM, welche eine WPRF zu einer starken PRF aufwertet, während die Tiefe des Auswertungs-Schaltkreises erhalten bleibt.

Der Tapering-Mechanismus: In einem Standard-GGM-Baum bleibt die Zustandsgröße konstant, und die Tiefe akkumuliert sich linear mit der Anzahl der Baumebenen ( $\ell \cdot d_{WPRF}$ ). In Tapering-GGM schrumpft die Zustandsgröße in jeder Ebene geometrisch. Wenn der Sicherheitsparameter auf Ebene $i$ gleich $\lambda^{(i)}$ ist, definieren die Autoren $\lambda^{(i)} = \lambda^{2^{-i+1}}$ . Folglich nimmt die Tiefe des WPRF-Aufrufs auf Ebene $i$ , bezeichnet als $d(\lambda^{(i)})$ , geometrisch ab.
Tiefenanalyse: Wenn die Basis-WPRF die Tiefe $d(\lambda) = \Theta(\log \lambda)$ besitzt, wird die Gesamttiefe der Tapering-GGM-Konstruktion zu:
$d_{total} = O(\log \lambda) + \sum_{i=1}^{\ell} d(\lambda^{(i)}) \approx O(\log \lambda) + \sum_{i=1}^{\ell} \log(\lambda^{2^{-i+1}}) = O(\log \lambda)$
Dieser geometrische Zerfall stellt sicher, dass die Gesamttiefe $O(d(\lambda))$ bleibt, wodurch die Konstruktion in NC1 verbleibt, sofern die zugrunde liegende WPRF in NC1 liegt.
Sicherheitsherausforderungen & Lösungen:
- Herausforderung: Je tiefer der Baum wird, desto kleiner wird der Sicherheitsparameter $\lambda^{(i)}$ (sub-polynomiell), was die rechnerische Sicherheit der zugrunde liegenden WPRF potenziell untergräbt.
- Lösung 1 (Hashing): Die Eingabe wird zuerst mittels einer paarweise unabhängigen Hash-Funktion gehasht. Dies stellt sicher, dass die Abfragen eines Angreifers mit hoher Wahrscheinlichkeit "zerstreut" (auf distinkte Pfade abgebildet) werden innerhalb der oberen $O(\log_\Delta q)$ Ebenen, in denen der Sicherheitsparameter noch polynomiell ist.
- Lösung 2 (Key-Uniformität): Für Ebenen unterhalb des Zerstreuungspunktes beruht die Konstruktion auf informationstheoretischer Sicherheit. Die Autoren fordern, dass die WPRF schlüssel-uniform (1-weise unabhängig) ist. Wenn der Zustand auf der Zerstreuungsebene pseudozufällig ist, bildet die anschließende Komposition von schlüssel-uniformen Transformationen diesen Zustand auf einen perfekt uniformen Output ab, unabhängig von der rechnerischen Härte der tiefer liegenden WPRF-Aufrufe.

2.2 Tiefeneffiziente WPRF-Konstruktionen

Die Autoren instanziieren das Tapering-GGM-Framework mit neuen WPRF-Konstruktionen aus Standard-Annahmen:

Aus LWE (Learning With Errors):
- Die Autoren konstruieren die erste NC1 WPRF aus Standard-LWE mit einem polynomiellen Modulus-zu-Rauschen-Verhältnis ( $\alpha = n^{-\epsilon}$ ).
- Zentrales technisches Werkzeug: Ein Rounded Gaussian Sampler, der in $O(\text{poly}(\log \log \lambda))$ Tiefe berechenbar ist. Sie approximieren die Box-Muller-Transformation mittels Low-Depth-Polynom-Approximationen für $\ln$ , $\cos$ und Newton-Iteration für Quadratwurzeln.
- Konstruktion: Sie verwenden ein Chaining-Paradigma (inspiriert durch Kim [Kim20]). Die Konstruktion berechnet maskierte LWE-Skalarprodukte Schicht für Schicht. Die höchstwertigen Bits des Outputs einer Schicht sampeln deterministisch die Fehlerverteilung für die nächste Schicht. Die Begrenztheit des Error-Samplers gewährleistet die Stabilität, sodass der Sicherheitsbeweis mittels Hybriden durchgeführt werden kann.
Aus LPN (Learning Parity with Noise):
- Die Autoren nutzen ein aktuelles Ergebnis von Ding, Jain und Komargodski [DJK25], welches WPRFs in NC1 aus Standard-LPN (beliebige invers-polynomielle Rauschwahrscheinlichkeit) bereitstellt.
- Durch die Kombination mit Tapering-GGM erhalten sie die ersten NC1 PRFs aus Standard-LPN, wodurch die Notwendigkeit für strukturierte Varianten (z. B. Ring-LPN) entfällt, die in früheren Arbeiten erforderlich waren.
Aus CDH (Computational Diffie-Hellman):
- Die Autoren beobachten, dass Tapering-GGM tatsächlich ein schwächeres Primitiv als eine WPRF benötigt: einen Synthesizer (bei dem der Eingabepool vor dem Angreifer verborgen ist).
- Sie instanziieren die Transformation unter Verwendung der Naor-Reingold Synthesizer-Konstruktion [NR95, NR99], die unter der CDH-Annahme in NC1 berechenbar ist. Dies liefert die ersten NC1 PRFs aus CDH und verbessert damit die bisherigen DDH-basierten Konstruktionen.

3. Zentrale Beiträge

Generische tiefenerhaltende Transformation: Eine Black-Box-Transformation, die jede in Tiefe $d(\lambda) = \Omega(\log \lambda)$ berechenbare WPRF (oder Synthesizer) in eine starke PRF mit Tiefe $O(d(\lambda))$ umwandelt. Dies löst die generische Barriere, die NC1-PRFs aus Standard-Annahmen verhinderte.
NC1 PRFs aus Standard-LWE: Die erste Konstruktion von PRFs in NC1 aus LWE mit einem polynomiellen Modulus-zu-Rauschen-Verhältnis, womit ein explizit in den Vorlesungsnotizen von Vaikuntanathan genanntes offenes Problem gelöst wird. Dies stützt sich auf die Härte von GapSVP mit polynomiellen Approximationsfaktoren.
NC1 PRFs aus Standard-LPN: Die erste Konstruktion von PRFs in NC1 aus der Standard-LPN-Annahme, wodurch die Notwendigkeit für strukturierte Varianten wie Ring-LPN oder Sparse-LPN entfällt.
NC1 PRFs aus CDH: Die erste Konstruktion von PRFs in NC1 aus der Computational Diffie-Hellman-Annahme, was die 30 Jahre alte Naor-Reingold-Ergebnis verbessert, welches auf der stärkeren Decisional Diffie-Hellman (DDH) beruhte.
Low-Depth Gaussian Sampler: Ein neuartiger deterministischer Schaltkreis zum Sampling von gerundeten Gaußschen Fehlern in $O(\text{poly}(\log \log \lambda))$ Tiefe, welcher eine kritische Komponente für die LWE-basierte WPRF darstellt.

4. Ergebnisse

Die Arbeit etabliert die folgenden konkreten Ergebnisse:

Theorem: Wenn es WPRFs in NC1 gibt, dann existieren auch PRFs in NC1.
Korollar (LWE): Angenommen, die LWE-Annahme gilt für ein Rausch-zu-Modulus-Verhältnis $\alpha = n^{-\epsilon}$ , dann existieren PRFs in NC1.
Korollar (LPN): Angenommen, die LPN-Annahme gilt für eine Rauschwahrscheinlichkeit $\mu = n^{-\epsilon}$ , dann existieren PRFs in NC1.
Korollar (CDH): Angenommen, die CDH-Annahme gilt, dann existieren PRFs in NC1.
Korollar (GapSVP): Angenommen, GapSVP ist schwer zu approximieren innerhalb eines $\tilde{O}(n^{1+\epsilon})$ Faktors, dann existieren PRFs in NC1.

5. Bedeutung

Die Arbeit beansprucht, mehrere langjährige offene Probleme in der Komplexität kryptographischer Primitive zu lösen. Durch die Entkopplung der Tiefe der PRF-Auswertung von der sequentiellen Natur der GGM-Transformation zeigen die Autoren, dass starke PRFs aus einer Vielzahl von Standard-Annahmen konstruiert werden können, ohne die parallele Effizienz zu opfern.

Speziell:

Entfernt die Abhängigkeit von Ring-LWE und superpolynomiellen Parametern für NC1-PRFs und wechselt zu Standard-LWE mit polynomiellen Parametern.
Entfernt die Abhängigkeit von strukturierten LPN-Varianten und wechselt zu Standard-LPN.
Schwächt die Härteannahme für CDH-basierte PRFs von DDH auf CDH ab.
Bietet einen generischen Rahmen (Tapering-GGM), der jede existierende Log-Depth WPRF-Kandidatur (z. B. aus [ABG+14], [AR16]) in eine Log-Depth PRF aufwerten kann, sofern die zugrunde liegende Annahme hält.

Die Autoren positionieren diese Arbeit als einen fundamentalen Schritt zum Verständnis der parallelen Komplexität der Kryptographie, mit Implikationen für Protokolle der sicheren Berechnung, Lerntheorie (via der PRF-versus-Learning-Verbindung) und Meta-Komplexität.