基于理想格公钥密码关键部件的改进与优化实现

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 cryptography 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 distribution 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 efficiency 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 algorithm 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.