Certified Randomness with Optimal Rate

In de digitale wereld is vertrouwen een kwetsbaar goed. Wanneer we online stemmen, geheime codes genereren voor bankzaken of leiders kiezen voor gedecentraliseerde netwerken, vertrouwen we op een willekeur die werkelijk onvoorspelbaar is. Als deze willekeur voorspelbaar of bevooroordeeld is, stort het hele systeem in. Decennialang hebben wetenschappers gezocht naar een manier om dergelijke willekeur te genereren zonder dat daarvoor de machine die de generatie uitvoert, vertrouwd hoeft te worden. Het ideale scenario omvat een apparaat dat een reeks bits produceert — enen en nullen — die zo chaotisch en uniform is dat niemand, zelfs niet de eigenaar van het apparaat, de uitkomst van tevoren had kunnen raden. Dit is de heilige graal van "gecertificeerde willekeur": een wiskundige garantie dat de output werkelijk willekeurig is, verifieerbaar door iedereen, zonder dat daarvoor een vooraf bestaande geheime zaadwaarde (seed) nodig is.

De uitdaging is altijd geweest dat bestaande methoden ofwel zwakke willekeur produceerden die gemakkelijk gemanipuleerd kon worden, ofwel een vertrouwde mens vereisten om een klein, willekeurig startgetal te leveren. Een nieuwe studie van Siddhartha Jain, Saachi Mutreja en Bhaskar Roberts pakt deze fundamentele beperking aan. Zij hebben een protocol ontwikkeld waarmee een quantumcomputer kan bewijzen dat het een reeks bits heeft gegenereerd met bijna perfecte willekeur, zelfs als de computer kwaadwillend is en de persoon die het resultaat controleert volledig deterministisch is en geen eigen willekeurige getallen bezit. Deze doorbraak elimineert de noodzaak voor een vertrouwde startpunt en bereikt een snelheid van willekeur die theoretisch zo hoog mogelijk is.

De onderzoekers werkten binnen een raamwerk dat bekend staat als het quantum random oracle model, een theoretische setting waarin alle partijen toegang hebben tot een publieke, perfect willekeurige functie die fungeert als een universele hash. In deze omgeving hebben zij een systeem geconstrueerd waarbij een quantum prover een lange reeks bits kan genereren en een kort bewijs kan leveren dat de reeks werkelijk willekeurig is. De kerninnovatie is dat de verifier, die het bewijs controleert, niet zelf willekeurig hoeft te zijn; deze kan een vast, deterministisch algoritme zijn. Eerdere pogingen om dit te bereiken faalden ofwel in het garanderen van een hoge kwaliteit willekeur, ofwel door te vertrouwen op een verifier die een kleine, vertrouwde willekeurige seed nodig had om het proces te starten. Het nieuwe protocol elimineert die seed volledig, en bewijst dat een deterministische verifier nog steeds overtuigd kan worden van de willekeur van een lange reeks gegenereerd door een onbetrouwbaar quantumapparaat.

Om de betekenis te begrijpen, moet men kijken naar wat er gebeurt als een systeem niet perfect willekeurig is. Als een reeks bits slechts "zwak" willekeurig is, kan deze er chaotisch uitzien, maar kan deze nog steeds bevooroordeeld zijn naar bepaalde patronen, waardoor het kwetsbaar is voor voorspelling. De onderzoekers bewezen dat hun methode een niveau van entropie, of wanorde, garandeert dat bijna maximaal is. In praktische termen betekent dit dat voor een reeks van een specifieke lengte, het aantal bits dat werkelijk onvoorspelbaar is, bijna gelijk is aan de totale lengte van de reeks. Het enige minuscule verlies aan willekeur is een logaritmische hoeveelheid, wat onvermijdelijk is vanwege de aard van de wetten van de fysica en de informatica. Dit is een enorme verbetering ten opzichte van eerdere methoden, die vaak reeksen produceerden waarbij de hoeveelheid gegarandeerde willekeur slechts een fractie van de totale lengte bedroeg.

Het protocol werkt in twee hoofdfasen. Eerst genereert het quantumapparaat een "zwak" willekeurige bron met behulp van een specifieke wiskundige constructie die bewezen veilig is tegen quantumattacks. Deze bron is nog niet goed genoeg voor toepassingen met een hoog risico. In de tweede fase laat het apparaat deze bron door een compressiefunctie gaan, die fungeert als een filter. Dit filter condenseert de zwakke bron tot een kortere, veel sterkere reeks bits. De onderzoekers hebben aangetoond dat zelfs als een tegenstander probeert het proces te manipuleren door specifieke inputs te kiezen of het gedrag van de functie te observeren, zij de uiteindelijke output niet voorspelbaar kunnen maken. De uiteindelijke reeks behoudt een hoog niveau van min-entropie, een maatstaf voor hoe moeilijk het is om de meest waarschijnlijke uitkomst te raden, zelfs wanneer de tegenstander de volledige geschiedenis van de interactie heeft gezien.

Een cruciaal onderdeel van dit werk is het concept van "conditionele" min-entropie. In veel real-world toepassingen, zoals een publieke willekeurige beacon die elke uur een nieuw willekeurig getal uitzendt, hangt de veiligheid van het huidige getal af van het feit dat het niet voorspeld kan worden, zelfs als een aanvaller alles weet over de voorgaande getallen. De onderzoekers toonden aan dat hun protocol garandeert dat elke nieuwe puls van willekeur onvoorspelbaar is, zelfs wanneer deze geconditioneerd is op alle berichten en gegevens die eraan voorafgingen. Dit is essentieel voor toepassingen zoals leiderverkiezing in blockchain-netwerken of het genereren van gemeenschappelijke willekeurige reeksen voor cryptografische protocollen, waarbij de integriteit van de huidige ronde afhangt van de onvoorspelbaarheid van het verleden.

Het team heeft ook de beperkingen van hun eigen werk met rigoureuze eerlijkheid geadresseerd. Zij bewezen dat het onmogelijk is om perfecte, uniforme willekeur te bereiken met een deterministische verifier als de tegenstander wordt toegestaan om gedurende een polynomiale tijd te opereren. Een aanvaller zou theoretisch een techniek genaamd rejection sampling kunnen gebruiken om een klein aantal bits in de output vast te leggen, waardoor het systeem effectief "bespeeld" wordt om een licht bevooroordeeld resultaat te produceren. De onderzoekers toonden echter aan dat hun protocol het best mogelijke resultaat bereikt onder deze beperkingen: het garandeert dat het aantal bits dat door een aanvaller kan worden vastgelegd zo klein is, dat de resterende willekeur nog steeds voldoende is voor alle praktische cryptografische doeleinden. Het verlies is verwaarloosbaar, en de veiligheid blijft standhouden tegen elke tegenstander met realistische rekenkracht.

Dit werk heeft directe implicaties voor de toekomst van veilige communicatie en gedecentraliseerde systemen. Door de noodzaak van een vertrouwde seed te verwijderen, maakt het protocol de creatie van willekeurige beacons mogelijk die op een enkel, onbetrouwbaar quantumapparaat kunnen draaien. Zo'n beacon zou periodiek verse, onvoorspelbare willekeurige getallen kunnen publiceren die iedereen kan verifiëren. De veiligheid van deze getallen zou niet afhangen van de eerlijkheid van de apparatuurbeheerder, maar van de wetten van de quantummechanica en de wiskundige structuur van het protocol zelf. Hoewel de huidige implementatie steunt op theoretische modellen, is de weg naar praktische toepassing duidelijker dan ooit, wat een manier biedt om de vertrouwde willekeur te genereren die de moderne digitale samenleving dringend nodig heeft, zonder dat we de machine hoeven te vertrouwen.

De studie vormt een definitief antwoord op een vraag die eerder door onderzoekers werd gesteld over de grenzen van gecertificeerde willekeur. Het bevestigt dat, hoewel perfecte uniformiteit wiskundig onbereikbaar is voor een deterministische verifier, een niveau van willekeur dat effectief ononderscheidbaar is van perfectie, wel bereikbaar is. De onderzoekers hebben niet alleen de snelheid van willekeur verbeterd; zij hebben de grenzen van wat mogelijk is in een vertrouwensloze omgeving hergedefinieerd. Hun constructie biedt een robuuste, onvoorwaardelijke garantie van veiligheid in het quantum random oracle model, en zet een nieuwe standaard voor hoe we over willekeur denken in het quantumtijdperk. Het resultaat is een protocol dat zowel theoretisch solide als praktisch relevant is, en de brug slaat tussen abstracte quantumtheorie en de concrete behoeften van een veilige digitale infrastructuur.