🔢 mathematics

On the Direct Construction of MDS and Near-MDS Matrices

Dit artikel introduceert directe constructiemethoden voor zowel niet-recursieve als recursieve Near-MDS-matrices, evenals voor niet-recursieve en involutorische MDS-matrices op basis van gegeneraliseerde Vandermonde-matrices, en bewijst enkele folklore-resultaten gerelateerd aan NMDS-codes.

Oorspronkelijke auteurs: Kishan Chand Gupta, Sumit Kumar Pandey, Susanta Samanta

Gepubliceerd 2026-04-10

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Kishan Chand Gupta, Sumit Kumar Pandey, Susanta Samanta

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 heel veilig huis wilt bouwen. In de wereld van digitale beveiliging (zoals bij bankapps of WhatsApp) is dit huis een versleuteling. Om ervoor te zorgen dat niemand je boodschap kan kraken, heb je twee belangrijke bouwstenen nodig:

Verwarring (Confusion): Het maakt de relatie tussen de sleutel en de code ondoorzichtig.
Verspreiding (Diffusion): Dit is waar dit artikel over gaat. Het zorgt ervoor dat als je één klein stukje van de boodschap verandert, dat effect zich als een rimpel in een vijver verspreidt over heel de boodschap. Als één letter verandert, moeten alle andere letters er ook anders uitzien.

In de wiskunde worden deze "verspreiders" gemaakt met speciale matrijzen (een soort rekentabellen). De beste verspreiders heten MDS-matrices. Ze zijn perfect, maar soms ook zwaar en traag om te berekenen, vooral op kleine apparaten zoals een slimme horloge of een sensor in een boerderij.

Soms is een "bijna-perfecte" verspreider, een NMDS-matrix, juist beter. Hij is iets minder krachtig in het verspreiden, maar veel lichter en sneller. Voor kleine apparaten is dit vaak de perfecte balans tussen veiligheid en snelheid.

Het Probleem: De Bouwtekening ontbreekt

Tot nu toe hadden ingenieurs twee manieren om deze matrijzen te bouwen:

Zoeken: Ze probeerden miljoenen willekeurige combinaties uit tot ze een goede vonden. Dit werkt goed voor kleine matrijzen, maar is onmogelijk voor grote, complexe systemen. Het is alsof je probeert een sleutel te vinden door elke sleutel op aarde één voor één te proberen.
Direct bouwen: Ze gebruikten vaste formules. Dit werkt goed voor de perfecte MDS-matrices, maar voor de "bijna-perfecte" NMDS-matrices (vooral de snelle, recursieve varianten) bestond er geen enkele bouwtekening. Het was alsof je wist dat het huis er moest zijn, maar je had geen blauwdruk om het te bouwen.

De Oplossing: Nieuwe Wiskundige Gereedschappen

De auteurs van dit artikel hebben nieuwe "gereedschappen" ontwikkeld om deze matrijzen direct te bouwen, zonder te hoeven zoeken. Ze gebruiken een wiskundig concept dat lijkt op een Vandermonde-matrix.

Om dit te begrijpen, gebruik ik een analogie:

De Standaard Matrijs (De Gewone Muur): Stel je een muur voor die je bouwt met bakstenen in een vast patroon (1, 2, 3, 4...). Dit is een standaard Vandermonde-matrix. Hij is sterk, maar als je één steen verwijdert, kan de hele muur instorten (hij is niet altijd veilig genoeg).
De Verbeterde Matrijs (De Geavanceerde Muur): De auteurs gebruiken een gegeneraliseerde Vandermonde-matrix. Dit is alsof je niet alleen bakstenen gebruikt, maar ook speciale mortel en een ander patroon. Je kunt bepaalde bakstenen (getallen) weglaten of vervangen door andere patronen. Hierdoor kun je de muur zo bouwen dat hij precies de sterkte heeft die je nodig hebt: soms perfect (MDS), soms "bijna perfect" maar veel lichter (NMDS).

De Drie Grote Doorbraken

Het artikel presenteert drie belangrijke nieuwe manieren om deze matrijzen te bouwen:

De "Recurserende" NMDS-matrix (De Opstap-methode):
- Het idee: In plaats van een hele grote, zware machine te bouwen, bouw je een kleine, simpele machine die je herhaaldelijk gebruikt.
- De analogie: Stel je voor dat je een trap bouwt. In plaats van een enorme lift (zware MDS) te maken, bouw je een simpele trap (een kleine matrix) en loop je er een paar keer overheen (herhaling). De auteurs hebben nu de eerste blauwdruk gevonden om deze "trappen" te bouwen die veilig genoeg zijn voor lichte apparaten, maar die voorheen onmogelijk te vinden waren.
De "Spiegelende" Matrijzen (Involutory):
- Het idee: In cryptografie moet je vaak versleutelen én ontsleutelen. Als de matrijs die je gebruikt om te versleutelen precies hetzelfde is als die voor ontsleutelen, bespaar je enorm veel ruimte en energie. Dit heet een "involutory" matrijs.
- De analogie: Stel je een spiegel voor. Wat je erin ziet, is het omgekeerde, maar de spiegel zelf is hetzelfde object. De auteurs hebben een formule gevonden om deze "spiegel-matrijzen" te bouwen die zowel versleutelen als ontsleutelen, en dat voor zowel de perfecte als de "bijna-perfecte" varianten. Dit is een wereldprimeur voor de NMDS-variant.
De "Twee-Spiegel" Methode:
- Om deze matrijzen te maken, gebruiken ze twee sets van hun speciale "gegeneraliseerde bakstenen" (Vandermonde-matrices) en combineren ze deze op een slimme manier. Het is alsof je twee verschillende patronen van tegels neemt en ze zo tegen elkaar aan legt dat ze een perfect, veilig mozaïek vormen.

Waarom is dit belangrijk?

Voor de gemiddelde gebruiker betekent dit dat in de toekomst:

Veiligere apparaten: Je slimme horloge, je thermostaat of je auto kan versleuteling gebruiken die net zo veilig is als die van je bank, maar dan zonder dat de batterij direct leeg is.
Snellere beveiliging: Omdat deze matrijzen direct "gebouwd" kunnen worden in plaats van gezocht, kunnen ze sneller worden ingebouwd in nieuwe technologieën.
Flexibiliteit: De auteurs hebben laten zien dat je de "sterkte" van de beveiliging kunt afstellen. Wil je maximale veiligheid? Gebruik de MDS-methode. Wil je maximale snelheid op een klein apparaat? Gebruik de nieuwe NMDS-methode.

Kortom: De auteurs hebben de "lege plekken" in de bouwtekening voor digitale beveiliging opgevuld. Ze hebben bewezen dat je niet alleen de perfecte muren kunt bouwen, maar ook slimme, lichte muren die net zo goed werken, en ze hebben de formules geschreven zodat ingenieurs deze nu direct kunnen gebruiken.

Titel: Over de Directe Constructie van MDS- en Near-MDS-matrices

Auteurs: Kishan Chand Gupta, Sumit Kumar Pandey en Susanta Samanta.

1. Probleemstelling

In de cryptografie, met name bij het ontwerp van blokcijfers en hash-functies, zijn diffusie-lagen cruciaal om interne afhankelijkheden te verspreiden. De meest gewenste eigenschap voor deze lagen is het gebruik van Maximum Distance Separable (MDS) matrices, vanwege hun optimale vertakkingsgetal (branch number), wat maximale diffusie garandeert.

Er zijn echter twee belangrijke uitdagingen:

Zoekruimte en Schaalbaarheid: Hoewel exhaustieve zoekmethodes werken voor kleine matrices, worden ze onhaalbaar voor grotere maten of grote eindige velden. Directe constructiemethoden zijn daarom nodig, maar bestaande methoden zijn vaak beperkt tot specifieke klassen (zoals Cauchy-matrices) of leveren niet altijd de laagste implementatiekosten.
Lightweight Cryptografie en NMDS: Voor lichtgewicht toepassingen (waar energie en hardware-ruimte beperkt zijn) zijn MDS-matrices soms te zwaar. Near-MDS (NMDS) matrices bieden een suboptimale, maar acceptabele diffusie met een betere balans tussen beveiliging en efficiëntie.
- Het Gaten: Hoewel er veel onderzoek is gedaan naar de directe constructie van MDS-matrices (zowel recursief als niet-recursief), ontbreekt er in de literatuur een directe constructiemethode voor recursieve NMDS-matrices. Daarnaast zijn er beperkte methoden voor het direct construeren van involutorische (hun eigen inverse zijn) NMDS-matrices.

2. Methodologie

De auteurs gebruiken geavanceerde algebraïsche structuren uit de coderingstheorie en lineaire algebra om nieuwe constructiemethoden te ontwikkelen. De kern van hun aanpak rust op de volgende concepten:

Generalized Vandermonde Matrices ( $V^\perp(x; I)$ ): In plaats van standaard Vandermonde-matrices, gebruiken de auteurs een gevarieerde vorm waarbij een verzameling $I$ van exponenten wordt weggelaten. De determinant van deze matrices wordt uitgedrukt in termen van elementaire symmetrische polynomen en de standaard Vandermonde-determinant.
Companion Matrices: Voor recursieve constructies gebruiken ze companion matrices geassocieerd met monische polynomen. Een matrix $B$ is recursief MDS/NMDS als $B^m$ (voor een bepaalde $m$ ) de gewenste eigenschappen heeft.
Lineaire Codes: De constructies worden gefundeerd op de relatie tussen generator- en pariteitscheck-matrices van $[2n, n]$ codes. Een matrix $A$ is MDS (resp. NMDS) als $[I | A]$ een generatormatrix is van een MDS (resp. NMDS) code.
Algebraïsche Voorwaarden: De auteurs leiden strikte voorwaarden af voor de elementen van de matrices (zoals sommen van machten van veld-elementen) die moeten worden voldaan om de vereiste rang- en lineariteitsafhankelijkheidseigenschappen te garanderen.

3. Belangrijkste Bijdragen

Het artikel introduceert vier hoofdbijdragen die de staat van de kunst uitbreiden:

Directe Constructie van Recursieve NMDS-matrices:
- Dit is een noviteit, aangezien er hiervoor geen directe methoden bestonden.
- De auteurs stellen methoden voor op basis van companion matrices. Ze tonen aan dat door de wortels ( $\lambda_i$ ) van het bijbehorende polynoom zorgvuldig te kiezen (bijvoorbeeld door te voldoen aan $\sum \theta^{r_i} = 0$ voor specifieke indexsets), men matrices kan construeren die voldoen aan de NMDS-criteria.
- Ze presenteren ook een nieuwe directe constructie voor recursieve MDS-matrices via companion matrices.
Constructie via Generalized Vandermonde Matrices (Niet-Recursief):
- De auteurs gebruiken geavanceerde eigenschappen van $V^\perp(x; I)$ met specifieke verzamelingen $I$ (zoals $\{1\}$ , $\{n-1\}$ , en $\{1, n\}$ ) om niet-recursieve MDS- en NMDS-matrices te construeren.
- Ze bewijzen dat door twee dergelijke matrices ( $V_1$ en $V_2$ ) te combineren (bijv. via $V_1^{-1}V_2$ ), men matrices kan verkrijgen waarvan elke vierkante submatrix niet-singulier is (MDS) of voldoet aan de NMDS-rangvoorwaarden.
Constructie van Involutorische MDS- en NMDS-matrices:
- Involutorische matrices ( $M = M^{-1}$ ) zijn zeer gewenst in cryptografie omdat ze de implementatiekosten voor encryptie en decryptie halveren.
- De auteurs presenteren de eerste directe constructie voor involutorische NMDS-matrices over eindige velden.
- Ze tonen aan hoe men door een symmetrische algebraïsche relatie tussen de elementen van twee generalized Vandermonde matrices te leggen (bijv. $x_{n+i} = l + x_i$ in velden met karakteristiek 2), involutorische matrices kan genereren.
Formele Bewijzen van "Folklore"-resultaten:
- Het artikel biedt formele wiskundige bewijzen voor diverse resultaten over NMDS-codes die in de literatuur vaak als bekend worden verondersteld maar niet altijd strikt bewezen zijn (bijvoorbeeld de relatie tussen de rang van kolommen van de pariteitscheck-matrix en de gegeneraliseerde Hamming-gewichten).

4. Resultaten

Theoretische Validatie: De auteurs hebben bewezen dat hun constructies voldoen aan de strikte definitie van MDS en NMDS codes door gebruik te maken van de eigenschappen van gegeneraliseerde Vandermonde-determinanten en lineaire onafhankelijkheid.
Concrete Voorbeelden: Er worden concrete voorbeelden gegeven over velden zoals $\mathbb{F}_{2^4}$ en $\mathbb{F}_{2^8}$ die aantonen dat de methoden praktisch toepasbaar zijn. Deze voorbeelden genereren succesvol $4 \times 4$ en $6 \times 6$ matrices die voldoen aan de NMDS- en MDS-eisen.
Vergelijking met Bestaande Literatuur: Een tabel in het artikel (Tabel 1) illustreert dat de voorgestelde methoden de enige directe constructies zijn voor:
- Recursieve NMDS-matrices.
- Involutorische NMDS-matrices.
- Recursieve MDS-matrices via companion matrices (als alternatief voor bestaande coderingstheorie-methoden).

5. Betekenis en Toekomstperspectief

De betekenis van dit werk ligt in het vullen van een belangrijke kennislacune in de cryptografische ontwerptheorie:

Lightweight Cryptografie: Het biedt ontwerpers nieuwe, efficiënte opties voor diffusie-lagen die lichter zijn dan traditionele MDS-matrices, maar toch voldoende beveiliging bieden.
Theoretische Uitbreiding: Het introduceert een nieuw algebraïsch raamwerk (gebaseerd op gegeneraliseerde Vandermonde-matrices en symmetrische polynomen) dat losstaat van de traditionele Cauchy- en standaard Vandermonde-benaderingen.
Implementatie: Hoewel de huidige constructies niet altijd de absolute laagste hardwarekosten garanderen (wat vaak via zoekmethodes wordt bereikt), bieden ze een schaalbare en theoretisch onderbouwde route voor grotere matrices.

Toekomstig werk: De auteurs suggereren dat de volgende stap het toepassen van globale optimalisatie-heuristieken op deze nieuw ontdekte matrixklassen zal zijn om concrete implementatiemetrieken (zoals gate-count en latentie) te evalueren voor de integratie in lichtgewicht cryptografische primitieven.