Compressed Permutation Oracles Revisited

In de digitale wereld rust veiligheid vaak op het idee van een perfecte, onvoorspelbare machine. Cryptografen stellen zich een apparaat voor dat elke invoer neemt en een volledig willekeurig ogende uitvoer produceert, maar met één cruciale regel: als je dezelfde invoer twee keer invoert, krijg je elke keer dezelfde uitvoer. Dit staat bekend als een willekeurige permutatie. Het is de onzichtbare motor achter veel van de hulpmiddelen die we gebruiken om gegevens veilig te houden, van de manier waarop onze wachtwoorden worden opgeslagen tot de algoritmen die de integriteit van onze communicatie verifiëren. Om te testen of deze hulpmiddelen werkelijk veilig zijn, stellen wetenschappers zich een krachtige aanvaller voor die vragen aan deze machine kan stellen. In de klassieke wereld stelt een aanvaller één vraag tegelijk. Maar in de kwantumwereld kan een aanvaller veel vragen tegelijk stellen, door ze te superponeren op een manier die voelt alsof men elke mogelijke vraag tegelijkertijd stelt. Deze mogelijkheid om in superpositie te bevragen, maakt het bewijzen van veiligheid ongelooflijk moeilijk, omdat de aanvaller informatie verkrijgt op een manier die onze gebruikelijke intuïtie tart.

Jarenlang hebben onderzoekers geprobeerd een wiskundig model te bouwen om bij te houden wat een kwantum-aanvaller leert van deze vragen. Een veelbelovende methode, genaamd de gecomprimeerde oracle, werkt als een vereenvoudigd notitieblok. In plaats van de volledige, enorme machine bij te houden, registreert het notitieblok alleen de specifieke paren van invoer en uitvoer waar de aanvaller tot nu toe naar heeft gevraagd. Dit maakt de wiskunde beheersbaar, waardoor wetenschappers kunnen bewijzen dat bepaalde beveiligingssystemen veilig zijn. Echter, een aanzienlijk probleem plaagde deze methode: het notitieblok was niet perfect nauwkeurig. Het werd alleen bewezen correct te werken wanneer de aanvaller een relatief klein aantal vragen stelde. Als de aanvaller te veel vragen stelde, kon de voorspelling van het notitieblok afwijken van de realiteit, waardoor de veiligheidsbewijzen onbetrouwbaar werden. Deze beperking betekende dat we voor veel moderne cryptografische systemen niet zeker konden zijn of ze zouden standhouden tegen een vastberaden kwantum-adversary.

Een team van onderzoekers heeft deze methode nu herzien en de meest kritieke fout ervan hersteld. Ze hebben aangetoond dat het gecomprimeerde notitieblok veel betrouwbaarder is dan voorheen werd gedacht. Hun nieuwe analyse bewijst dat de methode correct werkt, zelfs wanneer de aanvaller een aantal vragen stelt dat veel groter is dan voorheen — specifiek, tot de vierkantswortel van het totaal aantal mogelijke invoerwaarden. Dit is een enorme verbetering ten opzichte van de vorige limiet, die slechts een fractie van dat aantal was. De onderzoekers bereikten dit door te veranderen hoe ze de verbinding tussen de echte, complexe machine en het vereenvoudigde notitieblok bouwden. In plaats van een ingewikkelde, indirecte constructie, hebben zij aangetoond dat het notitieblok kan worden beschouwd als een directe meting van de onderliggende staat van de machine. Dit nieuwe perspectief maakt de wiskunde niet alleen schoner en directer, maar verwijdert ook de kunstmatige bovengrens voor het aantal vragen dat de aanvaller kan stellen voordat het bewijs instort.

De impact van deze verbetering is onmiddellijk en concreet. De onderzoekers hebben hun nieuwe, nauwere bewijs toegepast op twee van de belangrijkste structuren in de moderne cryptografie: de sponge-constructie en de Davies-Meyer compressiefunctie. Dit zijn de blauwdrukken die worden gebruikt om de hashfuncties te bouwen die onze digitale wereld beveiligen, inclusief de SHA-3-standaard en de oudere SHA-1 en SHA-2-systemen. Met behulp van hun verfijnde methode hebben de onderzoekers precies berekend hoeveel kwantum-queries een aanvaller nodig zou hebben om deze systemen te breken. Ze vonden dat de veiligheid van deze systemen robuust is, waarbij een aanvaller een aantal operaties moet uitvoeren dat groeit met de vierkantswortel van de omvang van het systeem voor het vinden van botsingen (collisions), en zelfs meer voor pre-images. Hun resultaten bieden expliciete, concrete cijfers voor de veiligheid van de vier belangrijkste SHA-3-varianten, en laten zien dat deze veilig blijven, zelfs tegen krachtige kwantumcomputers, mits die computers geen manier vinden om specifieke structurele zwakheden in het onderliggende ontwerp uit te buiten.

De onderzoekers waren zorgvuldig in het onderscheid tussen het bewijzen van de veiligheid van het wiskundige model en de veiligheid van de feitelijke hardware. Hun werk bevestigt dat, indien de onderliggende willekeurige permutatie zich gedraagt zoals verwacht, de cryptografische constructies die daarop zijn gebouwd, veilig zijn. Ze beweerden niet dat de specifieke permutatie die in de echte wereld wordt gebruikt voor de SHA-3-standaard perfect is, maar wel dat het ontwerp zelf solide is. Dit onderscheid is essentieel; het betekent dat het falen van een systeem waarschijnlijk zou komen door een fout in de specifieke implementatie van de permutatie, en niet door een fundamentele zwakte in de manier waarop het systeem is opgebouwd. Door de wiskundige grenzen te verstrengen, hebben de onderzoekers cryptografen een krachtiger instrument gegeven om toekomstige systemen te analyseren, zodat de volgende generatie digitale beveiliging kan worden ontworpen met een helder en accuraat begrip van de kwantumdreigingen waar het voor staat.

De kern van hun ontdekking ligt in de manier waarop zij de relatie tussen de queries van de aanvaller en de database van bekende antwoorden behandelen. In de oude methode was de verbinding tussen de echte machine en het notitieblok enigszins losjes, wat fouten introduceerde die cumulatief werden naarmig de hoeveelheid vragen groeide. De nieuwe aanpak behandelt het notitieblok als een directe, coherente reflectie van de staat van de machine. Zij hebben een brug geconstrueerd tussen de twee die de exacte wiskundige relaties behoudt, waardoor het notitieblok de ware staat van het systeem nooit uit het oog verliest, ongeacht hoeveel vragen er worden gesteld. Deze brug is gebouwd met een techniek die de informatie verdeelt in verschillende niveaus, vergelijkbaar met het organiseren van een bibliotheek per verdieping, en vervolgens de verbindingen tussen hen zorgvuldig normaliseert. Deze normalisatie zorgt ervoor dat de in het notitieblok berekende waarschijnlijkheden overeenkomen met de waarschijnlijkheden in de echte wereld, waardoor de drift die voorheen de bruikbaarheid van de methode beperkte, wordt geëlimineerd.

Dit werk verbetert niet slechts een enkel bewijs; het versterkt de gehele fundering van de kwantumveiligheidsanalyse voor symmetrische cryptografie. Door de limiet van de gecomprimeerde oracle te verleggen van een klein fractie van de mogelijke invoerwaarden naar de vierkantswortel, hebben de onderzoekers de deur geopend voor het analyseren van systemen die voorheen buiten bereik lagen. De resultaten suggereren dat het kwantumvoordeel bij het breken van dit specifieke type cryptografische systemen niet zo groot is als men vreest, mits de systemen voldoende capaciteit hebben. Het vermogen van het team om expliciete constanten en concrete grenzen te leveren, betekent dat ingenieurs nu het exacte niveau van veiligheid die een systeem biedt kunnen berekenen, in plaats van te vertrouwen op vage schattingen. Deze helderheid is essentieel voor het bouwen van de digitale infrastructuur van de toekomst, om ervoor te zorgen dat onze gegevens beschermd blijven in een tijdperk waarin kwantumcomputers een realiteit worden.

De studie breidt haar bevindingen ook uit naar ideale ciphers, die de bouwstenen zijn voor veel encryptieschema's. In dit model hangt de veiligheid af van een familie van permutaties, elk gecontroleerd door een andere sleutel. De onderzoekers hebben aangetoond dat hun verbeterde methode hier net zo goed werkt, zelfs wanneer de aanvaller het systeem in superpositie kan bevragen over verschillende sleutels. Dit is een significant resultaat omdat het betekent dat de veiligheid van deze systemen niet degradeert simpelweg omdat er veel sleutels betrokken zijn. De analyse blijft standhouden, ongeacht het aantal sleutels, wat het idee versterkt dat de fundamentele structuur van deze cryptografische ontwerpen solide is tegen kwantumaanvallen.

Uiteindelijk vertegenwoordigt dit artikel een volwassenwording van de instrumenten die worden gebruikt om kwantumveiligheid te begrijpen. Het neemt een methode die ooit als te fragiel werd beschouwd voor rigoureuze bewijsvoering en versterkt deze tot een betrouwbaar instrument. De onderzoekers hebben aangetoond dat de gecomprimeerde oracle niet slechts een heuristische benadering is, maar een wiskundig solide manier om kwantuminformatie bij te houden. Door dit te doen, hebben zij de cryptografische gemeenschap een helderder beeld van het landschap gegeven, waardoor zij systemen kunnen ontwerpen die bewezen veilig zijn tegen de meest geavanceerde dreigingen. Het werk staat als een testament voor de kracht van het verfijnen van onze wiskundige modellen om de complexe realiteiten van de kwantumwereld beter te reflecteren.