### Generic, Efficient and Isochronous Gaussian Sampling over the Integers

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

##### Abstract

Gaussian sampling over the integers is one of the fundamental building blocks of lattice-based cryptography. Among the extensively used trapdoor sampling algorithms, it's ineluctable until now. Under the influence of numerous side-channel attacks, it's still challenging to construct a Gaussian sampler that is generic, efficient, and resistant to timing attacks. 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%-14%. Second, we develop an isochronous 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 2018), an open-source lattice cryptography library. During the online phase of trapdoor sampling, the running time of the G-lattice sampling algorithm is reduced by 44.12% while resisting timing attacks. Third, we improve the efficiency of the COSAC sampler (PQC 2020). 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.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Lattice-based cryptographyGaussian samplerRejection samplingTiming attacksTrapdoor
Contact author(s)
sunshuo @ iie ac cn
History
2021-12-09: revised
See all versions
Short URL
https://ia.cr/2021/199

CC BY

BibTeX

@misc{cryptoeprint:2021/199,
author = {Shuo Sun and Yongbin Zhou and Yunfeng Ji and Rui Zhang and Yang Tao},
title = {Generic, Efficient and Isochronous Gaussian Sampling over the Integers},
howpublished = {Cryptology ePrint Archive, Paper 2021/199},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/199}},
url = {https://eprint.iacr.org/2021/199}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.