#Toom-4

共收录 1 条相关安全情报。

← 返回所有主题
👥 作者: Sakura Oku, Momonari Kudo

在基于格的密码学中,多项式乘法是核心运算。数论变换(NTT)能够实现快速乘法,但其系数域模数有严格限制。Hafiz等人(2025)通过引入不完全NTT(incomplete NTT)解决了这一局限,该方案将截断NTT与传统乘法方法结合。本文针对不完全NTT框架下的Toom-4乘法进行了深入研究。尽管Toom-4在渐近复杂度上优于Karatsuba乘法,但其精确成本尚未以与不完全NTT兼容的形式表达。为此,作者给出了Toom-4的具体实现,并推导了显式的运算计数,将系数域上的加法/减法与乘法分开统计。基于加法链的分析,提出了一个简洁的不完全NTT成本模型。利用该模型,分析了结合Toom-4、Karatsuba和不完全NTT的混合策略,确定了Toom-4具有优势的参数范围,并通过实验验证了预测行为的正确性。该工作为格密码实现中乘法方法的选择提供了理论依据,有助于优化性能。

💡 推荐理由: 该研究为格密码底层运算提供了精确成本模型,有助于安全工程师选取最优乘法策略以提升效率,同时不影响安全性。对于实现高性能格密码库(如Kyber、Dilithium)的团队具有参考价值。

🎯 建议动作: 研究跟进

排序因子: 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.5)