💻 computer science

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

Dit artikel introduceert een generieke transformatie die zwakke PRF's omzet in sterke PRF's met minimale diepte-overhead, waardoor de constructie van $\mathsf{NC}^1$ -berekenbare PRF's mogelijk wordt op basis van standaardveronderstellingen waaronder LWE, LPN en CDH, waarmee langlopende openstaande problemen in de lage-diepte cryptografie worden opgelost.

Oorspronkelijke auteurs: Youlong Ding, Aayush Jain, Ilan Komargodski

Gepubliceerd 2026-08-27

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Youlong Ding, Aayush Jain, Ilan Komargodski

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

In de digitale wereld rust beveiliging vaak op een speciaal soort wiskundig hulpmiddel dat een pseudowillekeurige functie wordt genoemd. Stel je een machine voor die een geheime code en een stukje data neemt, en vervolgens een reeks getallen uitspuugt die volkomen willekeurig lijkt voor iedereen die toekijkt. Als de machine correct werkt, kan niemand het verschil zien tussen de output van de machine en een werkelijk willekeurige sequentie, zelfs niet als ze de machine vele malen hebben zien werken. Deze tools zijn de onzichtbare sloten en sleutels die alles beschermen, van online bankieren tot privéberichten. Decennialang hebben onderzoekers geprobeerd deze machines zo te bouwen dat ze zo snel mogelijk werken, specif으로 door ze in zeer weinig stappen te laten werken. In de taal van de informatica betekent dit dat ze worden gebouwd met een circuit dat zeer ondiep is, waardoor de berekening bijna direct op moderne processors kan plaatsvinden. Hoe sneller en eenvoudiger deze tools zijn, hoe efficiënter ze kunnen worden gebruikt in complexe systemen zoals veilig stemmen of het delen van private gegevens.

Een lange tijd was er een hardnekkige kloof in ons vermogen om deze snelle, ondiepe machines te bouwen. We wisten hoe we ze konden maken met zeer sterke, complexe wiskundige aannames, maar die vereisten diepe, trage circuits. Omgekeerd konden we wel ondiepe circuits bouwen, maar dan moesten we vertrouwen op zwakkere, minder bewezen aannames of zeer specifieke, rigide wiskundige structuren. Het was alsoals het hebben van een sleutel die een deur kon openen maar te zwaar was om te dragen, of een sleutel die licht was maar slechts op één vreemd slot paste. Het doel was om een manier te vinden om een lichtgewicht sleutel te maken die elke deur kon openen, gebruikmakend van alleen de meest standaard, betrouwbare sloten die beschikbaar zijn. Deze uitdaging heeft bijna dertig jaar bestaan en beperkte hoe efficiënt we de digitale wereld konden beveiligen.

Een team van onderzoekers heeft deze kloof nu overbrugd met een nieuwe, algemene methode die een zwakker, gemakkelijker te bouwen hulpmiddel transformeert in een sterk, veilig hulpmiddel zonder het te vertragen. Hun werk, gepubliceerd in een artikel met de titel "Pseudorandom Functions in NC1 from LWE/LPN/CDH", demonstreert dat het mogelijk is om deze snelle, ondiepe machines te construeren met behulp van drie van de meest fundamentele en breed vertrouwde aannames in de cryptografie. De onderzoekers bereikten dit door een oude idee genaamd de GGM-constructie te verfijnen, die een complexe functie bouwt door door een boom van kleinere berekeningen te wandelen. De traditionele manier van dit proces was als het lopen door een lange gang waar elke stap evenveel inspanning vereiste, waardoor de totale reis lang en traag werd. De nieuwe methode verandert de vorm van de gang. Naarmate het proces dieper in de boom gaat, krimpt de hoeveelheid werk die bij elke stap vereist is geometrisch. De eerste paar stappen zijn zwaar, maar de daaropvolgende stappen worden steeds lichter en lichter, zodat de totale inspanning klein blijft. Deze "tapering"-techniek (het taps toelopen) stelt de onderzoekers in staat om het gehele proces binnen de grenzen van een ondiep, snel circuit te houden.

Om te bewijzen dat deze nieuwe methode werkt, heeft het team deze toegepast op drie specifieke wiskundige problemen die bekend staan als moeilijk op te lossen. Het eerste is het Learning With Errors-probleem, dat gaat over het vinden van een verborgen patroon in een ruizige dataset. Eerdere pogingen om snelle machines vanuit dit probleem te bouwen, vereisten een specifieke, complexere versie van de wiskunde die zeer grote getallen gebruikte. Het nieuwe werk laat zien dat de standaardversie, met veel kleinere getallen, voldoende is. Het tweede probleem is Learning Parity with Noise, dat te maken heeft met het vinden van een verborgen patroon in een stroom bits waarvan de bits willekeurig zijn omgedraaid. De onderzoekers toonden aan dat hun methode werkt met de standaardversie van dit probleem, waardoor de noodzaak voor de gespecialiseerde, gestructureerde versies die voorheen vereist waren, vervalt. Het derde probleem is de Computational Diffie-Hellman aanname, een hoeksteen van de moderne internetbeveiliging die wordt gebruikt voor het uitwisselen van geheime sleutels. Decennialang vertrouwde de enige bekende manier om snelle machines vanuit deze aanname te bouwen op een sterkere, meer restrictieve versie van het probleem. De nieuwe constructie bewijst dat de standaardversie genoeg is.

De betekenis van dit werk ligt in de algemeenheid en het vertrouwen op standaard aannames. Door aan te tonen dat een zwak, ondiep hulpmiddel kan worden opgegradeerd naar een sterk, veilig hulpmiddel zonder de diepte toe te voegen, hebben de onderzoekers de mogelijkheid ontsloten om snelle, veilige functies te bouwen vanuit de meest basale en goed bestudeerde wiskundige problemen. Dit lost verschillende langlopende vragen in het vakgebied op en biedt een nieuw, flexibel blauwdruk voor toekomstige cryptografische systemen. De onderzoekers suggereerden niet alleen dat dit mogelijk zou kunnen zijn; ze leverden een concrete, stapsgewijze constructie en een rigoureus bewijs dat het werkt. Ze toonden aan dat de diepte van de resulterende machine essentieel hetzelfde is als de diepte van het startinstrument, waardoor het snelheidsvoordeel behouden blijft terwijl de noodzakelijke beveiliging wordt verkregen.

Deze prestatie betekent dat we voor het eerst deze essentiële beveiligingsinstrumenten kunnen bouwen met de meest gebruikelijke en vertrouwde wiskundige fundamenten, zonder snelheid op te offeren. Het heft de noodzaak weg voor gespecialiseerde, complexe varianten van deze problemen die voorheen als noodzakelijk werden beschouwd voor efficiëntie. Het resultaat is een robuustere en veelzijdiger fundament voor de digitale beveiliging van de toekomst, wat zorgt voor snellere en efficiëntere encryptiemethoden die kunnen worden ingezet binnen een breed scala aan technologieën. Het werk dient als een definitief bewijs dat de barrière tussen zwakke, snelle tools en sterke, snelle tools is doorbroken, wat de deur opent naar een nieuw tijdperk van efficiënt cryptografisch ontwerp.

Technische Samenvatting: Pseudorandom Functions in NC1 vanuit LWE/LPN/CDH

1. Probleemstelling

De constructie van Pseudorandom Functions (PRF's) met een lage parallelle complexiteit (specifiek binnen de klasse NC1, berekenbaar door circuits met een polynomiale grootte en logaritmische diepte) is een langdurig openstaand probleem in de cryptografie. Hoewel PRF's generiek geconstrueerd kunnen worden uit Pseudorandom Generators (PRG's) via de Goldreich-Goldwasser-Micali (GGM) transformatie, is deze methode inherent sequentieel. Zelfs als de onderliggende PRG berekenbaar is in logaritmische diepte, vereist de resulterende PRF een diepte van $\omega(\log n)$ , wat buiten NC1 valt.

Vóór dit werk waren bekende NC1-berekenbare PRF's schaars en vertrouwden ze op zeer specifieke algebraïsche structuren of sterke aannames:

Naor-Reingold (1997, 2004): Construeerden PRF's in $TC_0 \subseteq NC1$ vanuit Decisional Diffie-Hellman (DDH) en factorisatie.
Banerjee-Peikert-Rosen (2012): Construeerden PRF's in $TC_0$ vanuit Ring-LWE, maar vereisten een super-polynomiale modulus-naar-ruisverhouding.
Ding-Jain-Komargodski (2025): Construeerden PRF's vanuit gestructureerde varianten van Learning Parity with Noise (LPN), zoals SeededLPN of Ring-LPN.

De centrale uitdaging is om NC1-berekenbare PRF's te bereiken vanuit standaard aannames (LWE met een polynomiale modulus-naar-ruisverhouding, standaard LPN, en Computational Diffie-Hellman) zonder te vertrouwen op gestructureerde varianten of super-polynomiale parameters.

2. Methodologie

Het artikel introduceert een tweeledige aanpak: een generieke diepte-behoudende transformatie van Weak PRF's (WPRF's) naar sterke PRF's, en nieuwe diepte-efficiënte constructies van WPRF's (of synthesizers) vanuit standaard aannames.

2.1 Tapering-GGM: Een Generieke Transformatie

De auteurs stellen een nieuwe aanpassing voor van de GGM-boomconstructie, genaamd Tapering-GGM, die een WPRF upgrade naar een sterke PRF terwijl de evaluatie-diepte van het circuit behouden blijft.

Het Tapering-mechanisme: In een standaard GGM-boom blijft de grootte van de toestand constant, en de diepte accumuleert lineair met het aantal boomlagen ( $\ell \cdot d_{WPRF}$ ). In Tapering-GGM krimpt de grootte van de toestand geometrisch bij elke laag. Als de beveiligingsparameter op niveau $i$ gelijk is aan $\lambda^{(i)}$ , definiëren de auteurs $\lambda^{(i)} = \lambda^{2^{-i+1}}$ . Bijgevolg neemt de diepte van de WPRF-aanroep op niveau $i$ , aangeduid als $d(\lambda^{(i)})$ , geometrisch af.
Diepte-analyse: Als de basis-WPRF een diepte heeft van $d(\lambda) = \Theta(\log \lambda)$ , dan wordt de totale diepte van de Tapering-GGM constructie:
$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)$
Dit geometrische verval zorgt ervoor dat de totale diepte $O(d(\lambda))$ blijft, waardoor de constructie binnen NC1 blijft als de onderliggende WPRF in NC1 zit.
Beveiligingsuitdagingen & Oplossingen:
- Uitdaging: Naarmate de boom dieper gaat, wordt de beveiligingsparameter $\lambda^{(i)}$ klein (sub-polynomial), wat de computationele veiligheid van de onderliggende WPRF kan breken.
- Oplossing 1 (Hashing): De input wordt eerst gehasht via een pairwise-onafhankelijke hashfunctie. Dit zorgt ervoor dat, met hoge waarschijnlijkheid, de queries van de tegenstander "versnipperd" worden (gemapt naar onderscheidende paden) binnen de bovenste $O(\log_\Delta q)$ lagen, waar de beveiligingsparameter nog steeds polynomiaal is.
- Oplossing 2 (Key-Uniformity): Voor lagen onder het versnipperingspunt vertrouwt de constructie op informatie-theoretische veiligheid. De auteurs vereisen dat de WPRF key-uniform (1-wise independent) is. Als de toestand op het versnipperingsniveau pseudorandom is, brengt de daaropvolgende compositie van key-uniforme transformaties deze toestand naar een perfect uniforme output, ongeacht de computationele hardheid van de WPRF op lagere niveaus.

2.2 Diepte-efficiënte WPRF Constructies

De auteurs instantiëren het Tapering-GGM framework met nieuwe WPRF-constructies vanuit standaard aannames:

Vanuit LWE (Learning With Errors):
- De auteurs construeren de eerste NC1 WPRF vanuit standaard LWE met een polynomiale modulus-naar-ruisverhouding ( $\alpha = n^{-\epsilon}$ ).
- Cruciaal technisch instrument: Een Rounded Gaussian Sampler die berekenbaar is in $O(\text{poly}(\log \log \lambda))$ diepte. Ze benaderen de Box-Muller transformatie met low-depth polynomiale benaderingen voor $\ln$ , $\cos$ , en Newton-iteratie voor vierkantswortels.
- Constructie: Ze maken gebruik van een chaining-paradigma (geïnspireerd door Kim [Kim20]). De constructie berekent gemaskeerde LWE inner products laag voor laag. De hoogste bits van de output van één laag bepalen deterministisch de foutdistributie voor de volgende laag. De begrensdheid van de error sampler zorgt voor stabiliteit, waardoor het beveiligingsbewijs via hybriden kan verlopen.
Vanuit LPN (Learning Parity with Noise):
- De auteurs maken gebruik van een recent resultaat door Ding, Jain, en Komargodski [DJK25] dat WPRF's in NC1 biedt vanuit standaard LPN (arbitraire inverse polynomiale ruis).
- Door dit te combineren met Tapering-GGM, verkrijgen zij de eerste NC1 PRF's vanuit standaard LPN, waardoor de noodzaak voor gestructureerde varianten (zoals Ring-LPN) verdwijnt.
Vanuit CDH (Computational Diffie-Hellman):
- De auteurs observeren dat Tapering-GGM eigenlijk een primitief vereist dat zwakker is dan een WPRF: een Synthesizer (waarbij de input-pool verborgen is voor de tegenstander).
- Ze instantiëren de transformatie met de Naor-Reingold synthesizer constructie [NR95, NR99], die berekenbaar is in NC1 onder de CDH-aanname. Dit levert de eerste NC1 PRF's op vanuit CDH, wat een verbetering is ten opzichte van de eerdere DDH-gebaseerde constructies.

3. Belangrijkste Bijdragen

Generieke Diepte-behoudende Transformatie: Een black-box transformatie die elke WPRF (of synthesizer) berekenbaar in diepte $d(\lambda) = \Omega(\log \lambda)$ omzet in een sterke PRF berekenbaar in diepte $O(d(\lambda))$ . Dit lost de generieke barrière op die NC1 PRF's uit standaard aannames verhinderde.
NC1 PRF's vanuit Standaard LWE: De eerste constructie van PRF's in NC1 vanuit LWE met een polynomiale modulus-naar-ruisverhouding, wat een openstaand probleem oplost dat expliciet in de aantekeningen van Vaikuntanathan werd vermeld. Dit steunt op de hardheid van GapSVP met polynomiale benaderingsfactoren.
NC1 PRF's vanuit Standaard LPN: De eerste constructie van PRF's in NC1 vanuit de standaard LPN-aanname, waarbij de noodzaak voor gestructureerde varianten zoals Ring-LPN of Sparse LPN wordt geëlimineerd.
NC1 PRF's vanuit CDH: De eerste constructie van PRF's in NC1 vanuit de Computational Diffie-Hellman aanname, wat de 30 jaar oude Naor-Reingold resultaten die vertrouwden op de sterkere Decisional Diffie-Hellman (DDH) verbetert.
Low-Depth Gaussian Sampler: Een nieuwe deterministische circuit voor het samplen van afgeronde Gaussian errors in $O(\text{poly}(\log \log \lambda))$ diepte, wat een cruciaal onderdeel is voor de LWE-gebaseerde WPRF.

4. Resultaten

Het artikel stelt de volgende concrete resultaten vast:

Stelling: Als er WPRF's in NC1 bestaan, dan bestaan er PRF's in NC1.
Corollary (LWE): Uitgaande van de LWE-aanname voor een noise-to-modulus ratio $\alpha = n^{-\epsilon}$ , bestaan er PRF's in NC1.
Corollary (LPN): Uitgaande van de LPN-aanname voor een noise kans $\mu = n^{-\epsilon}$ , bestaan er PRF's in NC1.
Corollary (CDH): Uitgaande van de CDH-aanname, bestaan er PRF's in NC1.
Corollary (GapSVP): Uitgaande van de aanname dat GapSVP moeilijk te benaderen is binnen een $\tilde{O}(n^{1+\epsilon})$ factor, bestaan er PRF's in NC1.

5. Betekenis

Het artikel claimt verschillende langdurige openstaande problemen in de complexiteit van cryptografische primitieven op te lossen. Door de diepte van de PRF-evaluatie los te koppelen van het sequentiële karakter van de GGM-transformatie, laten de auteurs zien dat sterke PRF's kunnen worden geconstrueerd vanuit een breed scala aan standaard aannames zonder in te boeten op parallelle efficiëntie.

Specifiek:

Verwijdert de afhankelijkheid van Ring-LWE en super-polynomiale parameters voor NC1 PRF's, en beweegt naar standaard LWE met polynomiale parameters.
Verwijdert de afhankelijkheid van gestructureerde LPN varianten, en beweegt naar standaard LPN.
Verzwakt de hardheidsaanname voor CDH-gebaseerde PRF's van DDH naar CDH.
Biedt een generiek framework (Tapering-GGM) dat elke bestaande log-diepte WPRF kandidaat (bijv. [ABG+14], [AR16]) kan upgraden naar een log-diepte PRF, mits de onderliggende aanname standhoudt.

De auteurs positioneren dit werk als een fundamentele stap in het begrijpen van de parallelle complexiteit van cryptografie, met implicaties voor veilige computatieprotocollen, leertheorie (via de PRF-versus-learning connecties) en meta-complexiteit.