密码学报（中英文）2024，Vol.11Issue(4)：830-844,15.DOI:10.13868/j.cnki.jcr.000711
环上多项式乘法在GPU上的优化实现
Optimal Implementation of Multiplication over Polynomial Rings on GPUs
摘要
Abstract
As a core component of lattice-based cryptography,the efficiency and accuracy of polyno-mial multiplication over polynomial rings are crucial for the practicality and security of lattice-based cryptographic schemes.Existing polynomial multiplication algorithms,such as NTT and KNTT,have high parallelism,however they are difficult to fully leverage on CPUs.This means that there is still much room for improvement in the efficiency of ring polynomial multiplication algorithms based on CPU implementations.To address this issue,this paper proposes an efficient implementation of ring polynomial multiplication based on the KNTT algorithm proposed by Zhu et al.This implementation leverages the massive parallel nature and powerful computing capabilities of GPUs.Specifically,each thread block in the GPU thread model is mapped to one of the small-degree polynomials generated by the KNTT algorithm,with each block responsible for the NTT parallel operation of a single polyno-mial.As multiple thread blocks in the GPU can be scheduled to start computing tasks simultaneously,parallel processing of multiple polynomials is enabled,which further improves the efficiency of the KNTT algorithm on the GPU.Experimental results show that the GPU implementation of the KNTT algorithm is significantly faster than both the GPU version of the NTT algorithm and the original CPU version.For example,when the modular polynomial length N is 16 384,the GPU implementation achieves a speedup of 93.78％compared to the original C version.Compared with the GPU version of the NTT algorithm,the GPU implementation of the KNTT algorithm can achieve a speedup of 40.62％when N=2048.关键词
格密码/多项式乘法/NTT/KNTTKey words
lattice-based cryptography/polynomial multiplication/NTT/KNTT分类
信息技术与安全科学引用本文复制引用
赵新颖,袁峰,赵臻,王保仓..环上多项式乘法在GPU上的优化实现[J].密码学报（中英文）,2024,11(4):830-844,15.基金项目
国家自然科学基金(62272362,U19B2021,62102299) （62272362,U19B2021,62102299）
河南省网络密码技术重点实验室研究课题(LNCT2022-A05) （LNCT2022-A05）
陕西高校青年创新团队National Natural Science Foundation of China(62272362,U19B2021,62102299) （62272362,U19B2021,62102299）
Open Fund of Henan Key Laboratory of Network Cryptography Technology(LNCT2022-A05) （LNCT2022-A05）
The Youth Innovation Team of Higher Edu-cations of Shaanxi Province （）
