Dependency-Aware ROM/CBD Correctness Bounds for ML-KEM-768 at the Heuristic Failure Scale

In de digitale wereld rust beveiliging vaak op wiskundige problemen die gemakkelijk in de ene richting te gebruiken zijn, maar extreem moeilijk om te keren zonder de juiste geheime informatie. ML-KEM is een post-kwantum sleutelopbouwsysteem dat is ontworpen om veilig te blijven, zelfs tegen toekomstige kwantumcomputers. Net als andere op roosters (lattices) gebaseerde cryptografische systemen, heeft het een extreem kleine waarschijnlijkheid van wat een 'honest decapsulation failure' wordt genoemd: zelfs wanneer beide partijen zich correct gedragen, zouden de twee zijden in principe verschillende sleutels kunnen afleiden. Het schatten hoe zelden dit kan gebeuren, is een belangrijke vraag over de correctheid. Eerdere analyses hebben grotendeels vertrouwd op heuristische schattingen van de foutschaal, terwijl het verkrijgen van een rigoureuze bovengrens die de relevante wiskundige afhankelijkheden tussen de verschillende fouttermen behoudt, aanzienlijk moeilijker is.

Een nieuwe studie door Aurélie Duriez en Christophe Tommasini pakt dit probleem aan door een rigoureuze wiskundige analyse van ML-KEM-768 te ontwikkelen binnen een expliciete geïdealiseerde random-function / centered-binomial, of ROM/CBD, abstractie. Het werk is geen simulatie en probeert niet het exacte foutpercentage te berekenen. In plaats daarvan leiden de auteurs een gecertificeerde bovengrens af voor de waarschijnlijkheid van een 'honest decapsulation failure', waarbij de belangrijke afhankelijkheden tussen de verschillende fouttermen behouden blijven. In het bijzonder houdt de analyse rekening met de afhankelijkheden die worden veroorzaakt door de publieke matrix en door beide ciphertext-compressietermen, in plaats van ze simpelweg als onafhankelijk te behandelen. De resulterende gecertificeerde bovengrens is kleiner dan één op 2 tot de macht 164,81.

Dit bevinding is significant omdat het een heuristische schatting van de foutschaal, binnen het bestudeerde expliciete model, vervangt door een afhankelijkheidsbewuste gecertificeerde bovengrens. De analyse neemt niet simpelweg aan dat de relevante fouten onafhankelijk zijn; het behoudt de wiskundige afhankelijkheden die er tussen ontstaan. De gecertificeerde bovengrens bereikt nagenoeg dezelfde schaal als eerdere heuristische schattingen, maar dit moet niet worden geïnterpreteerd als een bewijs dat die schattingen de exacte foutwaarschijnlijkheid zijn. Het resultaat is doelbewust nauwer: binnen de in het artikel bestudeerde expliciete ROM/CBD-abstractie is de waarschijnlijkheid van een 'honest decapsulation failure' rigoureus begrensd aan de bovenzijde door een extreem kleine waarde. Het artikel maakt ook duidelijk dat dit geen exact decapsulation-foutpercentage is en geen informatie-theoretische uitspraak is over de vaste SHAKE-instantie van FIPS 203.

Het werk vereiste een andere manier van het probleem benaderen. Vereenvoudigde heuristische analyses kunnen veel gemakkelijker worden als sommige fouttermen als onafhankelijk worden behandeld, maar de werkelijke algebraïsche structuur creëert afhankelijkheden die een rigoureuze analyse moet behouden. De auteurs ontwikkelden daarom een methode die deze afhankelijkheden door de berekening volgt in plaats van ze weg te laten. Het onderzoeksproces maakte ook gebruik van een AI-ondersteunde methodologie om mogelijke benaderingen te verkennen, kritieke gevallen te identificeren en de analyse te structureren. Dit verkennende gebruik van AI werd gecombineerd met uitputtende computer-geverifieerde controles, exacte of gecertificeerde rekenkunde en onafhankelijk controleerbare berekeningen om de moeilijkste delen van het argument te sluiten. De uiteindelijke wiskundige claims rusten daarom op expliciet, reproduceerbaar bewijs in plaats van op de AI-output zelf.

Het resultaat is een rigoureuze en transparante gecertificeerde correctheidsgrens binnen de gestelde abstractie. De onderzoekers hebben hun code, gegevens en ondersteunende artefacten beschikbaar gesteld, zodat de berekeningen onafhankelijk kunnen worden gecontroleerd. Dit niveau van reproduceerbaarheid is bijzonder belangrijk in de cryptografie, waar wiskundige claims open moeten staan voor onafhankelijke verificatie. De studie toont aan dat, binnen de expliciet overwogen ROM/CBD-abstractie, de waarschijnlijkheid van een 'honest decapsulation failure' begrensd is op een extreem laag niveau. Het moet echter niet worden geïnterpreteerd als een algemeen veiligheidscertificaat voor ML-KEM-768, als een bewijs van alle beveiligingseigenschappen van het gestandaardiseerde schema, of als een verklaring die elke hardware- of software-implementatie omvat.

Dit resultaat draagt bij aan het rigoureuze begrip van één specifiek aspect van de correctheid van ML-KEM-768 door over te stappen van een heuristische schatting van de foutschaal naar een afhankelijkheidsbewuste gecertificeerde bovengrens binnen een duidelijk gedefinieerde abstractie. Het laat zien dat een bovengrens op de heuristische schaal kan worden vastgesteld terwijl de belangrijke afhankelijkheden tussen de relevante fouttermen behouden blijven. Het getal 164,81 is de gecertificeerde exponent van deze bovengrens: binnen de gestelde ROM/CBD-abstractie is de waarschijnlijkheid van een 'honest-decapsulation failure' begrensd aan de bovenzijde door 2 tot de macht -164,81. Dit getal moet daarom worden begrepen als een precieze eigenschap van de in het artikel bewezen gecertificeerde bovengrens, in plaats van als een algemene maat voor de veiligheid of beveiliging van ML-KEM-768 als geheel.

De onderzoekers hebben ook zorg gedragen voor een uitleg van de beperkingen van hun werk. Ze merkten op dat hun bewijs van toepassing is op een specifieke abstractie van het systeem, en niet noodzakelijkerwijs op elke mogelijke implementatie van de software. Ze beweerden niet het probleem voor alle variaties van de encryptiestandaard te hebben opgelost, noch suggereerden ze dat het systeem immuun is voor alle soorten aanvallen. Hun focus lag strikt op de correctheid van het decryptieproces onder eerlijke omstandigheden. Door duidelijk te zijn over wat ze wel en niet bewezen hebben, hebben ze ervoor gezorgd dat hun bevindingen niet verkeerd worden geïnterpreteerd. De studie staat als een testament voor de kracht van zorgvuldige, gedetailleerde analyse in een veld waar kleine fouten enorme gevolgen kunnen hebben. Het laat zien dat met voldoende rigor en de juiste instrumenten zelfs de meest complexe wiskundige systemen begrepen en geverifieerd kunnen worden.

Uiteindelijk levert het artikel een precies maar doelbewust afgebakend resultaat: binnen de gestelde ROM/CBD-abstractie is de waarschijnlijkheid van een 'honest-decapsulation failure' rigoureus begrensd aan de bovenzijde door 2 tot de macht -164,81. Dit is een extreem kleine gecertificeerde bovengrens, maar het is geen exact foutpercentage en het is geen algemeen bewijs dat het volledige ingezette ML-KEM-768-systeem zonder fouten werkt onder alle realistische omstandigheden. De bijdrage ligt in het vervangen van een heuristische schatting van de foutschaal door een afhankelijkheidsbewuste, reproduceerbare en onafhankelijk controleerbare bovengrens binnen een duidelijk gedefinieerd model. De kracht ervan komt niet voort uit het claimen van zekerheid buiten dat model, maar uit het expliciet zijn over zowel wat er is bewezen als wat buiten de reikwijdte van het resultaat valt.