Generic,efficient and isochronous Gaussian sampling over the integers  

作　　者：Shuo Sun Yongbin Zhou Yunfeng Ji Rui Zhang Yang Tao 

机构地区：[1]Institute of Information Engineering,Chinese Academy of Sciences,Beijing,China [2]School of Cyber Security,University of Chinese Academy of Sciences,Beijing,China [3]School of Cyber Science and Engineering,Nanjing University of Science and Technology,Nanjing,China

出　　处：《Cybersecurity》2022年第3期52-73,共22页网络空间安全科学与技术（英文）

基　　金：This work is supported in part by National Natural Science Foundation of China(No.U1936209 and No.62002353);China Postdoctoral Science Foundation(No.2021M701726);Yunnan Provincial Major Science and Technology Special Plan Projects(No.202103AA080015).

摘　　要：Gaussian sampling over the integers is one of the fundamental building blocks of lattice-based cryptography.Among the extensively used trapdoor sampling algorithms,it is ineluctable until now.Under the influence of numerous side-channel attacks,it is 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-based 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.

关 键 词：Lattice-based cryptography Gaussian sampler Rejection sampling Timing attacks TRAPDOOR 

分 类 号：O15[理学—数学]