Association Journal of CSIAM
Supervised by Ministry of Education of PRC
Sponsored by Xi'an Jiaotong University
ISSN 1005-3085  CN 61-1269/O1

Chinese Journal of Engineering Mathematics ›› 2025, Vol. 42 ›› Issue (5): 918-934.doi: 10.3969/j.issn.1005-3085.2025.05.009

Previous Articles     Next Articles

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).

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

CLC Number: