Cryptology ePrint Archive: Report 2018/309

Error Estimation of Practical Convolution Discrete Gaussian Sampling with Rejection Sampling

Zhongxiang Zheng and Xiaoyun Wang and 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.

Category / Keywords: Discrete Gaussian Sampling, convolution theorem, lattice, error estimation

Date: received 1 Apr 2018, last revised 31 Jul 2018

Contact author: zhengzx13 at mails tsinghua edu cn

Available format(s): PDF | BibTeX Citation

Note: Update the analysis about delta_RD

Version: 20180801:012915 (All versions of this report)

Short URL: ia.cr/2018/309


[ Cryptology ePrint archive ]