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

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