Explicit cost analysis of Toom-4 multiplication for incomplete NTT in lattice-based cryptography

Sintesi Tecnica: Analisi dei Costi Espliciti della Moltiplicazione Toom-4 per NTT Incompleta nella Crittografia Basata su Reticoli

Enunciato del Problema
La moltiplicazione di polinomi è un'operazione fondamentale nei sistemi crittografici basati su reticoli come Kyber (ML-KEM) e Dilithium (ML-DSA), tipicamente eseguita su anelli di resto $R_q = \mathbb{F}_q[x]/\langle x^n + 1 \rangle$. Sebbene la Trasformata Numerica Teorica (NTT) offra una velocità di moltiplicazione di $O(n \log n)$, richiede rigorosamente la condizione $2n \mid (q-1)$. Questo vincolo limita la selezione dei parametri e può compromettere gli obiettivi di sicurezza o efficienza.

Per affrontare questo problema, Hafiz et al. (2025) hanno introdotto la "NTT incompleta", che rilassa il vincolo sul modulo eseguendo una NTT tronca di profondità $\ell$ (dove $2^{\ell+1} \mid (q-1)$) e combinandola con la moltiplicazione polinomiale convenzionale per i sottoproblemi rimanenti. Sebbene la moltiplicazione di Karatsuba sia ben compresa all'interno di questo quadro, il costo preciso della moltiplicazione Toom-4, in particolare i suoi fattori costanti relativi ad addizioni e moltiplicazioni, non è stato espresso in una forma compatibile con il modello di costo della NTT incompleta. Le analisi esistenti di Toom-Cook (ad esempio Bodrato e Zanoni) si concentrano sull'ottimizzazione generale ma non sono integrate direttamente nel quadro ibrido specifico richiesto per la NTT incompleta.

Metodologia
Gli autori presentano un'implementazione concreta della moltiplicazione Toom-4 adattata al quadro della NTT incompleta e derivano un modello esplicito di conteggio delle operazioni.

1. Strategia di Implementazione: Gli autori adottano punti di valutazione interi $\{0, \pm 1, \pm 2, 3, \infty\}$ per evitare costanti frazionarie. Tutte le divisioni sono posticipate a una fase finale di scalatura.
2. Ottimizzazione della Catena di Addizione: Un componente critico della metodologia è l'uso di catene di addizione per calcolare i multipli scalari necessari durante la fase di interpolazione. Invece di eseguire moltiplicazioni scalari individuali, gli autori costruiscono catene di addizione minime per i coefficienti target richiesti dalla matrice di Vandermonde inversa. Ciò consente una determinazione sistematica del numero esatto di addizioni e sottrazioni richieste.
3. Derivazione del Costo: Gli autori separano i conteggi delle operazioni in addizioni/sottrazioni ($A$) e moltiplicazioni ($M$) sul campo dei coefficienti $\mathbb{F}_q$. Derivano formule ricorsive per i passaggi Toom-4 (suddivisione, valutazione, moltiplicazione ricorsiva, interpolazione e ricomposizione) e li integrano nel modello di costo ponderato della NTT incompleta stabilito da Hafiz et al.
4. Analisi Ibrida: Lo studio analizza strategie ibride che combinano Toom-4, Karatsuba e NTT incompleta. Minimizzando la funzione di costo ponderata $C_w(n; \ell, L)$ (dove $w$ è il costo relativo dell'addizione rispetto alla moltiplicazione), gli autori determinano la profondità di ricorsione ottimale $L$ per varie dimensioni dei sottoproblemi.

Contributi Chiave

• Modello di Costo Toom-4 Esplicito: Il documento fornisce il primo modello di costo Toom-4 esplicito compatibile con il quadro della NTT incompleta. Dettaglia i conteggi esatti di addizioni e moltiplicazioni, inclusi i fattori costanti derivati da catene di addizione ottimizzate.
• Verifica delle Catene di Addizione: Gli autori forniscono script di verifica (disponibili nel loro repository) che confermano l'ottimalità delle catene di addizione utilizzate per gli scalari di interpolazione, garantendo che i conteggi derivati siano minimi per i punti di valutazione scelti.
• Ottimizzazione della Strategia Ibrida: Lo studio identifica intervalli di parametri specifici in cui un ibrido Toom-4/Karatsuba supera Karatsuba puro o Toom-4 puro nel contesto della NTT incompleta.
• Validazione Sperimentale: Gli autori hanno implementato il metodo ibrido proposto in Python e hanno validato le previsioni teoriche rispetto ai tempi di esecuzione sperimentali utilizzando moduli primi non amichevoli per l'NTT (simili per dimensione al modulo di Dilithium ma con valutazioni 2-adiche ristrette).

Risultati
L'analisi rivela che l'efficacia di Toom-4 in questo contesto dipende fortemente dalla profondità NTT ammissibile ($\ell$) e dalla dimensione risultante del sottoproblema ($d = n/2^\ell$):

• Regime di Profondità Limitata: Quando la profondità NTT ammissibile è piccola (ad esempio $\ell=0$ o $\ell=1$), i sottoproblemi sono abbastanza grandi da permettere a Toom-4 di fornire guadagni significativi. Ad esempio, con $n=256$ e $\ell=0$, il metodo ibrido ha ridotto il costo ponderato di circa il 5% rispetto a Karatsuba puro e ha superato significativamente Toom-4 puro.
• Ricorsione Ottimale: La profondità di ricorsione ottimale $L$ varia con $d$. Per $d \le 128$, la strategia ottimale è $L=0$ (Karatsuba puro). Per $d=256$, $L=1$ è ottimale, e per $d \ge 512$, $L=2$ è ottimale.
• Conferma Sperimentale: Gli esperimenti su numeri primi con valutazioni 2-adiche ristrette hanno confermato il modello teorico. Quando la profondità ammissibile massima era minima ($\ell_{max}=0$), il metodo ibrido ha superato significativamente Karatsuba (ad esempio, 14,182 ms contro 16,722 ms per $n=256$). All'aumentare della profondità ammissibile, il vantaggio prestazionale del metodo ibrido si è ridotto, convergendo infine con Karatsuba quando i sottoproblemi sono diventati troppo piccoli.

Significato e Affermazioni
Gli autori affermano modestamente che il loro contributo principale non è un nuovo algoritmo di moltiplicazione, ma un'analisi precisa a livello di costanti di Toom-4 adattata al quadro della NTT incompleta. Affermano che questo modello di costo esplicito colma una lacuna nella letteratura, consentendo la valutazione sistematica delle strategie ibride in scenari in cui l'NTT completa non è disponibile.

Il documento conclude che Toom-4 è più vantaggioso nel "regime di profondità limitata" della NTT incompleta, specificamente quando la valutazione 2-adica di $q-1$ limita la profondità della trasformazione. In tali casi, la strategia ibrida proposta offre un miglioramento misurabile delle prestazioni rispetto agli approcci standard basati su Karatsuba. Gli autori notano che la loro implementazione attuale è in Python e che i lavori futuri riguardano l'ottimizzazione delle implementazioni a basso livello (ad esempio in C/C++) e un'ulteriore valutazione in schemi concreti basati su reticoli.