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

Resumo Técnico: Análise de Custo Explícito da Multiplicação Toom-4 para NTT Incompleta em Criptografia Baseada em Retículos

Declaração do Problema
A multiplicação de polinômios é uma operação fundamental em sistemas criptográficos baseados em retículos, como Kyber (ML-KEM) e Dilithium (ML-DSA), tipicamente realizada sobre anéis de resíduo $R_q = \mathbb{F}_q[x]/\langle x^n + 1 \rangle$. Embora a Transformada Numérica Teórica (NTT) ofereça velocidade de multiplicação $O(n \log n)$, ela exige estritamente a condição $2n \mid (q-1)$. Essa restrição limita a seleção de parâmetros e pode comprometer objetivos de segurança ou eficiência.

Para abordar isso, Hafiz et al. (2025) introduziram a "NTT incompleta", que relaxa a restrição do módulo realizando uma NTT truncada de profundidade $\ell$ (onde $2^{\ell+1} \mid (q-1)$) e combinando-a com multiplicação polinomial convencional para os subproblemas restantes. Embora a multiplicação de Karatsuba seja bem compreendida dentro desse framework, o custo preciso da multiplicação Toom-4 — especificamente seus fatores constantes referentes a adições e multiplicações — não foi expresso em uma forma compatível com o modelo de custo da NTT incompleta. Análises existentes de Toom-Cook (por exemplo, Bodrato e Zanoni) focam em otimização geral, mas não estão diretamente integradas ao framework híbrido específico requerido para a NTT incompleta.

Metodologia
Os autores apresentam uma implementação concreta da multiplicação Toom-4 adaptada ao framework da NTT incompleta e derivam um modelo explícito de contagem de operações.

1. Estratégia de Implementação: Os autores adotam pontos de avaliação inteiros $\{0, \pm 1, \pm 2, 3, \infty\}$ para evitar constantes fracionárias. Todas as divisões são postergadas para uma etapa final de escalonamento.
2. Otimização da Cadeia de Adição: Um componente crítico da metodologia é o uso de cadeias de adição para calcular os múltiplos escalares necessários durante a fase de interpolação. Em vez de realizar multiplicações escalares individuais, os autores constroem cadeias de adição mínimas para os coeficientes-alvo exigidos pela matriz de Vandermonde inversa. Isso permite uma determinação sistemática do número exato de adições e subtrações requeridas.
3. Derivação de Custos: Os autores separam as contagens de operações em adições/subtrações ($A$) e multiplicações ($M$) sobre o campo de coeficientes $\mathbb{F}_q$. Eles derivam fórmulas recursivas para as etapas Toom-4 (divisão, avaliação, multiplicação recursiva, interpolação e recomposição) e integram-nas ao modelo de custo ponderado da NTT incompleta estabelecido por Hafiz et al.
4. Análise Híbrida: O estudo analisa estratégias híbridas que combinam Toom-4, Karatsuba e NTT incompleta. Ao minimizar a função de custo ponderado $C_w(n; \ell, L)$ (onde $w$ é o custo relativo da adição em relação à multiplicação), os autores determinam a profundidade de recursão ótima $L$ para vários tamanhos de subproblema.

Principais Contribuições

• Modelo de Custo Toom-4 Explícito: O artigo fornece o primeiro modelo de custo Toom-4 explícito compatível com o framework da NTT incompleta. Detalha as contagens exatas de adições e multiplicações, incluindo fatores constantes derivados de cadeias de adição otimizadas.
• Verificação de Cadeia de Adição: Os autores fornecem scripts de verificação (disponíveis em seu repositório) que confirmam a otimalidade das cadeias de adição usadas para os escalares de interpolação, garantindo que as contagens derivadas sejam mínimas para os pontos de avaliação escolhidos.
• Otimização de Estratégia Híbrida: O estudo identifica faixas de parâmetros específicas onde um híbrido Toom-4/Karatsuba supera o Karatsuba puro ou o Toom-4 puro no contexto da NTT incompleta.
• Validação Experimental: Os autores implementaram o método híbrido proposto em Python e validaram as previsões teóricas contra tempos de execução experimentais usando módulos primos não amigáveis à NTT (semelhantes em tamanho ao módulo do Dilithium, mas com valuações 2-ádicas restritas).

Resultados
A análise revela que a eficácia do Toom-4 neste contexto é altamente dependente da profundidade de NTT admissível ($\ell$) e do tamanho resultante do subproblema ($d = n/2^\ell$):

• Regime de Profundidade Limitada: Quando a profundidade de NTT admissível é pequena (por exemplo, $\ell=0$ ou $\ell=1$), os subproblemas são grandes o suficiente para que o Toom-4 forneça ganhos significativos. Por exemplo, com $n=256$ e $\ell=0$, o método híbrido reduziu o custo ponderado em aproximadamente 5% em comparação ao Karatsuba puro e superou significativamente o Toom-4 puro.
• Recursão Ótima: A profundidade de recursão ótima $L$ varia com $d$. Para $d \le 128$, a estratégia ótima é $L=0$ (Karatsuba puro). Para $d=256$, $L=1$ é ótimo, e para $d \ge 512$, $L=2$ é ótimo.
• Confirmação Experimental: Experimentos em primos com valuações 2-ádicas restritas confirmaram o modelo teórico. Quando a profundidade admissível máxima era mínima ($\ell_{max}=0$), o método híbrido superou significativamente o Karatsuba (por exemplo, 14,182 ms vs. 16,722 ms para $n=256$). À medida que a profundidade admissível aumentava, a vantagem de desempenho do método híbrido diminuía, convergindo eventualmente com o Karatsuba quando os subproblemas se tornavam muito pequenos.

Significado e Alegações
Os autores afirmam modestamente que sua principal contribuição não é um novo algoritmo de multiplicação, mas uma análise precisa em nível de constante do Toom-4 adaptada ao framework da NTT incompleta. Eles afirmam que este modelo de custo explícito preenche uma lacuna na literatura, permitindo a avaliação sistemática de estratégias híbridas em cenários onde a NTT completa não está disponível.

O artigo conclui que o Toom-4 é mais vantajoso no "regime de profundidade limitada" da NTT incompleta, especificamente quando a valuação 2-ádica de $q-1$ restringe a profundidade da transformada. Nesses casos, a estratégia híbrida proposta oferece uma melhoria de desempenho mensurável sobre as abordagens padrão baseadas em Karatsuba. Os autores observam que sua implementação atual está em Python e que trabalhos futuros envolvem a otimização de implementações de baixo nível (por exemplo, em C/C++) e avaliação adicional em esquemas concretos baseados em retículos.