Verified Pythagorean Composition for Adaptive Cryptographic Games: Noise Flooding in Homomorphic Encryption

Stel je voor dat je een geheim bericht naar een vriend stuurt, maar je moet het versturen via een postkantoor dat wordt gerund door een ondeugende goblin die ervan houdt om brieven te bespieden. In de oude dagen sloot je de brief in een kistje op, maar zodra de goblin de kist opende om de boodschap te lezen, was het geheim weg. Toen kwam er een magische uitvinding genaamd Homomorfe Encryptie. Dit is als een speciale vergrendelde kist waardoor de goblin wiskunde kan uitvoeren op de vergrendelde brieven — optellen, vermenigvuldigen, sorteren — zonder ze ooit te ontgrendelen. Wanneer de goblin het resultaat aan je teruggeeft, ontgrendel jij het en is het het juiste antwoord op de wiskundige som, ook al heeft de goblin de getallen binnenin nooit gezien.

Echter, er is een addertje onder het gras. In de meest populaire versie van deze magie, genaamd CKKS, is de wiskunde niet perfect. Omdat de getallen zo complex zijn, is het resultaat dat je terugkrijgt een beetje "wazig" of benaderd, zoals een wazige foto in plaats van een scherpe. Meestal is deze wazigheid geen probleem; het is slechts een klein beetje statische ruis. Maar een sluwe goblin (een aanvaller) kan om het antwoord op veel verschillende wiskundige problemen vragen, de wazige resultaten vergelijken met wat zij denken dat het antwoord zou moeten zijn, en deze kleine verschillen gebruiken om langzaam jouw geheime sleutel te reconstrueren. Het is also alsof de goblin precies kon zien hoeveel je vergrendelde kist wiebelde wanneer je ertegen schudde, en die wiebel gebruikte om de combinatie te achterhalen. Om dit te stoppen, bedachten cryptografen een verdediging genaamd Noise Flooding (ruisoverstroming): ze voegen een enorme, willekeurige uitbarsting van statische ruis toe aan het antwoord voordat ze het terugsturen, waardoor de kleine aanwijzingen die de goblin probeerde te gebruiken, worden overstemd.

De grote vraag was: Hoeveel statische ruis moet je toevoegen? Als je te weinig toevoegt, kan de goblin het geheim nog steeds horen. Als je te veel toevoegt, wordt het antwoord zo wazig dat het onbruikbaar is. Het lastige deel is dat de goblin vragen één voor één kan stellen, waarbij hij zijn strategie aanpast op basis van je vorige antwoorden. Als je voor elke vraag apart statische ruis toevoegt, loopt de "kosten" van de ruis snel op, waardoor je de antwoorden extreem wazig moet maken. Maar een slim wiskundig idee suggereerde dat als je naar het hele spel in één keer kijkt, de kosten veel langzamer groeien — zoals de vierkantswortel van het aantal vragen, in plaats van het aantal zelf. Dit papier gaat over het bewijzen dat dit slimme idee daadwerkelijk werkt, en het bewijzen op een manier die een computer kan controleren om er zeker van te zijn dat er geen fouten zijn gemaakt.

---

De Grote Ontdekking van het Papier: Het "Pythagoreïsche" Geheim

Dit papier, getiteld "Verified Pythagorean Composition for Adaptive Cryptographic Games," is een enorme prestatie in formele verificatie, wat in feite het gebruik van een superintelligente computer is om wiskundige bewijzen op fouten te controleren. De auteurs, een team van onderzoekers, hebben een beroemd beveiligingsargument over noise flooding vertaald naar een taal die de computer kan begrijpen. Ze hebben de computer vervolgens gevraagd om elke enkele logische stap te verifiëren, om te garanderen dat de wiskunde standhoudt onder de meest intense controle.

De kern van hun werk is een nieuwe manier van denken over hoe fouten zich opstapelen wanneer je een sluwe aanvaller hebt die veel vragen stelt.

Het "Wazige Foto" Probleem

Stel je voor dat je probeert een geheim te verbergen door een beetje statische ruis aan een foto toe te voegen. Als je een heel klein beetje statische ruis toevoegt, is de foto nog steeds duidelijk, maar een scherpziende goblin kan het geheim opmerken. Als je veel statische ruis toevoegt, is het geheim veilig, maar is de foto een puinhoop.
In de wereld van encryptie wordt de "statische ruis" ruis genoemd. Het papier kijkt naar een scenario waarin een aanvaller tot $q$ keer om het gedecodeerde resultaat van een bericht vraagt. Elke keer dat dit gebeurt, voegt de verdediger ruis toe om het geheim te verbergen.

• De Oude Manier (Lineaire Verlies): Als je elke vraag als een afzonderlijke gebeurtenis behandelt, moet je genoeg ruis toevoegen om veilig te zijn voor elke enkele vraag. Als de aanvaller 100 vragen stelt, heb je misschien wel 100 keer de ruis nodig, waardoor het uiteindelijke resultaat volkomen onbruikbaar wordt.
• De Nieuwe Manier (Vierkantswortel Verlies): Het papier bevestigt een slimmere strategie. Het laat zien dat omdat de vragen van de aanvaller met elkaar verbonden zijn (ze zijn "adaptief"), de totale hoeveelheid ruis die nodig is, slechts groeit met de vierkantswortel van het aantal vragen ($\sqrt{q}$). Dus voor 100 vragen heb je alleen 10 keer de ruis nodig, niet 100. Dit is een enorme winst, omdat het betekent dat je de antwoorden veel duidelijker kunt houden terwijl je nog steeds veilig bent.

De "Pythagoreïsche" Analogie

Waarom noemen ze het "Pythagoreïsch"? Denk aan een rechthoekige driehoek. Als je twee zijden hebt met lengtes 3 en 4, dan is de langste zijde (de hypotenusa) niet $3 + 4 = 7$. Het is $\sqrt{3^2 + 4^2} = 5$. De totale lengte is korter dan simpelweg de zijden bij elkaar op te tellen.
In dit papier zijn de "zijden" de kleine beetjes risico (of "kosten") van de vragen van de aanvaller.

• De Fout: Als je de risico's gewoon bij elkaar optelt ($3 + 4$), krijg je een enorm, eng getal.
• De Realiteit: De auteurs bewijzen dat deze risico's combineren als de zijden van een driehoek. Ze "cancellen" elkaar een beetje omdat ze aan elkaar gerelateerd zijn. Het totale risico is de vierkantswortel van de som van de kwadraten.
  Het papier bewijst dat je deze risico's apart kunt bijhouden (als "Conditional Kullback-Leibler kosten", wat een chique wiskundige manier is om te zeggen "hoe verschillend de antwoorden eruitzien") en ze pas aan het einde omzet in een definitieve "veiligheidsscore". Dit zorgt ervoor dat de wiskunde efficiënt blijft en de ruis laag blijft.

De Rol van de Computer: De "Robotadvocaat"

Je vraagt je misschien af: "Waarom hebben we een computer nodig om dit te controleren? Is wiskunde niet gewoon wiskunde?"
Het probleem is dat deze bewijzen ongelooflijk complex zijn. Ze bevatten duizenden stappen en gaan over waarschijnlijkheden, willekeurige getallen en het gedrag van een sluwe aanvaller die van gedachten verandert. Het is makkelijk voor een mens om een klein detail te missen of een kleine aanname te doen die het hele argument doet instorten.
De auteurs gebruikten een tool genaamd Rocq (een proof assistant) en een bibliotheek genaamd SSProve. Ze hebben het bewijs niet alleen op papier geschreven; ze hebben een digitaal model van het encryptiespel gebouwd.

1. De Logica: Ze creëerden een nieuwe set regels (een "programmalogica") die de computer vertelt hoe deze "Pythagoreïsche" risicocomcombinaties te behandelen.
2. De Compiler: Ze bouwden een "trace compiler", wat een soort robot is die het programma van de aanvaller in de gaten houdt. De robot kan de aanvaller pauzeren, even kijken naar de volgende zet, en de aanvaller dan weer door laten gaan, terwijl het geheim veilig blijft.
3. De Verificatie: De computer controleerde elke regel code en elke wiskundige stap. Het bevestigde dat als de onderliggende encryptie veilig is, het toepassen van deze noise flooding-verdediging het veilig maakt tegen deze specifieke soorten aanvallen, met de "vierkantswortel"-efficiëntie.

Wat dit voor jou betekent

Dit papier vindt geen nieuwe encryptiemethode of een nieuwe aanval uit. In plaats daarvan neemt het een bekende verdediging (noise flooding) en bewijst het, met absolute wiskundige zekerheid, dat het werkt precies zoals de slimme "Pythagoreïsche" theorie voorspelde.

• Het ontkracht het idee dat je een enorme hoeveelheid ruis moet toevoegen (lineaire groei) om veilig te zijn tegen adaptieve aanvallers.
• Het bewijst dat de "vierkantswortel"-groei echt is en veilig, mits de onderliggende encryptie al veilig is.
• Het bevestigt dat de complexe wiskunde achter deze verdediging geen verborgen gaten heeft.

De auteurs zijn zeer voorzichtig in hun stelling dat dit een geverifieerd bewijs is van de logica, en geen garantie dat elke specifieke encryptiesoftware in de wereld perfect is. Ze bewezen dat als je een goede encryptiemethode hebt en je deze noise flooding correct toepast, de wiskunde zegt dat je veilig bent. Ze merkten ook op dat ze niet de specifieke details van de meest populaire encryptiemethode (CKKS) zelf hebben gecontroleerd, maar enkel de logica van de ruisverdediging. Maar voor de beschermers van digitale privacy is dit een enorme stap voorwaarts: het betekent dat we de wiskunde kunnen vertrouwen die onze geheimen veilig houdt, zelfs wanneer de aanvallers slim en volhardend zijn.

Kortom, het papier is als een meesterarchitect die, na jaren van debat, eindelijk een team van robotinspecteurs inschakelt om te bevestigen dat het ontwerp van de brug deugt. Ze hebben bewezen dat de brug niet met twee keer zoveel staal gebouwd hoeft te worden als we eerst dachten; de slimme geometrie van het ontwerp (de Pythagoreïsche regel) is voldoende om het gewicht te dragen, waardoor het pad vrij blijft en de geheimen verborgen blijven.