一种新的多项式环上的数论变换算法

作者：张瀚丰; 周子健^*; 杨智超; 屈龙江

来源：密码学报, 2023, 10(03): 539-553.

DOI：10.13868/j.cnki.jcr.000612

• 数论变换算法
• 多项式环
• 格密码

得益于易并行、速度快、方案平均意义下的安全性可建立在最坏情况的底层困难问题上等特点,格密码被认为是最有希望成为后量子密码标准的方案.在基于多项式环上格困难问题构造的密码方案中,数论变换算法是加速多项式乘法、提升密码方案运行效率的关键技术手段之一.目前已有的方法只对形如■[x]/(xn±1)的多项式环适用,且安全参数n被限制为2的方幂.本文给出新多项式环■[x]/(xn-■+1)上的数论变换及其上元素相乘的公式,并借助蝶形算法给出了变换公式的计算复杂度.结合Karatsuba算法,扩展了n=c·2k情形下数论变换的参数选取范围,并优化了计算复杂度.

• 单位
  中国人民解放军海军工程大学; 国防科技大学