Paper 2018/309

Error Estimation of Practical Convolution Discrete Gaussian Sampling with Rejection Sampling

Zhongxiang Zheng, Xiaoyun Wang, Guangwu Xu, and Chunhuan Zhao

Abstract

Discrete Gaussian Sampling is a fundamental tool in lattice cryptography which has been used in digital signatures, identify-based encryption, attribute-based encryption, zero-knowledge proof and fully homomorphic cryptosystem. As a subroutine of lattice-based scheme, a high precision sampling usually leads to a high security level and also brings large time and space complexity. In order to optimize security and efficiency, how to achieve a higher security level with a lower precision becomes a widely studied open question. A popular method for addressing this question is to use different metrics other than statistical distance to measure errors. The proposed metrics include KL-divergence, Rényi-divergence, and Max-log distance, and these techniques are supposed to achieve $2^p$ security with $\frac{p}2$ precision or even less. However, we note that error bounds are not universal but depend on specific sampling methods. For example, if we use the popular rejection sampling, there will be large gaps between some existing results and practical experiments in terms of error bounds. In this paper, we make two novel observations about practical errors. As an application of the observations, we consider convolution theorem of discrete Gaussian sampling by using Rejection method and reformulate it into a practical one with much more accurate error bounds. We describe a rigorous proof of it and demonstrate that the bounds are tightly matched by our experiments. It seems that the statistical distance is a better metric to distinguish distributions by looking at characteristic functions of probabilities. Our bounds under KL-divergence, Rényi-divergence and Max-log distance using Rejection sampling may have no influence on estimating security level, but this successful application reveals the proposed observations are very effective in analyzing practical probabilities. Moreover, some technical tools including several improved inequalities for discrete Gaussian measure are developed.

Note: Update the analysis about delta_RD