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

Technical Summary: Explicit Cost Analysis of Toom-4 Multiplication for Incomplete NTT in Lattice-Based Cryptography

Problem Statement
Polynomial multiplication is a fundamental operation in lattice-based cryptosystems such as Kyber (ML-KEM) and Dilithium (ML-DSA), typically performed over residue rings $R_q = \mathbb{F}_q[x]/\langle x^n + 1 \rangle$. While the Number Theoretic Transform (NTT) offers $O(n \log n)$ multiplication speed, it strictly requires the condition $2n \mid (q-1)$. This constraint limits parameter selection and can compromise security or efficiency goals.

To address this, Hafiz et al. (2025) introduced the "incomplete NTT," which relaxes the modulus constraint by performing a truncated NTT of depth $\ell$ (where $2^{\ell+1} \mid (q-1)$) and combining it with conventional polynomial multiplication for the remaining subproblems. While Karatsuba multiplication is well-understood within this framework, the precise cost of Toom-4 multiplication—specifically its constant factors regarding additions and multiplications—has not been expressed in a form compatible with the incomplete NTT cost model. Existing analyses of Toom-Cook (e.g., Bodrato and Zanoni) focus on general optimization but are not directly integrated into the specific hybrid framework required for incomplete NTT.

Methodology
The authors present a concrete implementation of Toom-4 multiplication tailored to the incomplete NTT framework and derive an explicit operation count model.

1. Implementation Strategy: The authors adopt integer evaluation points $\{0, \pm 1, \pm 2, 3, \infty\}$ to avoid fractional constants. All divisions are postponed to a final scaling step.
2. Addition Chain Optimization: A critical component of the methodology is the use of addition chains to compute the necessary scalar multiples during the interpolation phase. Instead of performing individual scalar multiplications, the authors construct minimal addition chains for the target coefficients required by the inverse Vandermonde matrix. This allows for a systematic determination of the exact number of additions and subtractions required.
3. Cost Derivation: The authors separate the operation counts into additions/subtractions ($A$) and multiplications ($M$) over the coefficient field $\mathbb{F}_q$. They derive recursive formulas for the Toom-4 steps (splitting, evaluation, recursive multiplication, interpolation, and re-composition) and integrate these into the weighted cost model of incomplete NTT established by Hafiz et al.
4. Hybrid Analysis: The study analyzes hybrid strategies that combine Toom-4, Karatsuba, and incomplete NTT. By minimizing the weighted cost function $C_w(n; \ell, L)$ (where $w$ is the relative cost of addition to multiplication), the authors determine the optimal recursion depth $L$ for various subproblem sizes.

Key Contributions

• Explicit Toom-4 Cost Model: The paper provides the first explicit Toom-4 cost model compatible with the incomplete NTT framework. It details the exact counts of additions and multiplications, including constant factors derived from optimized addition chains.
• Addition Chain Verification: The authors provide verification scripts (available in their repository) that confirm the optimality of the addition chains used for the interpolation scalars, ensuring the derived counts are minimal for the chosen evaluation points.
• Hybrid Strategy Optimization: The study identifies specific parameter ranges where a Toom-4/Karatsuba hybrid outperforms pure Karatsuba or pure Toom-4 within the incomplete NTT context.
• Experimental Validation: The authors implemented the proposed hybrid method in Python and validated the theoretical predictions against experimental running times using NTT-unfriendly prime moduli (similar in size to Dilithium's modulus but with restricted 2-adic valuations).

Results
The analysis reveals that the effectiveness of Toom-4 in this context is highly dependent on the admissible NTT depth ($\ell$) and the resulting subproblem size ($d = n/2^\ell$):

• Limited Depth Regime: When the admissible NTT depth is small (e.g., $\ell=0$ or $\ell=1$), the subproblems are large enough that Toom-4 provides significant gains. For instance, with $n=256$ and $\ell=0$, the hybrid method reduced the weighted cost by approximately 5% compared to pure Karatsuba and significantly outperformed pure Toom-4.
• Optimal Recursion: The optimal recursion depth $L$ varies with $d$. For $d \le 128$, the optimal strategy is $L=0$ (pure Karatsuba). For $d=256$, $L=1$ is optimal, and for $d \ge 512$, $L=2$ is optimal.
• Experimental Confirmation: Experiments on primes with restricted 2-adic valuations confirmed the theoretical model. When the maximal admissible depth was minimal ($\ell_{max}=0$), the hybrid method significantly outperformed Karatsuba (e.g., 14.182 ms vs. 16.722 ms for $n=256$). As the admissible depth increased, the performance advantage of the hybrid method diminished, eventually converging with Karatsuba when subproblems became too small.

Significance and Claims
The authors modestly claim that their primary contribution is not a new multiplication algorithm, but a precise constant-level analysis of Toom-4 tailored to the incomplete NTT framework. They assert that this explicit cost model bridges a gap in the literature, allowing for the systematic evaluation of hybrid strategies in scenarios where full NTT is unavailable.

The paper concludes that Toom-4 is most advantageous in the "limited-depth regime" of incomplete NTT, specifically when the 2-adic valuation of $q-1$ restricts the transform depth. In such cases, the proposed hybrid strategy offers a measurable performance improvement over standard Karatsuba-based approaches. The authors note that their current implementation is in Python and that future work involves optimizing low-level implementations (e.g., in C/C++) and further evaluation in concrete lattice-based schemes.