密码学报（中英文）2024，Vol.11Issue(4)：878-894,17.DOI:10.13868/j.cnki.jcr.000714
基于理想格公钥密码关键部件的改进与优化实现
Improvement and Optimized Implementation of Key Components of Public Key Cryptography Based on Ideal Lattice
摘要
Abstract
The discrete Gaussian distribution sampling and the polynomial multiplication are two key components of public key cryptography based on ideal lattice.High efficiency,security and strong portability of these two components can greatly promote the rapid development of public key cryp-tography based on ideal lattice.This paper starts from the algorithm improvement and optimized implementation,and improves the computational efficiency and portability of these two components while maintaining their security.For discrete Gaussian distribution sampling components,a new dis-tribution function is constructed to determine a new sampling standard.Based on this,the algorithm procedure of Bernoulli sampling algorithm is optimized,and a fast bit matrix generation algorithm and background sampling optimization method are proposed,which greatly improve the sampling ef-ficiency while ensuring the sampling security.For the polynomial multiplication component in the ideal lattice,based on the number theory transformation of butterfly structure,the modulo reduction algorithm is combined with the delay modulo operation,and the NTT cache optimization method is proposed,which greatly improves the efficiency of multiplication operation without affecting the original security.Finally,simulation experiments are carried out in the mainstream x86-64,ARMv7,and WebAssembly environments respectively,and the results show that the improved algorithms and method of optimization can be correctly executed in the three test environments and have strong portability.On the premise of ensuring security,the sampling speed using bit matrix generation algo-rithm and background sampling optimization is increased by at least 13.57％and 29.67％,which are higher than those of the original algorithm.Compared with the original algorithm,the multiplication speed of NTT buffer optimization combined with modular reduction algorithm and delayed modular operation is improved by at least 77.54％and 34.51％respectively.关键词
理想格/公钥密码/离散高斯分布采样/多项式乘法/软件优化Key words
ideal lattice/public key cryptography/discrete Gaussian distribution sampling/multi-plication of polynomials/software optimization分类
信息技术与安全科学引用本文复制引用
高莹,高健鑫,杨欣蕊,郭子渊,陈洁..基于理想格公钥密码关键部件的改进与优化实现[J].密码学报（中英文）,2024,11(4):878-894,17.基金项目
国家自然科学基金(62372180)National Natural Science Foundation of China(62372180) （62372180）
