💻 computer science

Lower Bounds on Black-Box Constructions of Pseudorandom Functions

Dit artikel stelt vast dat geen enkele volledig black-box constructie van een pseudorandom functie (PRF) uit een pseudorandom generator (PRG) $o(n/\log n)$ niet-adaptieve aanroepen naar de PRG kan bereiken, zelfs niet voor zwakke PRF's met één-bit outputs, en biedt daarmee sterke ondergrenzen voor de efficiëntie van dergelijke constructies en laat de mogelijkheid van een constructie met een enkele aanroep als een belangrijke openstaande uitdaging.

Oorspronkelijke auteurs: Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam

Gepubliceerd 2026-08-17

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam

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

De Dilemma van de Digitale Slotenmaker

Stel je voor dat je een meesterslotenmaker bent die probeert een onbreekbare kluizdeur te bouwen. In de wereld van digitale beveiliging is deze "kluis" een Pseudorandom Function (PRF). Denk aan een PRF als een magisch apparaat: je voert het een geheime sleutel en een specifieke input (zoals een kamernummer), en het spuwt een reeks getallen uit die er voor iedereen die toekijkt volkomen willekeurig uitziet. Echter, als je dezelfde geheime sleutel opnieuw gebruikt, produceert het altijd exact dezelfde "willekeurige" reeks. Deze consistentie is wat het nuttig maakt voor het beveiligen van je e-mails, het beveiligen van je banktransacties en het beschermen van je wachtwoorden.

Om dit magische apparaat te bouwen, beginnen cryptografen vaak met iets eenvoudiger, namelijk een Pseudorandom Generator (PRG). Een PRG is als een kleine, efficiënte zaadje dat uitgroeit tot een enorm, willekeurig ogend bos. Het neemt een korte, geheime string en rekt deze uit tot een veel langere string die er willekeurig uitziet voor elk computerprogramma. De grote vraag in de cryptografie is geweest: Hoeveel keer moeten we deze "zaadje-rekkende" machine gebruiken om onze "kluisdeur" te bouwen?

Decennialang was het standaard recept (bekend als de GGM-constructie) om de zaadje-rekkende machine herhaaldelijk te gebruiken, in een boomachtige structuur, ongeveer $\omega(\log n)$ keer (waarbij $n$ de grootte van het zaadje is). Het werkt geweldig, maar het voelt een beetje omslachtig. Is er een kortere weg? Zouden we een perfecte kluizdeur kunnen bouwen door de zaadje-rekkende machine slechts één keer te gebruiken? Of misschien slechts een handvol keren? Dit paper duikt diep in die vraag, als een detective die probeert te bewijzen dat je, hoe slim je ook bent, simpelweg niet in staat bent om een veilige kluizdeur te bouren met te weinig rek-beurten van het zaadje.

De Grote Ontdekking van het Paper: Het "Te Weinig" Probleem

Dit paper, geschreven door Bar Alon, Itai Dinur en Muthuramakrishnan Venkitasubramaniam, pakt de fundamentele vraag aan: Wat is het absolute minimum aantal keren dat we een Pseudorandom Generator (PRG) moeten aanroepen om een Pseudorandom Function (PRF) te bouwen?

De auteurs bewijzen dat voor een specifiek en zeer redelijk type constructie, het antwoord "veel meer dan je zou hopen" is. Specifiek laten ze zien dat je geen veilige PRF kunt bouwen met een "volledig black-box" methode als je de PRG slechts een klein aantal keren aanroept—namelijk minder dan ongeveer $n / \log n$ keer (waarbij $n$ de lengte van de input van de PRG is).

Om hun bewijs te begrijpen, stel je een spel voor van "Spot de Nep":

De Opzet: Een "Reductie" (de bouwer) probeert een PRF te creëren met behulp van een PRG. Ze hebben ook een "Adversary" (de hacker) die probeert te bepalen of de PRF echt is of gewoon een willekeurige functie.
De Truc: De auteurs stellen zich een scenario voor waarin de bouwer "query-bounded" is. Dit betekent dat de bouwer de hacker om hulp kan vragen, maar dat het aantal keren dat ze kunnen vragen beperkt is en niet explodeert op basis van het aantal vragen dat de hacker stelt.
De Tegenaanval: De auteurs construeren een "Real Adversary" en een "Ideal Adversary".
- De Ideal Adversary is een superkrachtige, trage computer die elke mogelijke geheime sleutel kan controleren om te zien of deze bij de data past. Het kan gemakkelijk onderscheid maken tussen een functie die een PRF is of een willekeurige functie.
- De Real Adversary is degene die de bouwer daadwerkelijk gebruikt. Deze heeft geen superkrachten; het ziet alleen de beperkte vragen die de bouwer aan de PRG heeft gesteld.
De Onthulling: De auteurs bewijzen dat als de bouwer de PRG te weinig aanroept, de "Real Adversary" de "Ideal Adversary" perfect kan imiteren zonder de beveiliging van de PRG zelf te breken. Dit creëert een paradox: als de bouwer een veilige PRF zou kunnen bouwen met zo weinig aanroepen van de PRG, dan zou hij ook de PRG zelf kunnen breken met een methode die te traag is om praktisch te zijn, wat in strijd is met de aanname dat de PRG veilig is.

Het Hoofdresultaat:
Het paper bewijst dat voor niet-adaptieve constructies (waarbij de bouwer alle PRG-vragen beslist voordat hij enige antwoorden ziet), het onmogelijk is om een PRF te bouwen met minder dan $o(n / \log n)$ aanroepen van de PRG. Dit geldt zelfs als de PRF slechts één bit output genereert (een 0 of 1) en zelfs als de hacker wordt beperkt tot het stellen van eenvoudige, willekeurige vragen.

Het "Lange Output" Resultaat:
De auteurs keken ook naar PRFs die lange reeksen data produceren (niet alleen één bit). Ze bewezen dat zelfs als de bouwer "adaptief" mag zijn (vragen één voor één stelt en de antwoorden gebruikt om de volgende vraag te bepalen), er nog steeds een harde limiet is. Als de PRG de input slechts een klein beetje uitrekt, heb je er minstens ongeveer $out / \log n$ nodig. Als de PRGu de input een groot stuk uitrekt, heb je er minstens $out / r$ nodig.

Wat dit betekent voor de "Eén Aanroep" Droom

Lange tijd vroegen cryptografen zich af of een "single-call" constructie mogelijk was—het bouwen van een perfecte PRF door het zaadje slechts één keer uit te rekken.

Voor niet-adaptieve methoden: Dit paper sluit dit effectief uit. Je kunt geen veilige PRF bouwen met een constant aantal aanroepen (zoals 1, 2 of 10) als de inputgrootte groeit. De wiskunde laat dit simpelweg niet toe.
Voor adaptieve methoden: Het paper sluit een "single-call" constructie voor alle adaptieve scenario's niet uit. In plaats daarvan laten ze zien dat voor PRFs met lange outputs, het aantal aanroepen moet meeschalen met de outputgrootte. Je kunt niet volstaan met een heel klein, vast aantal aanroepen voor een enorme kluis als de output groot is. De vraag of een single-call adaptieve constructie bestaat voor PRFs met korte outputs, blijft open.

De "Query-Bounded" Nuance

De auteurs zijn zeer voorzichtig met hun aannames. Ze richten zich op een klasse van reducties die ze "query-bounded" noemen. In gewone taal betekent dit dat de interactie van de bouwer met de hacker beperkt is op een manier die niet afhangt van hoeveel vragen de hacker stelt. De auteurs argumenteren dat bijna elke constructie in de geschiedenis van de cryptografie aan deze beschrijving voldoet. Ze erkennen dat als iemand een vreemde, niet-standaard manier uitvindt om een PRF te bouwen waarbij de bouwer miljoenen keren vraagt, simpelweg omdat de hacker één vraag stelde, hun bewijs mogelijk niet van toepassing is. Maar voor alle praktische, standaard cryptografische ontwerpen houden de gevonden ondergrenzen stand.

De Kernboodschap

Dit paper suggereert niet alleen een limiet; het levert een wiskundig bewijs dat de "shortcut" naar het bouwen van PRFs een doodlopende weg is. Als je een veilige, black-box PRF wilt, kun je de stappen niet overslaan. Je moet de prijs betalen door de PRG genoeg keren aan te roepen om ervoor te zorgen dat de "entropie" (de willekeur en onvoorspelbaarheid) hoog genoeg is om elke hacker te misleiden. De beroemde GGM-constructie, die ongeveer $\omega(\log n)$ aanroepen gebruikt, blijkt bijna optimaal te zijn. De droom om een fort te bouwen met slechts één baksteen is in deze context wiskundig onmogelijk.

Technische Samenvatting: Ondergrenzen voor Black-Box Constructies van Pseudorandom Functions

Probleemstelling

Het artikel behandelt een fundamentele openstaande vraag in de cryptografie: wat is het minimale aantal aanroepen van een pseudorandom generator (PRG) die nodig is om een pseudorandom function (PRF) te construeren via een volledig black-box constructie?

Het baanbrekende werk van Goldreich, Goldwasser en Micali (GGM) stelde vast dat een PRF kan worden geconstrueerd uit een PRG met behulp van een boomgebaseerde aanpak. Wanneer dit wordt gecombineerd met de domein-extensietechniek van Levin, vereist deze constructie $\omega(\log n)$ aanroepen van de PRG, waarbij $n$ de inputlengte van de PRG is. Hoewel recent werk door Beimel, Malkin en Mazor bewees dat GGM optimaal is voor een specifieke klasse van "boomconstructies", blijft de algemene casus onopgelost. Specifiek is het onbekend of een PRF kan worden gebouwd met minder dan $\omega(\log n)$ aanroepen, of zelfs met een enkele aanroep, met behulp van algemene black-box technieken.

Dit werk onderzoekt deze vraag binnen het kader van volledig black-box constructies, waarbij zowel de constructie als de beveiligingsreductie black-box zijn. De auteurs richten zich specifiek op een klasse reducties die wordt aangeduid als query-bounded reductions, waarbij het aantal interacties dat de reductie heeft met de tegenstander (adversary) wordt begrensd door een polynoom die onafhankelijk is van de query-complexiteit van de tegenstander (mits de tegenstander voldoende succesvol is).

Methodologie

De auteurs maken gebruik van het meta-reductie paradigma om hun ondergrenzen vast te stellen. Deze techniek houdt in dat men een inefficiënte "echte" tegenstander construeert die een "ideale" tegenstander (die de PRF breekt) kan simuleren zonder directe toegang tot de onderliggende PRG, waardoor de beveiliging van de PRG wordt gebroken met minder queries dan toegestaan.

Belangrijke technische componenten:

Query-Bounded Reductions: De auteurs definiëren een reductie als query-bounded als het aantal keren dat deze de onderscheidende tegenstander bevraagt, begrensd wordt door een polynoom $d(n)$ , ongeacht hoeveel queries de tegenstander aan zijn oracle doet. Deze klasse vangt de meeste bekende reducties in de literatuur op, inclusief GGM en Goldreich-Levin constructies.
Ideale versus Echte Tegenstanders:
- Ideale Tegenstander ( $A_{ideal}$ ): Een inefficiënte tegenstander die exponentiële toegang heeft tot de PRG-oracle. Deze probeert de PRF te breken door een sleutel (key) te vinden die consistent is met een groot deel van de input-output paren.
- Echte Tegenstander ( $A_{real}$ ): Een inefficiënte tegenstander die geen toegang heeft tot de PRG. In plaats daarvan ontvangt deze de query-antwoord paren gegenereerd door de interactie van de reductie met de PRG. Deze probeert $A_{ideal}$ te simuleren door de waarschijnlijkheid te schatten dat een sleutel consistent is met de geobserveerde outputs.
Score Functies en Onafhankelijkheid:
- De kernuitdaging is dat de outputs van de PRF op verschillende inputs afhankelijk kunnen zijn als ze dezelfde PRG-seeds delen.
- De auteurs introduceren een procedure om "frequente seeds" (seeds die door veel inputs worden gebruikt) te identificeren en hun outputs te vervangen door vaste waarden. Dit vermindert het aantal actieve PRG-aanroepen.
- Voor de resterende inputs maken zij gebruik van een combinatorische bewering (Claim 3/6) om aan te tonen dat ofwel een grote verzameling inputs wederzijds disjuncte PRG-seeds gebruikt (wat onafhankelijkheidsargumenten via de Hoeffding-ongelijkheid mogelijk maakt), of dat het aantal van dergelijke keys verwaarloosbaar is.
- Om de statistische afstand tussen de ideale en echte tegenstander te behandelen, gebruiken de auteurs een gerandomiseerde drempelwaarde (uniform getrokken uit $[0.8, 1]$ ) in plaats van een vaste drempelwaarde. Dit vlakt de beslissingsgrens af, wat ervoor zorgt dat de output-distributie van de echte tegenstander statistisch dicht bij die van de ideale tegenstander ligt, mits het aantal inputs $m$ voldoende groot is ten opzicht van het aantal reductie-queries $d$ .
Entropy Argumenten voor Lange Outputs: Voor het tweede resultaat (Theorem 2) gebruiken de auteurs een entropie-gebaseerd argument. Ze construeren een specifieke PRG die willekeur (randomness) alleen toepast op een klein prefix van de seed. Dit beperkt de entropie van de PRF-output aanzienlijk ten opzichte van een echt willekeurige functie, waardoor een distinguisher de constructie kan breken als het aantal aanroepen te laag is.

Belangrijkste Bijdragen en Resultaten

1. Ondergrens voor Niet-Adaptieve Aanroepen (Theorem 1)

Het artikel bewijst dat er geen volledig black-box constructie van een PRF uit een PRG bestaat met behulp van niet-adaptieve aanroepen en query-bounded reductions als het aantal aanroepen $c$ voldoet aan:
$c = o\left(\frac{n}{\log n}\right) \quad \text{en} \quad c = o\left(\frac{in}{\log in}\right)$
waarbij $n$ de inputlengte van de PRG is en $in$ de inputlengte van de PRF.

Reikwijdte: Dit resultaat geldt zelfs voor zwakke PRFs (waarbij de tegenstander beperkt is tot i.i.d. uniforme queries) en voor PRFs met een één-bit output.
Implicatie: Dit sluit de mogelijkheid uit om een PRF te construeren met een constant aantal niet-adaptieve aanroepen (bijv. een enkele aanroep) voor PRFs met inputlengtes $in = \omega(\log n)$ , wat een specifiek geval van het openstaande probleem oplost voor query-bounded reductions.

2. Ondergrens voor Lange Outputs (Theorem 2)

Het artikel stelt een ondergrens vast voor PRFs met lange outputs ($out$) die ook geldt voor adaptieve constructies en geen query-bounded reductie vereist.

Resultaat: Er bestaat geen volledig black-box constructie van een PRF met outputlengte $out$ uit een PRG met stretch $r$ met minder dan $\frac{out}{\max(r, \omega(\log n))}$ aanroepen.
Vergelijking met GGM: De GGM-constructie (met Levin's truc) gebruikt $\omega(\log n)$ aanroepen van een $n$ -bit stretch PRG om een $n$ -bit output te produceren. Door dit te combineren met een 1-bit stretch PRG (die $O(n/\log n)$ aanroepen vereist), is het totaal aantal aanroepen aan een 1-bit stretch PRG $\omega(n)$ . Theorem 2 impliceert een ondergrens van $\Omega(n / \omega(\log n))$ , wat aantoont dat GGM optimaal is tot een factor $\omega(\log n)$ .

Betekenis en Claims

Het artikel claimt aanzienlijke vooruitgang te hebben geboekt in de langdurige vraag naar de optimaliteit van PRF-constructies uit PRGs.

Optimaliteit van GGM: Hoewel eerdere resultaten beperkt waren tot "boomconstructies", biedt dit werk ondergrenzen voor algemene black-box constructies onder specifieke maar natuurlijke aannames (query-bounded reductions).
Resolutie van de Single-Call Case: De auteurs geven expliciet aan dat hun resultaat de vraag oplost of een PRF kan worden gebouwd met een enkele aanroep naar de PRG voor de klasse van query-bounded reductions. Ze demonstreren dat een dergelijke constructie onmogelijk is voor PRFs met inputlengtes $in = \omega(\log n)$ .
Robuustheid: De onmogelijkheidsresultaten blijven van kracht, zelfs voor zwakke PRFs en, in het geval van lange outputs, voor adaptieve constructies.
Beperkingen: De auteurs erkennen bescheiden dat hun hoofdresultaat (Theorem 1) steunt op de "query-bounded" aanname. Ze merken op dat het een openstaande vraag blijft of deze ondergrenzen kunnen worden uitgebreid naar alle black-box reducties, aangezien hun bewijs rust op het feit dat het aantal interacties van de reductie onafhankelijk is van de query-complexiteit van de tegenstander.

Samenvattend demonstreert het artikel dat de GGM-constructie bijna optimaal is qua het aantal PRG-invocaties die vereist zijn, met name voor niet-adaptieve constructies en die met lange outputs, door gebruik te maken van meta-reductietechnieken en zorgvuldige entropie-analyse.