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

Method to Construct Extension Field for NTT of Polynomial Multiplication with Small Modulus

作　　者：殷彦昭 乌力吉 张向民[1,2] 徐科 杨维[3] YIN Yan-Zhao;WU Li-Ji;ZHANG Xiang-Min;XU Ke;YANG Wei(Beijing National Research Center for Information Science and Technology,Beijing 100084,China;Institute of Microelectronics,Tsinghua University,Beijing 100084,China;ZTE Corporation,Shenzhen 518057,China)

机构地区：[1]北京信息科学与技术国家研究中心,北京100084 [2]清华大学微电子学研究所,北京100084 [3]中兴通讯股份有限公司,深圳518057

出　　处：《密码学报》2021年第2期260-272,共13页Journal of Cryptologic Research

基　　金：工信部核高基重大专项“高安全等级网络基础设施关键设备核心芯片及软件研发”(2017ZX01030301-003)。

摘　　要：在基于Ring-LWE体系的格密码算法中,快速数论变换是加速多项式环乘法的常见方法,但该方法对于系数域模数小于多项式长度的多项式环乘法不适用.本文通过对多项式系数域构造扩域,扩大系数域的阶数,使小模数的多项式环乘法也能够使用快速数论变换来加速.扩域上的有限域乘法会带来额外的计算开支,但快速NTT变换的使用可以带来指数级的加速效果,总体来说节省更多的计算复杂度.常见的快速数论变换使用与快速傅里叶变换相似的折半定理,进行基2的快速变换,而系数域构造扩域后由于其阶数无法满足基2变换的条件,本文通过将多项式长度进行质因子分解来推导复合基的快速数论变换,最终为小模数多项式环乘法提供可观的加速效果.In Ring-LWE lattice cryptography algorithms,fast transform is a common method in number theory to accelerate polynomial multiplication.However,this method is not applicable to polynomial multiplication when the modulus of coefficient field is less than the length of the polynomial.In this paper,a method to construct extension field of polynomial coefficient field is provided.With this method,the order of the coefficient field can be enlarged.Though module multiplication on extension field brings more computation cost,the use of fast NTT transform can bring exponential acceleration effect and reduce the computational cost.The common fast transform in number theory uses the folding theorem similar to the fast Fourier transform to implement the base-2 fast NTT,but the order of the extended domain cannot satisfy the condition of the base-2 transform.In this paper,a fast number theory transform of mixed-base is derived by factorizing the length of polynomial,which provides considerable acceleration effect for small modulus polynomial multiplication.

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

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]