Cryptology ePrint Archive: Report 2021/199

Generic, Efficient and Isochronous Gaussian Sampling over the Integers

Shuo Sun and Yongbin Zhou and Yunfeng Ji and Rui Zhang and Yang Tao

Abstract: Gaussian sampling over the integers is one of the fundamental building blocks of lattice-based cryptography. In particular, it can't be avoided in trapdoor sampling until now. However, it's still a challenging work how to construct a generic, efficient, and isochronous Gaussian sampler. In this paper, our contribution is three-fold.

First, we propose a secure, efficient exponential Bernoulli sampling algorithm. It can be applied to Gaussian samplers based on rejection samplings. We apply it to FALCON, a candidate of round 3 of the NIST post-quantum cryptography standardization project, and reduce its signature generation time by 13.66%-15.52%.

Second, we develop a new Gaussian sampler based on rejection sampling. Our Algorithm can securely sample from Gaussian distributions with different standard deviations and arbitrary centers. We apply it to PALISADE (S&P'18), an open-source lattice cryptography library. The new implementation of trapdoor sampling in PALISADE has better performance while resisting timing attacks.

Third, we improve the efficiency of the COSAC sampler (PQC'20). The new COSAC sampler is 1.46x-1.63x faster than the original and has the lowest expected number of trials among all Gaussian samplers based on rejection samplings. But it needs a more efficient algorithm sampling from the normal distribution to improve its performance.

Category / Keywords: public-key cryptography / Lattice-based cryptography, Gaussian sampler, Rejection sampling, Timing attacks, Trapdoor

Date: received 24 Feb 2021

Contact author: sunshuo at iie ac cn, zhouyongbin at iie ac cn, jiyunfeng at iie ac cn, r-zhang at iie ac cn, taoyang at iie ac cn

Available format(s): PDF | BibTeX Citation

Version: 20210224:145617 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]