一种用于小模数多项式乘法快速数论变换的扩域方法

摘要：

在基于Ring-LWE体系的格密码算法中,快速数论变换是加速多项式环乘法的常见方法,但该方法对于系数域模数小于多项式长度的多项式环乘法不适用.本文通过对多项式系数域构造扩域,扩大系数域的阶数,使小模数的多项式环乘法也能够使用快速数论变换来加速.扩域上的有限域乘法会带来额外的计算开支,但快速NTT变换的使用可以带来指数级的加速效果,总体来说节省更多的计算复杂度.常见的快速数论变换使用与快速傅里叶变换相似的折半定理,进行基2的快速变换,而系数域构造扩域后由于其阶数无法满足基2变换的条件,本文通过将多项式长度进行质因子分解来推导复合基的快速数论变换,最终为小模数多项式环乘法提供可观的加速效果.

关键词：格密码、Ring-LWE、快速数论变换、扩域

所属期刊栏目：8

分类号：TP309.7(计算技术、计算机技术)

资助基金：国家科技重大专项2017ZX01030301-003

在线出版日期：2021-06-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共13页

页码：260-272