💻 computer science

From Finite Enumeration to Universal Proof: Ring-Theoretic Foundations for PQC Hardware Masking Verification

Dit artikel presenteert de eerste machine-gecontroleerde universele bewijsvoering in Lean 4 voor de soundness van hardware-maskering in post-kwantumcryptografie, waardoor de afhankelijkheid van eindige enumeraties wordt vervangen door een wiskundig onderbouwde garantie die geldig is voor alle moduluswaarden $q$ , inclusief die van ML-KEM en ML-DSA.

Oorspronkelijke auteurs: Ray Iskander, Khaled Kirah

Gepubliceerd 2026-04-22

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Ray Iskander, Khaled Kirah

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

Stel je voor dat je een onbreekbare kluis bouwt voor de toekomst, een kluis die zelfs supercomputers van morgen niet kunnen kraken. Dit is wat Post-Quantum Cryptografie (PQC) doet: het beschermt onze digitale wereld tegen de komst van quantumcomputers.

Maar hier is het probleem: als je zo'n kluis bouwt, moet je zeker weten dat er geen "luikjes" zijn waar een dief langs kan gluren. In de digitale wereld gebeurt dit vaak via stroomverbruik. Als een computer een geheime sleutel berekent, verbruikt hij net iets meer stroom dan normaal. Een slimme hacker kan deze stroompatronen meten en de sleutel reconstrueren.

Om dit te voorkomen, gebruiken ingenieurs een trucje genaamd maskering. Het is alsof je de geheime sleutel niet in één hand houdt, maar in twee helften verdeelt over twee verschillende handen. Geen enkele hand op zich weet wat de geheime sleutel is; alleen samen vormen ze de sleutel. Zolang de handen niet samenkomen op een onveilig moment, is de sleutel veilig.

Het Probleem: De "Vijf-Steentjes" Test

In een eerder artikel (Paper 2 van deze auteurs) hadden de onderzoekers een hulpmiddel gebouwd genaamd QANARY. Dit is een soort super-scan die controleert of hun kluisontwerpen veilig zijn.

Het probleem was echter hoe ze dit controleerden. Ze keken naar een heel klein model van de kluis, gemaakt met slechts vijf steentjes (een wiskundige modulus van 5). Ze lieten een computer (een SMT-oplosser) alle mogelijke combinaties van die vijf steentjes doorlopen om te bewijven dat de maskering werkte.

Het was alsof je een brug wilt testen voor vrachtwagens, maar je test hem alleen met een fiets.

De vraag: Werkt het voor een fiets? Ja, perfect.
De realiteit: De echte brug moet een enorme vrachtwagen dragen (de echte cryptografische sleutels, die miljoenen keer groter zijn).

De onderzoekers wisten dat hun test met de "vijf steentjes" waarschijnlijk werkte, maar ze hadden geen wiskundig bewijs dat het ook werkte voor de enorme getallen die nodig zijn voor de echte wereld (zoals 3.329 of 8 miljoen). Ze hadden een gat in hun bewijs.

De Oplossing: De Universele Sleutel

In dit nieuwe artikel (Paper 3) hebben Ray Iskander en Khaled Kirah dat gat dichtgemaakt. Ze zijn niet gaan testen met meer steentjes; ze zijn de taal van de wiskunde zelf gaan gebruiken.

Ze hebben een universeel bewijs gevonden, geschreven in een speciale programmeertaal genaamd Lean 4.

De Analogie van de Magische Formule:
Stel je voor dat je wilt bewijzen dat als je een bal in een doos gooit, deze altijd binnen blijft.

De oude manier (SMT): Je gooit een bal in een doos van 5 cm, dan in een van 10 cm, dan 20 cm... je test duizenden keren. Als het elke keer lukt, denk je: "Het werkt wel." Maar je weet het niet zeker voor een doos van 1 meter.
De nieuwe manier (Lean 4): Ze hebben een magische formule gevonden die zegt: "Ongeacht hoe groot de doos is, als je de bal volgens deze regels gooit, blijft hij erin." Ze hoeven de bal niet één keer te gooien; de formule is het bewijs.

Wat hebben ze precies gedaan?

Van 225 tests naar 5 regels: De oude computer had 225 verschillende tests nodig om te zeggen "Ja, het werkt voor de kleine doos". De nieuwe formule van de onderzoekers is slechts 5 regels code lang. Deze 5 regels bewijzen dat het voor elke mogelijke doosgrootte werkt, van klein tot oneindig groot.
Geen twijfel meer: Omdat dit bewijs is gecontroleerd door een computer die zelf de regels van de wiskunde kent (de "Lean-kern"), hoeven we niet te vertrouwen op de software die de tests uitvoerde. Het bewijs is onweerlegbaar.
Toekomstbestendig: Als de wereld morgen besluit om nog grotere getallen te gebruiken voor hun beveiliging, is hun bewijs nog steeds geldig. Ze hoeven het niet opnieuw te doen.

Waarom is dit belangrijk voor jou?

Voor de gemiddelde gebruiker betekent dit dat de beveiliging van banken, overheidsdata en onze persoonlijke berichten in de toekomst veel steviger is.

Betrouwbaarheid: We weten nu met 100% zeker dat de "maskering" werkt, niet omdat we het hebben getest op een klein voorbeeld, maar omdat het wiskundig onmogelijk is dat het faalt.
Efficiëntie: Ingenieurs hoeven niet meer maandenlang te testen voor elke nieuwe versie van een beveiligingsstandaard. Ze kunnen vertrouwen op dit universele bewijs.

Samenvatting in één zin

De onderzoekers hebben bewezen dat hun methode om geheime sleutels te verbergen (maskering) werkt voor elke mogelijke grootte van sleutel, niet alleen voor de kleine testversies, door een kort, elegant wiskundig bewijs te vinden dat elke twijfel wegneemt.

Het is alsof ze van een lokaal weersvoorspelling ("Het regent vandaag in dit dorp") zijn gegaan naar een universele wet van de natuurkunde ("Als er wolken zijn, kan het regenen, ongeacht waar je bent"). Dat is een enorme stap voor de veiligheid van onze digitale wereld.

Titel

Van eindige enumeratie naar universeel bewijs: Ring-theoretische fundamenten voor verificatie van PQC-hardware-maskering.

1. Het Probleem

De migratie naar post-kwantumcryptografie (PQC), met name de nieuwe NIST-standaarden ML-KEM (FIPS 203) en ML-DSA (FIPS 204), vereist robuuste hardware-implementaties die bestand zijn tegen zijkanalaanvallen (zoals stroomverbruik). Een veelgebruikte verdediging is aritmische maskering, waarbij geheime waarden worden opgesplitst in delen (shares) modulo $q$ .

Het eerdere werk van de auteurs (het QANARY-framework) gebruikte SMT-oplossers (Z3 en CVC5) om de beveiliging van deze maskering te verifiëren. Dit resulteerde echter in een fundamentele beperking:

Eindige domein-verificatie: De geldigheid van het kernbewijs (Theorema 3.9.1) werd alleen geverifieerd voor een kleine modulus $q=5$ door alle 225 mogelijke Boolese draadfuncties uit te tellen.
Geen universele geldigheid: SMT-oplossers kunnen geen structurele inductie uitvoeren. Een bewijs voor $q=5$ garandeert geen correctheid voor de productmoduli die in de praktijk worden gebruikt, namelijk $q=3.329$ (ML-KEM) en $q=8.380.417$ (ML-DSA).
Vertrouwensbasis: De huidige aanpak vertrouwt op de correctheid van complexe SMT-oplossers en Python-encodings, wat de "trusted base" (vertrouwensbasis) vergroot.

Er was een urgente behoefte aan een universeel, machine-gecontroleerd bewijs dat geldt voor elke modulus $q > 0$ , om de beveiliging van toekomstige PQC-standaarden te garanderen zonder herverificatie.

2. Methodologie

De auteurs schakelen over van een op bit-vector gebaseerde SMT-aanpak naar Interactieve Theorema Bewijzen (Interactive Theorem Proving - ITP) met Lean 4 en de wiskundige bibliotheek Mathlib.

Abstraktieniveau: In plaats van te werken met concrete bit-vector representaties (waarbij overloop en modulo-reductie expliciet moeten worden gecontroleerd), gebruiken ze de algebraïsche structuur van de quotiëntring $\mathbb{Z}/q\mathbb{Z}$ .
Formalisatie: Ze definiëren de eigenschap "waarde-onafhankelijkheid" (value-independence) formeel. Als een draadfunctie $w$ onafhankelijk is van het geheim $x$ , dan moet de marginale verdeling van $w$ constant zijn, ongeacht de waarde van $x$ .
Bewijstechniek: Het bewijs maakt gebruik van de axioma's van commutatieve ringen (specifiek sub_add_cancel in Mathlib). Dit stelt hen in staat om algebraïsche identiteiten direct toe te passen in plaats van exhaustieve enumeratie.
Verificatie: Het volledige bewijs is "sorry-free" (geen onbewezen stellingen) en wordt volledig geverifieerd door de Lean-kernel, wat de trusted base minimaliseert tot de kern van de Lean-taal.

3. Belangrijkste Bijdragen

Het artikel presenteert de eerste machine-gecontroleerde universele bewijzen voor aritmische maskering in PQC-hardware. De bijdragen omvatten:

Universeel Hoofdbewijs (Theorema 4.1): Een bewijs dat geldt voor alle $q > 0$ $q > 0$ , alle draadfuncties $w: \mathbb{Z}_q \times \mathbb{Z}_q \to \beta$ $w : Z_{q} \times Z_{q} \to β$ , en alle geheimen. Het bewijst dat waarde-onafhankelijkheid impliceert dat de marginale verdeling constant is.
- Resultaat: Dit bewijs bestaat uit slechts vijf regels code in Lean 4, vergeleken met de 225 evaluaties die nodig waren voor de SMT-aanpak bij $q=5$ .
Ondersteunende Bewijssuite (T1–T6): Een verzameling van negen theorema's die de volgende aspecten dekken:
- T2 & T3: Bewijzen dat herschikking (reparametrization) van Boolese en aritmische maskering een round-trip is (bijv. $(x - s_1) + s_1 = x$ ) voor elke $q$ .
- T3': Bewijst dat deze herschikking een bijectie is, wat essentieel is voor de telling van histogrammen.
- T4: Bewijst dat er geen overloopproblemen zijn bij de conversie naar bit-vector implementaties (bridging theorema).
- T5: Kwantificeert de bias van Random Number Generators (RNG) en levert universele bovengrenzen voor ML-KEM en ML-DSA.
- T6: Levert een universeel tegenvoorbeeld dat laat zien dat de omgekeerde stelling niet geldt voor $q \ge 2$ (een constante verdeling garandeert niet automatisch waarde-onafhankelijkheid), wat de conservatieve aard van het QANARY-framework bevestigt.
Methodologisch Inzicht: De auteurs tonen aan dat ringtheorie de natuurlijke abstractielaag is voor verificatie van aritmische maskering, in plaats van SAT/SMT-oplossers die op bit-niveau werken.

4. Resultaten

Efficiëntie: Het kernbewijs (Theorema 4.1) vereist slechts 5 regels code in Lean 4, terwijl de vorige aanpak 225 evaluaties vereiste voor een enkel klein geval ( $q=5$ ).
Schaalbaarheid: Het bewijs is geldig voor elke modulus, inclusief de enorme waarden van ML-KEM ($3.329$) en ML-DSA ($8.380.417$), zonder dat de complexiteit toeneemt.
Vertrouwen: De trusted base is gereduceerd van {Z3, CVC5, Python} naar de Lean 4-kernel (een klein, formeel gespecificeerd C++-core).
Validatie: De volledige suite bestaat uit 1.739 build-taken, allemaal zonder fouten en zonder sorry-placeholders.
Tegenvoorbeeld: Het bewijs van T6 bevestigt dat de "INSECURE_CONSERVATIVE" labels die in eerdere werken werden gegenereerd, geen fouten in de tool waren, maar een inherent gevolg van de wiskundige beperkingen van het model voor elke $q \ge 2$ .

5. Betekenis en Impact

Certificering (FIPS 140-3): Dit werk biedt een universeel bewijs dat de beveiliging van PQC-hardware niet per parameter-set hoeft te worden herverifieerd. Een enkel bewijs dekt huidige en toekomstige NIST-standaarden. Dit verlaagt de last voor certificeringslaboratoria aanzienlijk.
Ontwerpportabiliteit: Als cryptografische parameters veranderen (bijv. een nieuwe $q$ als reactie op cryptanalytische doorbraken), blijft het bewijs geldig. De garantie van QANARY is nu automatisch overdraagbaar.
Paradigmaverschuiving: Het artikel demonstreert dat formele verificatie van hardware-maskering efficiënter en robuuster is wanneer deze wordt geformuleerd in algebraïsche termen (ringtheorie) in plaats van via logische enumeratie van bit-vectoren.
Toekomstige Richting: Dit werk vormt de basis voor Paper 4 in de serie, die de brug zal slaan tussen dit "r-vrije" bewijs en de volledige probabilistische beveiliging (inclusief frisse willekeurigheid).

Kortom, dit artikel sluit de methodologische kloof tussen theoretische beveiliging en praktische implementatie voor post-kwantumcryptografie door een wiskundig onderbouwde, universele garantie te bieden voor de beveiliging van hardware-maskering.