整数上离散高斯取样的常数时间实现方法
来源：计算机工程杂志2020年第8期北京时间：
作者：卢嘉嘉, 杜育松
单位：中山大学 数据科学与计算机学院, 广州 510006
摘要：整数上的离散高斯取样是格密码体制实现的基本操作，也是决定安全性的重要因素，但可能受到计时攻击从而造成秘密信息的泄漏。为此，在Knuth-Yao算法的基础上，提出一种整数上离散高斯取样的常数时间实现方法。通过计算给定离散高斯分布的矩阵概率，确定概率矩阵每个列向量的汉明重量，并使用单指量多数据对其进行向量化操作，从而提高取样速度。实验结果表明，与运行时间可变的Knuth-Yao方法相比，该方法在单指令多数据支持下，采样速度可提升至14.9×106 samples/s。
关键词：格密码,离散高斯分布,离散高斯取样,Knuth-Yao算法,单指令多数据
基金资助：国家重点研发计划电子货币新算法与新原理研究（2017YFB0802500）；广东省自然科学基金基于格的密码体制的应用研究（2016A030313298）；重庆市/信息产业部计算机网络与通信技术重点实验室开放基金格密码与区块链技术的新应用研究（CY-CNCL-2017-04）。
