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

Resumen Técnico: Análisis de Costos Explícitos de la Multiplicación Toom-4 para la NTT Incompleta en Criptografía Basada en Retículos

Planteamiento del Problema
La multiplicación de polinomios es una operación fundamental en los sistemas criptográficos basados en retículos, como Kyber (ML-KEM) y Dilithium (ML-DSA), típicamente realizada sobre anillos de residuos $R_q = \mathbb{F}_q[x]/\langle x^n + 1 \rangle$. Aunque la Transformada Numérica Teórica (NTT) ofrece una velocidad de multiplicación de $O(n \log n)$, requiere estrictamente la condición $2n \mid (q-1)$. Esta restricción limita la selección de parámetros y puede comprometer los objetivos de seguridad o eficiencia.

Para abordar esto, Hafiz et al. (2025) introdujeron la "NTT incompleta", que relaja la restricción del módulo realizando una NTT truncada de profundidad $\ell$ (donde $2^{\ell+1} \mid (q-1)$) y combinándola con la multiplicación polinómica convencional para los subproblemas restantes. Si bien la multiplicación de Karatsuba está bien entendida dentro de este marco, el costo preciso de la multiplicación Toom-4, específicamente sus factores constantes respecto a las adiciones y multiplicaciones, no se ha expresado en una forma compatible con el modelo de costos de la NTT incompleta. Los análisis existentes de Toom-Cook (por ejemplo, Bodrato y Zanoni) se centran en la optimización general pero no están integrados directamente en el marco híbrido específico requerido para la NTT incompleta.

Metodología
Los autores presentan una implementación concreta de la multiplicación Toom-4 adaptada al marco de la NTT incompleta y derivan un modelo explícito de conteo de operaciones.

1. Estrategia de Implementación: Los autores adoptan puntos de evaluación enteros $\{0, \pm 1, \pm 2, 3, \infty\}$ para evitar constantes fraccionarias. Todas las divisiones se posponen a una etapa final de escalado.
2. Optimización de la Cadena de Adiciones: Un componente crítico de la metodología es el uso de cadenas de adiciones para calcular los múltiplos escalares necesarios durante la fase de interpolación. En lugar de realizar multiplicaciones escalares individuales, los autores construyen cadenas de adiciones mínimas para los coeficientes objetivo requeridos por la matriz inversa de Vandermonde. Esto permite una determinación sistemática del número exacto de adiciones y sustracciones requeridas.
3. Derivación de Costos: Los autores separan los conteos de operaciones en adiciones/sustracciones ($A$) y multiplicaciones ($M$) sobre el campo de coeficientes $\mathbb{F}_q$. Derivan fórmulas recursivas para los pasos de Toom-4 (división, evaluación, multiplicación recursiva, interpolación y recomposición) e integran estos en el modelo de costos ponderados de la NTT incompleta establecido por Hafiz et al.
4. Análisis Híbrido: El estudio analiza estrategias híbridas que combinan Toom-4, Karatsuba y NTT incompleta. Al minimizar la función de costo ponderado $C_w(n; \ell, L)$ (donde $w$ es el costo relativo de la adición respecto a la multiplicación), los autores determinan la profundidad de recursión óptima $L$ para varios tamaños de subproblema.

Contribuciones Clave

• Modelo de Costos Toom-4 Explícito: El artículo proporciona el primer modelo de costos Toom-4 explícito compatible con el marco de la NTT incompleta. Detalla los conteos exactos de adiciones y multiplicaciones, incluidos los factores constantes derivados de cadenas de adiciones optimizadas.
• Verificación de Cadenas de Adiciones: Los autores proporcionan scripts de verificación (disponibles en su repositorio) que confirman la optimalidad de las cadenas de adiciones utilizadas para los escalares de interpolación, asegurando que los conteos derivados sean mínimos para los puntos de evaluación elegidos.
• Optimización de Estrategia Híbrida: El estudio identifica rangos de parámetros específicos donde un híbrido Toom-4/Karatsuba supera a Karatsuba puro o a Toom-4 puro dentro del contexto de la NTT incompleta.
• Validación Experimental: Los autores implementaron el método híbrido propuesto en Python y validaron las predicciones teóricas contra tiempos de ejecución experimentales utilizando módulos primos poco amigables para la NTT (similares en tamaño al módulo de Dilithium pero con valoraciones 2-ádicas restringidas).

Resultados
El análisis revela que la efectividad de Toom-4 en este contexto depende altamente de la profundidad de NTT admisible ($\ell$) y del tamaño resultante del subproblema ($d = n/2^\ell$):

• Régimen de Profundidad Limitada: Cuando la profundidad de NTT admisible es pequeña (por ejemplo, $\ell=0$ o $\ell=1$), los subproblemas son lo suficientemente grandes como para que Toom-4 proporcione ganancias significativas. Por ejemplo, con $n=256$ y $\ell=0$, el método híbrido redujo el costo ponderado en aproximadamente un 5% en comparación con Karatsuba puro y superó significativamente a Toom-4 puro.
• Recursión Óptima: La profundidad de recursión óptima $L$ varía con $d$. Para $d \le 128$, la estrategia óptima es $L=0$ (Karatsuba puro). Para $d=256$, $L=1$ es óptimo, y para $d \ge 512$, $L=2$ es óptimo.
• Confirmación Experimental: Los experimentos con primos que tienen valoraciones 2-ádicas restringidas confirmaron el modelo teórico. Cuando la profundidad admisible máxima era mínima ($\ell_{max}=0$), el método híbrido superó significativamente a Karatsuba (por ejemplo, 14.182 ms vs. 16.722 ms para $n=256$). A medida que aumentaba la profundidad admisible, la ventaja de rendimiento del método híbrido disminuyó, convergiendo eventualmente con Karatsuba cuando los subproblemas se volvieron demasiado pequeños.

Significado y Afirmaciones
Los autores afirman modestamente que su contribución principal no es un nuevo algoritmo de multiplicación, sino un análisis preciso a nivel de constantes de Toom-4 adaptado al marco de la NTT incompleta. Aseguran que este modelo de costos explícito cierra una brecha en la literatura, permitiendo la evaluación sistemática de estrategias híbridas en escenarios donde la NTT completa no está disponible.

El artículo concluye que Toom-4 es más ventajoso en el "régimen de profundidad limitada" de la NTT incompleta, específicamente cuando la valoración 2-ádica de $q-1$ restringe la profundidad de la transformada. En tales casos, la estrategia híbrida propuesta ofrece una mejora medible en el rendimiento sobre los enfoques estándar basados en Karatsuba. Los autores señalan que su implementación actual está en Python y que el trabajo futuro implica la optimización de implementaciones de bajo nivel (por ejemplo, en C/C++) y una evaluación adicional en esquemas concretos basados en retículos.