New Insights into Involutory and Orthogonal MDS Matrices

Sintesi Tecnica: Nuove Prospettive sulle Matrici MDS Involutorie e Ortogonali

Definizione del Problema
Le matrici Maximum Distance Separable (MDS) sono fondamentali per gli strati di diffusione dei cifrari a blocchi e delle funzioni di hash grazie ai loro ottimali numeri di ramo. Sebbene esista una letteratura significativa sulla costruzione di candidati MDS efficienti, specifiche proprietà strutturali — ovvero involutorie (auto-inverse) e ortogonali (trasposta-inversa) — sono altamente desiderabili per ridurre i costi di implementazione, permettendo l'uso di circuiti identici o quasi identici per cifratura e decifratura. Recentemente, questi concetti sono stati generalizzati in matrici "semi-involutorie" e "semi-ortogonali". Tuttavia, la ricerca esistente si è concentrata ampiamente sulla proposta di nuove costruzioni o sull'ottimizzazione di metriche di implementazione. Vi è una mancanza di comprensione sistematica riguardo alle interconnessioni strutturali tra queste varianti generalizzate (semi-involutoria/semi-ortogonale) e i loro corrispettivi convenzionali (involutoria/ortogonale), in particolare per quanto riguarda la loro enumerazione su campi finiti $\mathbb{F}_{2^m}$.

Metodologia
Gli autori adottano un approccio di analisi strutturale piuttosto che proporre nuove costruzioni di matrici. La metodologia centrale si basa sulla decomposizione unica delle matrici non singolari su $\mathbb{F}_{2^m}^*$ nella forma $M = D_1 M_1 D_2$, dove $D_1$ e $D_2$ sono matrici diagonali non singolari e $M_1$ è una "matrice rappresentativa" con una specifica forma canonica (prima riga e colonna composte da uno).

Le fasi metodologiche chiave includono:

1. Stabilire le Interconnessioni: Il documento dimostra che le proprietà di essere involutoria, semi-involutoria, ortogonale o semi-ortogonale sono preservate o trasformate in modi prevedibili applicando la scalatura diagonale $D_1 M_1 D_2$.
2. Derivare Relazioni di Conteggio: Analizzando i vincoli su $D_1$ e $D_2$ necessari affinché una matrice $M$ soddisfi specifiche proprietà, gli autori derivano relazioni bidirezionali tra il conteggio delle matrici generalizzate e quello dei loro corrispettivi convenzionali.
3. Caratterizzazione Strutturale: Gli autori derivano la struttura algebrica generale delle matrici ortogonali di ordine arbitrario $n$ su $\mathbb{F}_{2^m}$ e specializzano questo risultato per $n=3$ e $n=4$.
4. Enumerazione: Utilizzando i risultati di enumerazione noti per le matrici MDS involutorie e le relazioni strutturali derivate, gli autori calcolano il numero esatto di matrici MDS semi-involutorie e semi-ortogonali per ordini e dimensioni di campo specifici.

Contributi Chiave e Risultati

• Interconnessioni Strutturali: Il documento stabilisce relazioni non banali tra matrici semi-involutorie e involutorie, e tra matrici semi-ortogonali e ortogonali. Nello specifico, si dimostra che il numero di matrici MDS involutorie $n \times n$ è $(2^m - 1)^{n-1}$ volte il numero di matrici MDS semi-involutorie della forma $M_1$. Una simile corrispondenza è provata per le matrici semi-ortogonali e ortogonali.
• Enumerazione di Matrici 3×3:
  • MDS Ortogonali: Gli autori derivano una formula esplicita per il numero di matrici MDS ortogonali $3 \times 3$ su $\mathbb{F}_{2^m}$ come $(2^m - 2)(2^m - 3)(2^m - 4)$.
  • MDS Semi-Ortogonali: Sfruttando il legame strutturale, derivano il conteggio per le matrici MDS semi-ortogonali $3 \times 3$ come $(2^m - 1)^5(2^m - 2)(2^m - 3)(2^m - 4)$.
  • MDS Semi-Involutorie: Il documento fornisce una derivazione diretta per il conteggio delle matrici MDS semi-involutorie $3 \times 3$, confermando la formula $(2^m - 1)^5(2^m - 2)(2^m - 4)$. Ciò funge da alternativa alle precedenti prove trovate in letteratura.
• Intersezione di Proprietà: Gli autori caratterizzano le matrici che sono sia semi-involutorie che semi-ortogonali. Dimostrano che per le matrici $3 \times 3$, qualsiasi matrice semi-involutoria della forma $M_1$ è necessariamente simmetrica, il che implica che il conteggio delle matrici che possiedono entrambe le proprietà è identico al conteggio delle matrici semi-involutorie.
• Enumerazione di Matrici 4×4: Lo studio si estende alle matrici $4 \times 4$. Gli autori calcolano il numero di matrici MDS semi-involutorie per $m = 3, \dots, 8$ e le matrici ortogonali/semi-ortogonali per $m=3, 4$. Identificano inoltre matrici MDS ortogonali "lightweight" di ordine 4 basate sui conteggi delle porte d-XOR, trovando conteggi ottimali di 64 su $\mathbb{F}_{2^3}$ e 72 su $\mathbb{F}_{2^4}$.
• Struttura Generale: Viene derivata una forma generale per le matrici ortogonali $n \times n$ su $\mathbb{F}_{2^m}$, esprimendo l'ultima riga e l'ultima colonna in termini degli elementi della sotto-matrice rimanente e di specifici vincoli di sommatoria.

Significato e Rivendicazioni
Il documento sostiene di fornire un quadro unificato per comprendere l'enumerazione delle matrici MDS con specifici vincoli strutturali. Spostando l'attenzione dalla costruzione alla relazione strutturale, gli autori dimostrano che i conteggi delle varianti generalizzate (semi-involutoria/semi-ortogonale) possono essere derivati direttamente dai conteggi dei loro corrispettivi convenzionali.

Gli autori affermano che il loro lavoro offre:

1. Derivazioni Alternative: Una derivazione più diretta e concisa per le formule di conteggio delle matrici MDS semi-involutorie e semi-ortogonali $3 \times 3$ rispetto alle prove complete esistenti.
2. Nuovi Dati di Enumerazione: Conteggi espliciti per le matrici MDS ortogonali $3 \times 3$ (precedentemente non stabiliti in letteratura) e conteggi estesi per le matrici $4 \times 4$ su campi finiti più grandi.
3. Approfondimento Teorico: Una prova del fatto che per le matrici $3 \times 3$, l'intersezione delle proprietà semi-involutoria e semi-ortogonale coincide con l'insieme delle matrici semi-involutorie, una proprietà che non si verifica necessariamente per ordini superiori (ad esempio, $n \ge 4$).

Il documento conclude che queste interconnessioni forniscono un metodo sistematico per determinare il numero di matrici MDS che soddisfano ulteriori vincoli strutturali, consolidando le formule di enumerazione esplicite per diverse classi di matrici MDS $3 \times 3$ e $4 \times 4$ con vincoli algebrici.