Sintesi Tecnica: Implementazione Vettorizzata di SQIsign Utilizzando AVX-512

Definizione del Problema

SQIsign è l'unico schema di firma digitale basato su isogenia sottoposto al processo di standardizzazione del NIST Post-Quantum Cryptography. Sebbene offra dimensioni delle chiavi e delle firme compatte basate sulla durezza del problema dell'anello degli endomorfismi per curve ellittiche supersingolari, la sua implementazione pratica è attualmente ostacolata da procedure di firma computazionalmente intensive. Il collo di bottiglia delle prestazioni risiede principalmente nelle operazioni sul "lato curva" (curve-side), che includono estese operazioni aritmetiche su grandi campi primi ($\mathbb{F}_p$) e sulle loro estensioni quadratiche ($\mathbb{F}_{p^2}$), operazioni su curve ellittiche (point doubling e moltiplicazione scalare) ed valutazioni di isogenia ad alta dimensione su superfici assieliche principalmente polarizzate (PPAS). Le implementazioni di riferimento esistenti si affidano pesantemente all'aritmetica scalare, utilizzando spesso la GNU Multiple Precision Arithmetic Library (GMP) per le componenti dell'algebra dei quaternioni, il che limita il throughput.

Metodologia

Questo documento presenta la prima implementazione vettorizzata completa delle componenti del "lato curva" di SQIsign utilizzando l'architettura delle istruzioni AVX-512 Integer Fused Multiply-Add (IFMA). Gli autori hanno riprogettato sistematicamente lo stack computazionale per sfruttare il parallelismo SIMD (Single Instruction, Multiple Data) attraverso tutti i principali livelli algoritmici, specificando esplicitamente che le componenti dell'algebra dei quaternioni (IdealToIsogeny) rimangono scalari e non ottimizzate in questo lavoro.

Strategie Tecniche Core

1. Aritmetica di Campo Finito ($\mathbb{F}_p$ e $\mathbb{F}_{p^2}$):

   • Rappresentazione: L'implementazione adotta una rappresentazione in radix-$2^{51}$ per gli elementi di campo, decomponendoli in cinque limb da 51 bit. Questa dimensione è scelta per adattarsi ai 52 bit inferiori dei lane a 64 bit, prevenendo l'overflow durante le operazioni IFMA pur riservando spazio per la riduzione differita.
   • Parallelizzazione: Viene impiegata una strategia di parallelizzazione $(8 \times 1)$ a livello di $\mathbb{F}_p$, elaborando otto elementi di campo indipendenti simultaneamente all'interno di un singolo registro ZMM da 512 bit.
   • Estensioni: Per $\mathbb{F}_{p^2}$, gli autori implementano tre distinti pattern di parallelizzazione — $(8 \times 1 \times 1)$, $(4 \times 2 \times 1)$ e $(2 \times 4 \times 1)$ — per bilanciare throughput e pressione sui registri a seconda delle specifiche esigenze algoritmiche (ad esempio, operazioni batch rispetto al parallelismo dei componenti interni).
   • Istruzioni: Il design sfrutta le istruzioni vpmadd52luq e vpmadd52huq per eseguire otto moltiplicazioni parallele da $52 \times 52$ bit con capacità di fused multiply-add, riducendo significativamente il conteggio delle istruzioni per la moltiplicazione di Montgomery e la propagazione del carry.

2. Operazioni su Curve Ellittiche:

   • Point Doubling: Gli autori hanno ottimizzato il raddoppio dei punti sia per coordinate $x$-only (curve di Montgomery) che per coordinate proiettive complete (Jacobiane e Modificate Jacobiane). Per le coordinate $x$-only, omettono costantemente i passaggi di normalizzazione nei contesti vettorizzati per mantenere il flusso di dati, mentre la normalizzazione viene applicata solo quando si raddoppiano più punti simultaneamente per massimizzare il parallelismo.
   • Moltiplicazione Scalare: L'implementazione vettorizza la scala di Montgomery, la scala a tre punti e la scala a due dimensioni (LadderBiscalar). Un contributo chiave è una strategia di vettorizzazione a quattro vie ridisegnata per la funzione xDBLADD che si adatta al formato generale dei parametri $(A_{24}:C_{24})$ utilizzato nella crittografia basata su isogenia, evitando le dipendenze dalla forma speciale dei precedenti tentativi di vettorizzazione.
   • Pairings: Il documento affronta i calcoli del pairing di Tate-Lichtenbaum utilizzati per la generazione di basi. Fondendo un raddoppio di punto con due addizioni differenziali, gli autori hanno creato un algoritmo cubicalDBLADDADD che genera i pairing richiesti utilizzando tre moltiplicazioni parallele a quattro vie e una squaring parallela a quattro vie.

3. Valutazioni di Isogenia:

   • Dimensione 1 & 2: Gli autori hanno applicato strategie di batching alle valutazioni di isogenia. Invece di elaborare i punti sequenzialmente, intercalano le coordinate di più punti attraverso i lane AVX-512 per saturare i moltiplicatori SIMD. Questo approccio è applicato sia alle 4-isogenie su curve ellittiche che alle $(2,2)$-isogenie su superfici assieliche (PPAS), utilizzando l'aritmetica delle coordinate theta.

4. Contesto Architetturale:

   • Il documento affronta i malintesi riguardanti l'obsolescenza di AVX-512, notando che l'imminente architettura Intel AVX10 (revisione 10.2, prevista per la fine del 2026) standardizzerà queste capacità sia sui core di performance che su quelli di efficienza, garantendo la viabilità a lungo termine.

Contributi Chiave

1. Vettorizzazione Completa delle Operazioni del Lato Curva di SQIsign: Il lavoro fornisce la prima piena vettorizzazione delle componenti del "lato curva" di SQIsign utilizzando AVX-512IFMA, coprendo l'aritmetica del campo primo, le estensioni quadratiche, le operazioni su curve ellittiche (inclusa la moltiplicazione scalare e i pairing) e le valutazioni di isogenia sia in una che in due dimensioni. Le componenti dell'algebra dei quaternioni rimangono scalari.
2. Analisi della Vettorizzazione Estesa su x86-64: A differenza dei precedenti sforzi di vettorizzazione basati su ARM (ad esempio, De Feo et al. usando NEON), questo lavoro esplora una gamma significativamente più ampia di funzioni sulla piattaforma x86-64, incluse strategie complesse di moltiplicazione scalare e operazioni di coordinate theta. I design algoritmici sono indicati come architettura-agnostici, offrendo una base per la migrazione verso altre piattaforme SIMD come ARM SVE o RISC-V.
3. Ottimizzazioni Generalizzabili: Le tecniche sviluppate per il raddoppio dei punti, la moltiplicazione scalare batch e l'aritmetica dei punti theta vettorizzata sono presentate come fondamenta metodologiche applicabili ad altre costrutti crittografici basati su isogenia che utilizzano varietà assieliche di dimensione superiore, indipendentemente dalle specifiche varianti di SQIsign.

Risultati Sperimentali

L'implementazione è stata testata su una CPU Intel Core i7-11700F (2.50GHz) eseguendo Ubuntu 24.04. I risultati sono confrontati con l'implementazione di riferimento ufficiale (ottimizzata per Broadwell con limb a 64 bit).

• Guadagni di Performance:
  • Generazione delle Chiavi: Accelerazioni compresi tra $1.03\times$ e $1.28\times$.
  • Firma (Signing): Accelerazioni compresi tra $1.08\times$ e $1.26\times$.
  • Verifica: Accelerazioni compresi tra $1.46\times$ e $1.84\times$.
• Combinazione con Qlapoti: Quando combinata con la tecnologia Qlapoti, l'implementazione raggiunge un'accelerazione di $2.69\times$ per la firma e un miglioramento di $3.18\times$ per la verifica al livello di sicurezza NIST I.
• Disparità di Verifica: Il documento nota che la verifica beneficia più significativamente rispetto alla firma perché la verifica si basa esclusivamente sulle operazioni del lato curva vettorizzate, mentre la firma coinvolge ancora operazioni di algebra dei quaternioni attualmente eseguite tramite la scala GMP (una componente non ottimizzata in questo lavoro).

Significato e Rivendicazioni

Gli autori affermano che questo lavoro dimostra che la vettorizzazione SIMD rappresenta una dimensione di ottimizzazione critica ma ancora poco esplorata per gli schemi basati su isogenia post-quantum.

• Indipendenza dagli Avanzamenti Algoritmici: Le ottimizzazioni sono ortogonali ai recenti raffinamenti algoritmici di alto livello (come Qlapoti o Superglue). Ciò implica che i guadagni di prestazione ottenuti attraverso la vettorizzazione sono moltiplicativi; le future innovazioni a livello di protocollo possono essere applicate sopra questa base vettorizzata per comporre miglioramenti delle prestazioni.
• Viabilità a Lungo Termine: Enfatizzando la standardizzazione delle capacità AVX-512 nelle future architetture Intel (AVX10), il documento sostiene che queste tecniche di ottimizzazione non sono una soluzione temporanea, ma un percorso sostenibile per una crittografia basata su isogenia efficiente.
• Universalità: La metodologia è rivendicata come applicabile a varie costruzioni basate su isogenia (ad esempio, SQIsignHD, SQIsign2D-East, SQIPrime) poiché tutte si basano sulle stesse primitive ($\mathbb{F}_{p^2}$ arithmetic, theta coordinates, e operazioni su curve ellittiche) che sono i bersagli di questa ottimizzazione.

Il documento conclude che, sebbene il "lato quaternioni" di SQIsign rimanga un collo di bottiglia scalare, la vettorizzazione del "lato curva" colma significativamente il divario tra compattezza teorica ed efficienza di implementazione pratica.