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

Improvement and Optimized Implementation of Key Components of Public Key Cryptography Based on Ideal Lattice

作　　者：高莹 高健鑫 杨欣蕊 郭子渊 陈洁[3] GAO Ying;GAO Jian-Xin;YANG Xin-Rui;GUO Zi-Yuan;CHEN Jie(School of Cyber Science and Technology,Beihang University,Beijing 100191,China;Zhongguancun Laboratory,Beijing 100094,China;Software Engineering Institute,East China Normal University,Shanghai 200062,China)

机构地区：[1]北京航空航天大学网络空间安全学院,北京100191 [2]中关村实验室,北京100094 [3]华东师范大学软件工程学院,上海200062

出　　处：《密码学报（中英文）》2024年第4期878-894,共17页Journal of Cryptologic Research

基　　金：国家自然科学基金(62372180)。

摘　　要：离散高斯分布采样和理想格中多项式乘法是基于理想格公钥密码的两个关键部件.这两个部件的高效性、安全性和强可移植性可极大促进基于理想格公钥密码的快速发展.本文从算法改进和实现优化两个方面出发,在保证安全性的基础上,提升两个部件的计算效率和可移植性.针对离散高斯分布采样部件,构造新的分布函数,确定新的采样标准;在此基础上,优化Bernoulli采样算法的算法流程,提出一种快速的位矩阵生成算法和后台采样优化技术,在保证采样安全性的前提下,极大地提升了采样的效率.针对理想格中多项式乘法部件,在基于蝶形结构数论变换的基础上,将模约减算法与延迟模运算相结合,并提出NTT缓存优化技术,在保证原有安全性的前提下,极大地缩短了乘法运算的时间.最后,在主流的x86-64、ARMv7和WebAssembly环境下分别进行仿真实验,结果表明改进算法和优化技术在三种测试环境下均可正确执行,且具有较强的可移植性.在保证安全性的前提下,使用位矩阵生成算法和后台采样优化技术的采样速度和原始算法相比至少提升13.57%和29.67%;使用模约减算法与延迟模运算结合与NTT缓存优化技术的乘法运算速度和原始算法相比至少提升77.54%和34.51%.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.

关 键 词：理想格 公钥密码 离散高斯分布采样 多项式乘法 软件优化 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]