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

技术摘要：基于格密码中不完整 NTT 的 Toom-4 乘法显式成本分析

问题陈述
多项式乘法是基于格密码系统（如 Kyber (ML-KEM) 和 Dilithium (ML-DSA)）中的基本运算，通常在剩余环 $R_q = \mathbb{F}_q[x]/\langle x^n + 1 \rangle$ 上执行。虽然数论变换（NTT）提供了 $O(n \log n)$ 的乘法速度，但它严格要求满足条件 $2n \mid (q-1)$。这一约束限制了参数的选择，并可能损害安全性或效率目标。

为解决这一问题，Hafiz 等人（2025）引入了“不完整 NTT"，通过执行深度为 $\ell$ 的截断 NTT（其中 $2^{\ell+1} \mid (q-1)$）并将其与剩余子问题的传统多项式乘法相结合，从而放宽了模数约束。虽然在此框架内 Karatsuba 乘法已得到充分理解，但 Toom-4 乘法的精确成本——特别是其关于加法和乘法的常数因子——尚未以与不完整 NTT 成本模型兼容的形式表达。现有的 Toom-Cook 分析（例如 Bodrato 和 Zanoni 的研究）侧重于通用优化，但并未直接整合到不完整 NTT 所需的特定混合框架中。

方法论
作者提出了针对不完整 NTT 框架定制的 Toom-4 乘法具体实现，并推导出了显式的操作计数模型。

1. 实现策略：作者采用整数求值点 $\{0, \pm 1, \pm 2, 3, \infty\}$ 以避免分数常数。所有除法均推迟到最后一步缩放处理。
2. 加法链优化：方法论的一个关键组成部分是利用加法链来计算插值阶段所需的标量倍数。作者没有执行单独的标量乘法，而是为逆范德蒙德矩阵所需的靶系数构建了最小加法链。这使得能够系统地确定所需的加法和减法的确切数量。
3. 成本推导：作者将操作计数分离为系数域 $\mathbb{F}_q$ 上的加法/减法（$A$）和乘法（$M$）。他们推导了 Toom-4 步骤（分割、求值、递归乘法、插值和重组）的递归公式，并将这些公式整合到 Hafiz 等人建立的不完整 NTT 加权成本模型中。
4. 混合分析：该研究分析了结合 Toom-4、Karatsuba 和不完整 NTT 的混合策略。通过最小化加权成本函数 $C_w(n; \ell, L)$（其中 $w$ 是加法相对于乘法的成本），作者确定了各种子问题规模下的最优递归深度 $L$。

主要贡献

• 显式 Toom-4 成本模型：本文提供了首个与不完整 NTT 框架兼容的显式 Toom-4 成本模型。它详细列出了加法和乘法的确切计数，包括从优化加法链推导出的常数因子。
• 加法链验证：作者提供了验证脚本（可在其仓库中找到），确认了用于插值标量的加法链的最优性，确保所推导的计数对于所选求值点是最小的。
• 混合策略优化：该研究确定了特定的参数范围，在这些范围内，Toom-4/Karatsuba 混合策略在不完整 NTT 背景下优于纯 Karatsuba 或纯 Toom-4。
• 实验验证：作者在 Python 中实现了所提出的混合方法，并使用 2-adic 估值受限的 NTT 不友好素数模数（大小与 Dilithium 的模数相似，但 2-adic 估值受限）将理论预测与实验运行时间进行了验证。

结果
分析表明，Toom-4 在此背景下的有效性高度依赖于允许的 NTT 深度（$\ell$）和由此产生的子问题规模（$d = n/2^\ell$）：

• 有限深度机制：当允许的 NTT 深度较小时（例如 $\ell=0$ 或 $\ell=1$），子问题足够大，使得 Toom-4 能提供显著增益。例如，当 $n=256$ 且 $\ell=0$ 时，与纯 Karatsuba 相比，混合方法将加权成本降低了约 5%，并显著优于纯 Toom-4。
• 最优递归：最优递归深度 $L$ 随 $d$ 变化。对于 $d \le 128$，最优策略是 $L=0$（纯 Karatsuba）。对于 $d=256$，$L=1$ 是最优的；对于 $d \ge 512$，$L=2$ 是最优的。
• 实验确认：在 2-adic 估值受限的素数上进行的实验证实了理论模型。当最大允许深度最小（$\ell_{max}=0$）时，混合方法显著优于 Karatsuba（例如，对于 $n=256$，耗时分别为 14.182 毫秒对 16.722 毫秒）。随着允许深度的增加，混合方法的性能优势逐渐减弱，当子问题变得太小时，最终与 Karatsuba 趋同。

意义与主张
作者谦逊地声称，他们的主要贡献并非一种新的乘法算法，而是针对不完整 NTT 框架的 Toom-4 精确常数级分析。他们断言，这一显式成本模型填补了文献中的空白，使得能够在无法使用完整 NTT 的场景中系统地评估混合策略。

论文结论指出，Toom-4 在不完整 NTT 的“有限深度机制”中最为有利，特别是当 $q-1$ 的 2-adic 估值限制了变换深度时。在这种情况下，所提出的混合策略比标准的基于 Karatsuba 的方法提供了可衡量的性能提升。作者指出，他们目前的实现是在 Python 中完成的，未来的工作包括优化底层实现（例如在 C/C++ 中）以及在具体的基于格的方案中进行进一步评估。