摘要:
整数上的离散高斯采样是实现基于格的密码(格密码)体制的基础构建之一。一般可采用Knuth-Yao采样或逆采样方法来设计采样算法。由于这类算法实现的是对近似离散高斯分布的采样,一个关键问题是先要计算近似分布和理想分布之间的R\'enyi散度,并确定出尾切界和概率精度,从而平衡采样效率和格密码体制的安全性。然而,R\'enyi散度又依赖尾切界和概率精度,计算时需要进行参数预设,并反复检查散度值是否达到安全性上界。通过对整数上离散高斯分布的R\'enyi散度进一步的理论分析,提出使用估计公式直接计算得到尾切界和概率精度的方式,并分别给出尾切界和概率精度估计公式。使用估计公式不需要进行预设,也无需使用高精度浮点运算,只需要输入关键参数并计算一次即可确定出合适的尾切界和概率精度,极大简化了尾切界和概率精度的确定过程,有助于离散高斯采样算法的实现。公式估计结果和达到安全性要求的最小结果之间的比较表明,对于取值在$2$到$50$之间的参数$\sigma$,使用估计公式获得的尾切界与达到安全性要求的最小尾切界之差不超过$1.0$,使用估计公式获得的概率精度与达到安全性要求的最小精度之差在$5$比特内,估计效果优良。
中图分类号:
沈 静, 杨 欣, 杜育松. 整数上离散高斯采样算法实现中的安全参数估计[J]. 工程数学学报, 2025, 42(5): 918-934.
SHEN Jing, YANG Xin, DU Yusong. Estimating the Security Parameters for the Implementation of Discrete Gaussian Sampling Algorithms over the Integers[J]. Chinese Journal of Engineering Mathematics, 2025, 42(5): 918-934.