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

Résumé technique : Analyse explicite des coûts de la multiplication Toom-4 pour l'NTT incomplet en cryptographie basée sur les réseaux

Énoncé du problème
La multiplication de polynômes est une opération fondamentale dans les cryptosystèmes basés sur les réseaux tels que Kyber (ML-KEM) et Dilithium (ML-DSA), généralement effectuée sur des anneaux de résidus $R_q = \mathbb{F}_q[x]/\langle x^n + 1 \rangle$. Bien que la transformée de nombres (NTT) offre une vitesse de multiplication en $O(n \log n)$, elle exige strictement la condition $2n \mid (q-1)$. Cette contrainte limite la sélection des paramètres et peut compromettre les objectifs de sécurité ou d'efficacité.

Pour y remédier, Hafiz et al. (2025) ont introduit l'« NTT incomplet », qui assouplit la contrainte de module en effectuant une NTT tronquée de profondeur $\ell$ (où $2^{\ell+1} \mid (q-1)$) et en la combinant avec une multiplication polynomiale conventionnelle pour les sous-problèmes restants. Si la multiplication de Karatsuba est bien comprise dans ce cadre, le coût précis de la multiplication Toom-4 — spécifiquement ses facteurs constants concernant les additions et les multiplications — n'a pas été exprimé sous une forme compatible avec le modèle de coût de l'NTT incomplet. Les analyses existantes de Toom-Cook (par exemple Bodrato et Zanoni) se concentrent sur l'optimisation générale mais ne sont pas directement intégrées dans le cadre hybride spécifique requis pour l'NTT incomplet.

Méthodologie
Les auteurs présentent une implémentation concrète de la multiplication Toom-4 adaptée au cadre de l'NTT incomplet et dérivent un modèle explicite de comptage des opérations.

1. Stratégie d'implémentation : Les auteurs adoptent des points d'évaluation entiers $\{0, \pm 1, \pm 2, 3, \infty\}$ pour éviter les constantes fractionnaires. Toutes les divisions sont reportées à une étape finale de mise à l'échelle.
2. Optimisation des chaînes d'addition : Un composant critique de la méthodologie est l'utilisation de chaînes d'addition pour calculer les multiples scalaires nécessaires durant la phase d'interpolation. Au lieu d'effectuer des multiplications scalaires individuelles, les auteurs construisent des chaînes d'addition minimales pour les coefficients cibles requis par la matrice de Vandermonde inverse. Cela permet une détermination systématique du nombre exact d'additions et de soustractions requis.
3. Dérivation des coûts : Les auteurs séparent les comptages d'opérations en additions/soustractions ($A$) et multiplications ($M$) sur le corps des coefficients $\mathbb{F}_q$. Ils dérivent des formules récursives pour les étapes Toom-4 (découpage, évaluation, multiplication récursive, interpolation et recomposition) et les intègrent dans le modèle de coût pondéré de l'NTT incomplet établi par Hafiz et al.
4. Analyse hybride : L'étude analyse des stratégies hybrides combinant Toom-4, Karatsuba et l'NTT incomplet. En minimisant la fonction de coût pondéré $C_w(n; \ell, L)$ (où $w$ est le coût relatif de l'addition par rapport à la multiplication), les auteurs déterminent la profondeur de récursivité optimale $L$ pour diverses tailles de sous-problèmes.

Contributions clés

• Modèle de coût Toom-4 explicite : L'article fournit le premier modèle de coût Toom-4 explicite compatible avec le cadre de l'NTT incomplet. Il détaille les comptages exacts d'additions et de multiplications, y compris les facteurs constants dérivés de chaînes d'addition optimisées.
• Vérification des chaînes d'addition : Les auteurs fournissent des scripts de vérification (disponibles dans leur dépôt) qui confirment l'optimalité des chaînes d'addition utilisées pour les scalaires d'interpolation, garantissant que les comptages dérivés sont minimaux pour les points d'évaluation choisis.
• Optimisation de la stratégie hybride : L'étude identifie des plages de paramètres spécifiques où une hybride Toom-4/Karatsuba surpasse Karatsuba pur ou Toom-4 pur dans le contexte de l'NTT incomplet.
• Validation expérimentale : Les auteurs ont implémenté la méthode hybride proposée en Python et ont validé les prédictions théoriques contre des temps d'exécution expérimentaux en utilisant des modules premiers non favorables à l'NTT (de taille similaire au module de Dilithium mais avec des valuations 2-adiques restreintes).

Résultats
L'analyse révèle que l'efficacité de Toom-4 dans ce contexte dépend fortement de la profondeur NTT admissible ($\ell$) et de la taille résultante du sous-problème ($d = n/2^\ell$) :

• Régime de profondeur limitée : Lorsque la profondeur NTT admissible est faible (par exemple $\ell=0$ ou $\ell=1$), les sous-problèmes sont suffisamment grands pour que Toom-4 apporte des gains significatifs. Par exemple, avec $n=256$ et $\ell=0$, la méthode hybride a réduit le coût pondéré d'environ 5 % par rapport à Karatsuba pur et a nettement surpassé Toom-4 pur.
• Récursivité optimale : La profondeur de récursivité optimale $L$ varie avec $d$. Pour $d \le 128$, la stratégie optimale est $L=0$ (Karatsuba pur). Pour $d=256$, $L=1$ est optimal, et pour $d \ge 512$, $L=2$ est optimal.
• Confirmation expérimentale : Des expériences sur des nombres premiers avec des valuations 2-adiques restreintes ont confirmé le modèle théorique. Lorsque la profondeur admissible maximale était minimale ($\ell_{max}=0$), la méthode hybride a nettement surpassé Karatsuba (par exemple 14,182 ms contre 16,722 ms pour $n=256$). À mesure que la profondeur admissible augmentait, l'avantage de performance de la méthode hybride diminuait, convergeant éventuellement avec Karatsuba lorsque les sous-problèmes devenaient trop petits.

Signification et affirmations
Les auteurs affirment modestement que leur contribution principale n'est pas un nouvel algorithme de multiplication, mais une analyse explicite au niveau des constantes de Toom-4 adaptée au cadre de l'NTT incomplet. Ils affirment que ce modèle de coût explicite comble une lacune dans la littérature, permettant l'évaluation systématique des stratégies hybrides dans des scénarios où l'NTT complet n'est pas disponible.

L'article conclut que Toom-4 est le plus avantageux dans le « régime de profondeur limitée » de l'NTT incomplet, spécifiquement lorsque la valuation 2-adique de $q-1$ restreint la profondeur de la transformée. Dans de tels cas, la stratégie hybride proposée offre une amélioration de performance mesurable par rapport aux approches standard basées sur Karatsuba. Les auteurs notent que leur implémentation actuelle est en Python et que les travaux futurs consistent à optimiser les implémentations de bas niveau (par exemple en C/C++) et à poursuivre l'évaluation dans des schémas concrets basés sur les réseaux.