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

摘要：

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

关键词：数论变换算法、多项式环、格密码

所属期刊栏目：10

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

资助基金：国家自然科学基金;湖南省自然科学基金项目

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

页数：共15页

页码：539-553