Release time:2025-03-31

Hits:

DOI number:10.13868/j.cnki.jcr.000714

Journal:密码学报

Place of Publication:北京,中国

Key Words:理想格,公钥密码,离散高斯分布采样,多项式乘法,软件优化

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

Co-author:高健鑫, 杨欣蕊, 郭子渊,chenjie

First Author:gaoying

Indexed by:Journal paper

Correspondence Author:gaoying

Volume:11

Issue:4

Page Number:878-894

ISSN No.:2095-7025

Translation or Not:no

CN No.:10-1195/TN