计算机工程 ›› 2020, Vol. 46 ›› Issue (8): 119-123.doi: 10.19678/j.issn.1000-3428.0055206

• 网络空间安全 • 上一篇    下一篇

整数上离散高斯取样的常数时间实现方法

卢嘉嘉, 杜育松   

  1. 中山大学 数据科学与计算机学院, 广州 510006
  • 收稿日期:2019-06-14 修回日期:2019-08-30 发布日期:2019-09-10
  • 作者简介:卢嘉嘉(1998-),女,本科生,主研方向为密码算法;杜育松,讲师、博士。
  • 基金项目:
    国家重点研发计划"电子货币新算法与新原理研究"(2017YFB0802500);广东省自然科学基金"基于格的密码体制的应用研究"(2016A030313298);重庆市/信息产业部"计算机网络与通信技术重点实验室"开放基金"格密码与区块链技术的新应用研究"(CY-CNCL-2017-04)。

Constant-time Implementation Method for Discrete Gaussian Sampling on Integer

LU Jiajia, DU Yusong   

  1. School of Data and Computer Science, Sun Yat-sen University, Guangzhou 510006, China
  • Received:2019-06-14 Revised:2019-08-30 Published:2019-09-10

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

中图分类号: