Utilizing Circulant Structure to Optimize the Implementations of Linear Layers

Sintesi Tecnica: Sfruttamento della Struttura Circolante per Ottimizzare le Implementazioni dei Livelli Lineari

Enunciazione del Problema
L'ottimizzazione dei livelli lineari nella crittografia simmetrica è fondamentale sia per le implementazioni leggere (vincolate dal numero di porte e dall'area) sia per le valutazioni della sicurezza quantistica (vincolate dalla profondità del circuito e dal costo DW). Sebbene esistano algoritmi euristici per la sintesi di circuiti CNOT (quantistici) e circuiti XOR (classici) per matrici invertibili generali, essi spesso non riescono a sfruttare appieno le strutture algebriche specifiche intrinseche ai progetti crittografici. Molte matrici ampiamente utilizzate, come quelle in MixColumn di AES e Whirlwind, possiedono una struttura circolante. I metodi esistenti all'avanguardia, come quelli di Shi e Feng [SF24], trattano queste matrici come matrici binarie generiche $n \times n$, rischiando di perdere opportunità di ridurre la profondità del circuito e il numero di porte sfruttando le loro proprietà circolanti sottostanti.

Metodologia
Gli autori propongono un nuovo framework che sfrutta esplicitamente la struttura circolante delle matrici per guidare la sintesi di circuiti efficienti. La metodologia di base prevede una strategia di decomposizione ricorsiva che trasforma una matrice circolante su un'estensione di campo (ad esempio $F_{2^k}$ o $GL(F_2, m)$) in una forma più semplice, specificamente una matrice triangolare superiore, prima di applicare l'ottimizzazione euristica standard.

I componenti tecnici chiave includono:

1. Trasformazione Ricorsiva a Blocchi: Il Teorema 3 stabilisce che una matrice circolante $2^k \times 2^k$ su $F_2[x]$ può essere trasformata in una matrice triangolare superiore a blocchi utilizzando operazioni elementari su righe e colonne. L'algoritmo divide ricorsivamente la matrice in blocchi $A$ e $B$ (dove $M = \begin{smallmatrix} A & B \\ B & A \end{smallmatrix}$), applicando operazioni per azzerare blocchi specifici (ad esempio, trasformando in $\begin{smallmatrix} A+B & B \\ A+B & \dots \end{smallmatrix}$).
2. Esplorazione dei Percorsi di Trasformazione: Gli autori osservano che diverse scelte di operazioni su righe e colonne durante il passo ricorsivo portano a matrici intermedie diverse. L'algoritmo (Algoritmo 1) esplora molteplici percorsi di trasformazione (fino a $4^{2^k-1}$ possibilità per piccoli $k$) per trovare il percorso che produce il circuito successivo più efficiente.
3. Arresto Anticipato e Fallback: Riconoscendo che il beneficio della ricorsione diminuisce a profondità maggiori, gli autori introducono una strategia (Algoritmo 2) per arrestare la ricorsione anticipatamente. L'algoritmo itera attraverso diverse "dimensioni di blocco", variando efficacemente la profondità di ricorsione. Se la ricorsione viene arrestata anticipatamente, la matrice risultante viene passata a un ottimizzatore euristico standard (Heu) per la sintesi generale di CNOT/XOR. Ciò include una strategia di "fallback" in cui la profondità di ricorsione è zero, trattando efficacemente la matrice come un caso generale.
4. Ottimizzazione Automatizzata: A differenza dei precedenti approcci manuali (ad esempio Zhang et al. [ZSWS24] per AES), questo metodo automatizza il processo di ricerca della forma di matrice "più semplice" e delle corrispondenti sequenze di porte, eliminando la necessità di intervento umano.

Contributi Chiave

• Nuovo Framework: Questo è il primo lavoro a sfruttare sistematicamente la struttura circolante dei livelli lineari per ottimizzare le implementazioni dei circuiti, colmando il divario tra le proprietà algebriche delle matrici e le euristiche di sintesi dei circuiti.
• Sintesi Automatizzata: Gli autori forniscono un algoritmo automatizzato che sostituisce le ottimizzazioni manuali specifiche per caso. Genera sequenze di matrici di trasformazione che permettono alle euristiche a valle di trovare implementazioni più efficienti.
• Ottimizzazione Duale: Il framework è applicabile sia ai circuiti quantistici (minimizzando il numero e la profondità dei CNOT) sia ai circuiti classici (minimizzando i conteggi XOR, in particolare g-XOR e s-XOR).

Risultati
Gli autori hanno valutato il loro metodo su un dataset di livelli lineari provenienti da cifrari a blocchi (inclusi AES, Whirlwind, Clefia, PRIDE, ecc.) e su matrici MDS costruite.

• Profondità del Circuito Quantistico:

  • Whirlwind M0: Il metodo proposto ha ridotto la profondità del circuito da 28 (precedente stato dell'arte di [SF24]) a 17, un miglioramento del 39%. Anche il numero di porte è stato ridotto da 286 a 200.
  • MixColumn di AES: Il metodo automatizzato ha raggiunto una profondità di 10, uguagliando il risultato ottimizzato manualmente all'avanguardia di Zhang et al. [ZSWS24]. Il numero di porte è stato 107, che è solo 2 CNOT in più rispetto al risultato manuale (105) e significativamente migliore rispetto ai 131 CNOT ottenuti da [SF24].
  • Altre Matrici: Sono state osservate riduzioni significative della profondità per matrici ad alta densità (ad esempio Whirlwind, SKOP15 8x8), mentre i miglioramenti sono stati marginali o inesistenti per matrici sparse dove le euristiche funzionano già bene.

• Circuito Classico (Conteggio XOR):

  • Whirlwind M0: Il metodo ha raggiunto un conteggio s-XOR di 159, superando il precedente migliore di 173 (Yuan et al. [YWS+24]) di circa l'8%.
  • Prestazioni Generali: Sebbene il metodo generalmente comporti un sovraccarico di dimensione per molte matrici, è riuscito a battere i risultati all'avanguardia per specifiche matrici ad alta densità come Whirlwind M0 e M1.

Significato e Affermazioni
Il documento afferma che sfruttare la struttura circolante è una via potente, precedentemente sottoutilizzata, per l'ottimizzazione dei livelli lineari. Gli autori affermano che il loro approccio:

1. Supera le euristiche esistenti per specifiche matrici dense dove le strategie greedy standard faticano.
2. Automatizza l'ottimizzazione manuale, ottenendo risultati paragonabili a circuiti sintonizzati da esperti umani (come visto in MixColumn di AES) senza richiedere intervento manuale.
3. Fornisce una nuova linea di base per le valutazioni della sicurezza quantistica, offrendo stime di profondità più accurate per i livelli lineari, il che è cruciale per calcolare il costo DW (Profondità $\times$ Larghezza) nelle valutazioni di sicurezza post-quantistica.

Gli autori concludono che, sebbene il metodo non sia universalmente superiore per tutti i tipi di matrici (in particolare quelle sparse), offre un vantaggio significativo per le matrici con strutture circolanti e alta densità, dimostrando il potenziale dell'integrazione delle proprietà algebriche nella sintesi dei circuiti.