🔢 mathematics

Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes

Dit artikel presenteert een polynomial-time sleutelherstel-aanval die alle voorgestelde parametersets van het Enhanced Gabidulin Matrix Codes (EGMC) encryptieschema breekt door combinatorische en algebraïsche technieken te combineren om een equivalente geheime sleutel te herstellen, waardoor het geclaimde 128-bits beveiligingsniveau wordt teruggebracht tot slechts 35 bits.

Oorspronkelijke auteurs: Thai Hung Le

Gepubliceerd 2026-08-05

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Thai Hung Le

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 het internet voor als een enorme, bruisende stad waar iedereen probeert geheime berichten te versturen. Om deze berichten veilig te houden voor nieuwsgierige ogen, gebruiken we digitale sloten die cryptografie worden genoemd. Lange tijd hebben wetenschappers deze sloten gebouwd met behulp van complexe wiskundige puzzels die eenvoudig te maken zijn, maar ongelooflijk moeilijk op te lossen zonder de sleutel. Onlangs werd een nieuw type slot voorgesteld dat gebruikmaakt van een speciale vorm van wiskunde met behulp van rasters van getallen en "rang" (wat gewoon een chique manier is om te meten hoeveel informatie er daadwerkelijk in het raster gepakt zit). De makers van dit nieuwe slot dachten dat ze een laag "ruis" hadden toegevoegd—zoals statische elektriciteit op een radio—om de ware vorm van het slot te verbergen, waardoor het eruitzag als een willekeurige bende voor iedereen die probeerde in te breken. Ze beweerden dat dit nieuwe ontwerp zo veilig was dat zelfs een supersnelle quantumcomputer het niet zou kunnen kraken, en ze beloofden dat het klein en efficiënt zou zijn, perfect voor de toekomst van veilige communicatie.

Echter, net zoals een goochelaarstruc die vertrouwt op een specifieke handigheid, had dit nieuwe slot een verborgen gebrek. Een onderzoeker genaamd Thai Hung Le ontdekte dat de "ruis" de geheime vorm niet zo goed verborg als iedereen dacht. Door een slimme mix van gokken en algebraïsch detectivewerk te gebruiken, vond de onderzoeker een manier om de lagen van de statische ruis af te pellen en de oorspronkelijke, verborgen structuur eronder te onthullen. Het is alsof iemand een kaartenhuis heeft gebouwd met een geheim blauwdruk, bedekt met mist, en zich er vervolgens van realiseerde dat als je naar de mist vanuit de juiste hoek kijkt, de blauwdruk nog steeds vaag zichtbaar is. Deze ontdekking is een grote zaak omdat het betekent dat de nieuwe sloten niet zo veilig zijn als geadverteerd en dat de mensen die ze ontworpen hebben hun blauwdrukken moeten heroverwegen voordat ze ze gaan gebruiken om onze gegevens te beschermen.

De Grote Ontdekking van het Papier

In dit artikel presenteert Thai Hung Le een nieuwe manier om de "Enhanced Gabidulin Matrix Code" (EGMC) encryptieschema's te breken. Deze schema's werden recent geïntroduceerd als een manier om zeer kleine, efficiënte encryptiesleutels te creëren die bestand zouden zijn tegen aanvallen van toekomstige quantumcomputers. De beveiliging van deze schema's rustte op het idee dat als je een speciaal gestructureerd raster van getallen neemt en daar willekeurige rijen en kolommen aan toevoegt (de "ruis"), het onmogelijk wordt om het verschil te zien tussen de echte code en een volledig willekeurige bende.

De auteur laat zien dat deze aanname onjuist is. In plaats van te proberen elke mogelijke manier om de ruis te verwijderen door middel van brute force (wat eeuwen zou duren), introduceert het artikel een "hybride" aanval. Stel je voor dat je probeert een specifiek patroon te vinden in een gigantische, door elkaar gehusselde mozaïek. De oude manier was om de positie van elke individuele tegel te raden. Deze nieuwe methode is slimmer: de gebruiker raadt de positie van slechts één rij tegels, en gebruikt vervolgens wiskunde om direct te berekenen waar de rest van de tegels moet liggen.

Het artikel beschrijft twee hoofdmanieren om dit te doen:

Het raden van de kolommen: De aanvaller raadt hoe de kolommen van het raster zijn gehusseld en gebruikt vervolgens algebra om op te lossen hoe de rijen zijn gehusseld.
Het raden van de rijen: De aanvaller raadt hoe de rijen van het raster zijn gehusseld en lost vervolgens de kolommen op.

Zodra de aanvaller de gehusselde volgorde begrijpt, kan hij de willekeurige ruis verwijderen en de oorspronkelijke, verborgen structuur onthullen. Het artikel bewijst dat deze structuur een "Gabidulin-code" is, een type wiskundige puzzel die eigenlijk vrij eenvoudig op te lossen is zodra je het geheime patroon kent.

Wat het Papier Eigenlijk Breekt

De auteur vindt niet slechts een kleine barst; hij slaat het hele raam in. Het artikel demonstreert dat deze aanval werkt tegen alle 16 voorgestelde parametersets voor de EGMC-encryptieschema's. Dit betekent dat elke versie van het slot die voorgesteld is voor gebruik, nu als gebroken wordt beschouwd.

Om een gevoel te geven van de effectiviteit hiervan, kijkt het artikel naar een specifieke set getallen die bedoeld was om 128-bits beveiliging te bieden (een standaard niveau van veiligheid). De auteur laat zien dat deze aanval het beveiligingsniveau terugbrengt naar slechts 35 bits. In de wereld van cryptografie is dat alsof je van een kluis met een combinatie van een miljoen cijfers naar een slot gaat dat een kind in enkele seconden kan openen.

Het artikel geeft een concreet voorbeeld van deze kracht: met behulp van hun methode waren de onderzoekers in staat om de geheime sleutel van dat 128-bits beveiligingsniveau te herstellen in minder dan 10 minuten. Dit was niet alleen een theoretisch idee; ze hebben daadwerkelijk een computerprogramma gebouwd om het te doen.

Wat het Papier Uitsluit

Het is belangrijk op te merken wat dit artikel niet doet. De auteur legt uit dat eerdere pogingen om deze codes te breken vertrouwden op "combinatorische" methoden, waarbij zowel de rij- als de kolomhusseling tegelijkertijd wordt geraden. Het artikel betoogt dat deze oude manier te traag en inefficiënt is vergeleken met hun nieuwe "hybride" aanpak.

Bovendien voert het artikel aan dat de gedachte dat het simpelweg groter maken van de parameters (het toevoegen van meer ruis) het probleem voor alle gevallen zal oplossen, onjuist is. De auteur laat zien dat voor bepaalde typen van deze codes—specifiek wanneer een van de ruisfactoren (ofwel het aantal extra rijen of het aantal extra kolommen) nul is—de aanval zo snel wordt dat deze in "polynomiale tijd" verloopt. Dit betekent dat ongeacht hoe groot je het slot maakt in die specifieke gevallen, de aanval nog steeds snel genoeg zal zijn om het te breken. De enige manier om dit potentieel te repareren, suggereert het artikel, zou zijn om het fundamentele ontwerp te veranderen zodat beide ruisfactoren niet-nul zijn en groot genoeg zijn om de aanval te stoppen, maar de auteur waarschuwt dat dit de sleutels en berichten te groot en onbruikbaar zou maken.

Hoe Zeker Zijn Ze?

Het artikel is zeer zelfverzekerd over de resultaten. De auteur heeft niet alleen geraden; hij heeft een volledige wiskundige bewijsvoering geleverd van hoe de aanval werkt en dit ondersteund met een werkende computerimplementatie. Er wordt expliciet gesteld dat de aanval alle voorgestelde versies van het schema breekt. Ook vergelijkt de auteur de resultaten met eerdere aanvallen, waarbij wordt aangetoond dat hun methode aanzienlijk sneller en krachtiger is. Het artikel concludeert dat de EGMC-encryptieschema's niet langer veilig zijn voor gebruik en dat de cryptografische gemeenschap over moet stappen op andere ontwerpen.

Technische Samenvatting: Het breken van ACDGV MinRank Gabidulin-encryptieschema's over Matrix-codes

Probleemstelling
Het artikel behandelt de beveiliging van Enhanced Gabidulin Matrix Codes (EGMC), een maskeringstype dat door Aragon et al. bij Asiacrypt 2024 is geïntroduceerd. EGMC werd ontworpen om de algebraïsche structuur van Gabidulin-matrixcodes te verbergen, wat compacte McEliece- en Niederreiter-type encryptieschema's mogelijk maakt met kleine ciphertexts (bijv. 65 bytes voor 128-bits beveiliging). De beveiliging van EGMC rust op het Decisional EGMC-Indistinguishability probleem: de aanname dat een gemaskeerde EGMC-code computationeel ononderscheidbaar is van een willekeurige matrixcode. Eerdere cryptanalyse, specifiek een MinRank-gebaseerde kernel-aanval door Porwal et al. (Eurocrypt 2026), toonde exponentiële-tijd aanvallen aan die een deel van de voorgestelde parameter sets doorbraken, maar andere veilig lieten. De auteur onderzoekt of de EGMC-constructie voldoende verborgen structuur behoudt om efficiënter te worden gebroken.

Methodologie
De auteur stelt een nieuwe "hybride" distinguisher voor en een daaropvolgende sleutelherstelaanval die combinatorisch raden combineert met algebraïsch oplossen. In tegen tegenstelling tot eerdere distinguishers die zowel de rij- als kolomcompressiematrices via brute-force aanpakken, raadt deze aanval slechts één compressiematrix en lost de andere algebraïsch op.

De aanval werkt in twee primaire richtingen:

Guess- $V$ -solve- $U$ : De aanvaller raadt een kolomcompressiematrix $V$ en lost algebraïsch een rijcompressiematrix $U$ op.
Guess- $U$ -solve- $V$ : De aanvaller raadt een rijcompressiematrix $U$ en lost een kolomcompressiematrix $V$ op.

Algebraïsche Modellering en Oplossen
Zodra een geldige compressiematrix is geraden, wordt de publieke code gecomprimeerd naar een subruimte die equivalent is aan een korte Gabidulin-code (specifiek een $[k+1, k]$ code). De auteur modelleert de conditie dat deze gecomprimeerde code een $F_{q^m}$ -hypervlak moet zijn die wordt geannihileerd door een specifieke vector. Dit leidt tot een stelsel van bilineaire vergelijkingen die, na linearisatie, een homogeen lineair stelsel oplevert over de uitbreidingsring $F_{q^m}$ .

De kern van de aanval bestaat uit het vinden van een rank-1 oplossing binnen de kernel van dit lineaire stelsel. De auteur merkt op dat de kernel een basis toelaat met elementen in het grondlichaam $F_q$ . Bijgevolg reduceert het probleem zich tot het vinden van een lineaire combinatie van deze basismatrices die resulteert in een rank-1 matrix. Dit wordt geformuleerd als een stelsel van kwadratische vergelijkingen (het verdwijnen van $2 \times 2$ minors).

Om dit kwadratische stelsel efficiënt op te lossen, gebruikt de auteur de eigenwaardemethode (Stickelberger-eigenwaardemethode) voor zero-dimensionale polynoomstelsels. Ze maken gebruik van de Frobenius-stabiliteit van de kernel om berekeningen uit te voeren over het kleinere lichaam $F_q$ in plaats van $F_{q^m}$ , wat de complexiteit aanzienlijk vermindert. Een belangrijke conjectuur (Conjecture 1) stelt dat de quotientalgebra van het ideaal gegenereerd door de minors een dimensie heeft gelijk aan $m$ , wat garandeert dat het stelsel zero-dimensionaal en oplosbaar is via eigenwaarden.

Belangrijkste Bijdragen

Hybride Distinguisher: Het artikel introduceert een distinguisher die de volledige brute-force kosten van eerdere methoden vermijdt door één compressiematrix algebraïsch op te lossen.
Polynomial-Time Key Recovery: De auteur demonstreert dat als een van de bijgevoegde factoren $\ell_1$ of $\ell_2$ gelijk is aan nul, de aanval polynomiale tijd wordt. Dit komt omdat de exponentiële raden-factor verdwijnt, waardoor alleen de algebraïsche oplossingsstap overblijft, die de verborgen compressiematrix efficiënt herstelt.
Code Extensie: Na het herstellen van een gepuncteerde (korte) Gabidulin-code, biedt de auteur een polynomial-time algoritme om deze code uit te breiden naar een volledige, equivalente geheime Gabidulin-code door gebruik te maken van de $q$ -Frobenius structuur van Gabidulin-codes.
Universele Decryptie: De herstelde equivalente geheime sleutel (trapdoor) maakt decryptie mogelijk van zowel EGMC-McEliece als EGMC-Niederreiter ciphertexts.

Resultaten
De aanval breekt alle 16 voorgestelde parameter sets voor EGMC-Niederreiter encryptieschema's.

Beveiligingsreductie: Voor de parameter set die gericht is op 128-bits beveiliging met parameters $(2, 17, 37, 4, 0)$ , reduceert de aanval het beveiligingsniveau van de geclaimde 186 bits naar ongeveer 35 bits.
Efficiëntie: In de implementatie van de auteur wordt de equivalente geheime sleutel voor de 128-bits parameter set in minder dan 10 minuten hersteld.
Vergelijking: De aanval presteert aanzienlijk beter dan eerdere beste aanvallen (combinatorisch en MinRank-gebaseerd), zoals weergegeven in Tabel 1 van het artikel.

Betekenis en Claims
Het artikel claimt dat de EGMC-constructie, zoals voorgesteld, geen post-quantum beveiliging biedt voor de specifieke parameterfamilies waar $\ell_1 = 0$ of $\ell_2 = 0$ . De auteur voert aan dat het simpelweg verhogen van parameters zonder de maskering-constructie te wijzigen de beveiliging niet herstelt, aangezien de algebraïsche oplossingsstap polynomiale tijd blijft.

De auteur merkt op dat een potentiële reparatie vereist dat zowel $\ell_1$ als $\ell_2$ groter dan nul zijn en voldoende groot zijn om te garanderen dat het minimum van de twee aanvalsrichtingen boven het beoogde beveiligingsniveau ligt. De auteur waarschuwt echter dat het direct verhogen van deze parameters de omvang van de publieke sleutel en de ciphertext direct vergroot, en dat het nog onderzocht moet worden of een dergelijke reparatie concurrerend blijft met andere code-gebaseerde schema's. Het artikel concludeert dat de huidige EGMC-parameters onveilig zijn en dat de voorgestelde aanval zowel een distinguisher als een volledig sleutelherstelmechanisme biedt.

De Grote Ontdekking van het Papier

Wat het Papier Eigenlijk Breekt

Wat het Papier Uitsluit

Hoe Zeker Zijn Ze?

Meer zoals dit