Abstract:

Discrete Gaussian sampling over the integers is one of the fundamental building blocks of lattice-based cryptography. Rejection sampling is one of the main methods for the discrete Gaussian sampling over the integers. The key of using rejection sampling is to implement a sampling procedure for Bernoulli distributions with exponential functions as parameters, and this sampling procedure is also the key to determine whether the whole sampling algorithm can resist timing attacks. For a real x > 0, based on the isochronous sampling algorithm given by SUN et al. for the “exponential Bernoulli distribution” β_2-x, an alternative exact sampling algorithm with timing attack resistance is proposed for β_2-x. It can prevent the leakage of the information on the value of x caused by timing attacks, and does not require (online) floating-point arithmetic, and can also avoid the statistical error in the practical implementation of the sampling algorithm of SUN et al., so as to ensure the exactness of sampling results in practice. Experimental results demonstrate the effectiveness of this exact sampling algorithm.

Key words: lattice-based cryptography, discrete Gaussian sampling, Bernoulli distribution, timing attack