Paper 2021/199

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.

Metadata
Available format(s)
PDF
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
2021-02-24: received
See all versions
Short URL
https://ia.cr/2021/199
License
Creative Commons Attribution
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.