摘要： 整数上的离散高斯取样是格密码体制实现的基本操作，也是决定安全性的重要因素，但可能受到计时攻击从而造成秘密信息的泄漏。为此，在Knuth-Yao算法的基础上，提出一种整数上离散高斯取样的常数时间实现方法。通过计算给定离散高斯分布的矩阵概率，确定概率矩阵每个列向量的汉明重量，并使用单指量多数据对其进行向量化操作，从而提高取样速度。实验结果表明，与运行时间可变的Knuth-Yao方法相比，该方法在单指令多数据支持下，采样速度可提升至14.9×10⁶ samples/s。

关键词: 格密码, 离散高斯分布, 离散高斯取样, Knuth-Yao算法, 单指令多数据

Abstract: Discrete Gaussian sampling on integer is the basic operation implemented by lattice cryptosystems,and is also a determinant factor of security,but it may be subject to timing attacks and cause the leakage of secret information.To address the problem,this paper proposes a constant-time implementation method for discrete Gaussian sampling on integers based on the Knuth-Yao algorithm.The method calculates the probability matrix of a given discrete Gaussian distribution,and determines the Hamming weight of each column vector of the probability matrix,which is vectorized by SIMD in order to improve the sampling speed.Experimental results show that compared with the standard Knuth-Yao method with variable running time,which can reach 14.9×10⁶ samples/s by adopting the vectorization technique with the support of Single Instruction and Multiple Data(SIMD).

Key words: lattice cryptography, discrete Gaussian distribution, discrete Gaussian sampling, Knuth-Yao algorithm, Single Instruction Multiple Data(SIMD)

中图分类号: 

• TP309