在线咨询
中国工业与应用数学学会会刊
主管:中华人民共和国教育部
主办:西安交通大学
ISSN 1005-3085  CN 61-1269/O1

工程数学学报 ›› 2025, Vol. 42 ›› Issue (5): 918-934.doi: 10.3969/j.issn.1005-3085.2025.05.009cstr: 32411.14.cjem.CN61-1269/O1.2025.05.009

• • 上一篇    下一篇

整数上离散高斯采样算法实现中的安全参数估计

沈 静1, 杨 欣2, 杜育松2   

  1. 1. 广东工贸职业技术学院计算机与信息工程学院,广州  510510
    2. 中山大学计算机学院,广州 510006
  • 收稿日期:2022-11-28 接受日期:2025-05-21 出版日期:2025-10-15 发布日期:2025-12-15
  • 通讯作者: 杜育松 E-mail: duyusong@mail.sysu.edu.cn
  • 基金资助:
    国家自然科学基金 (61972431);广东省基础与应用基础研究重大项目 (2019B030302008);广东省基础与应用基础研究项目 (2020A1515010687; 2022A1515011512);广州市基础与应用基础研究项目 (202102080332);广东工贸职业技术学院校级科研项目 ,(2021-ZK-17).

Estimating the Security Parameters for the Implementation of Discrete Gaussian Sampling Algorithms over the Integers

SHEN Jing1,  YANG Xin2,  DU Yusong2   

  1. 1. Department of Computer and Information Engineering, Guangdong Polytechnic of Industry and Commerce, Guangzhou 510510
    2. School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006
  • Received:2022-11-28 Accepted:2025-05-21 Online:2025-10-15 Published:2025-12-15
  • Contact: Y. Du. E-mail address: duyusong@mail.sysu.edu.cn
  • Supported by:
    The National Natural Science Foundation of China (61972431); the Major Project of Basic and Applied Basic Research in Guangdong Province (2019B030302008); the Basic and Applied Basic Research Project of Guangdong Province
    (2020A1515010687; 2022A1515011512); the Basic and Applied Basic Research Project of Guangzhou City (202102080332); the school-level scientific research project of Guangdong Polytechnic of Industry and Commerce (2021-ZK-17).

摘要:

整数上的离散高斯采样是实现基于格的密码(格密码)体制的基础构建之一。一般可采用Knuth-Yao采样或逆采样方法来设计采样算法。由于这类算法实现的是对近似离散高斯分布的采样,一个关键问题是先要计算近似分布和理想分布之间的R\'enyi散度,并确定出尾切界和概率精度,从而平衡采样效率和格密码体制的安全性。然而,R\'enyi散度又依赖尾切界和概率精度,计算时需要进行参数预设,并反复检查散度值是否达到安全性上界。通过对整数上离散高斯分布的R\'enyi散度进一步的理论分析,提出使用估计公式直接计算得到尾切界和概率精度的方式,并分别给出尾切界和概率精度估计公式。使用估计公式不需要进行预设,也无需使用高精度浮点运算,只需要输入关键参数并计算一次即可确定出合适的尾切界和概率精度,极大简化了尾切界和概率精度的确定过程,有助于离散高斯采样算法的实现。公式估计结果和达到安全性要求的最小结果之间的比较表明,对于取值在$2$到$50$之间的参数$\sigma$,使用估计公式获得的尾切界与达到安全性要求的最小尾切界之差不超过$1.0$,使用估计公式获得的概率精度与达到安全性要求的最小精度之差在$5$比特内,估计效果优良。

关键词: 格密码, 随机数生成, 离散高斯采样, 逆采样, Knuth-Yao采样, R\'enyi散度

Abstract:

Discrete Gaussian sampling over the integers is one of the fundamental building blocks of lattice-based cryptography. The sampling algorithm can usually be designed by using Knuth-Yao sampling or inversion sampling method. Since this kind of algorithms are to realize sampling from approximate discrete Gaussian distributions, a key problem is to estimate the R\'enyi divergence between the approximate distribution and the ideal distribution, and determine the tailcut bound and probability precision, so as to balance the sampling efficiency and the security of lattice-based cryptosystems. However, due to the R\'enyi divergence depending on the variations of the tailcut bound and probability precision, it needs to preset the parameters and repeatedly check whether the value of divergence achieves the upper bound of security. Based on some more detailed theoretical analysis of the R\'enyi divergence of discrete Gaussian distributions over the integers, a method of directly calculating the tailcut bound and probability precision by using estimation formulas is suggested, and two estimation formulas are given respectively. There is no need for us to preset parameters when using the estimation formulas, nor is there a need to use high-precision floating-point arithmetic. A proper tailcut bound and a probability precision can be determined only by inputting key parameters and calculating once. This greatly simplifies the process of determining them, which is helpful to the implementation of the sampling algorithm. The comparison between the estimated results and the actual results shows that, for the parameter $\sigma$ between $2$ and $50$, the difference between the tailcut bound estimated by the formula is less than $1.0$ than the minimum tailcut bound meeting the security requirement, and the difference between the probability precision estimated by the formula and the minimum precision meeting the security requirement is only with in $5$ bits. The estimation effect is good.

Key words: lattice-based cryptography, random number generation, discrete Gaussian sampling, inversion sampling, Knuth-Yao sampling, R\'enyi divergence

中图分类号: