计算机工程

作者：卢嘉嘉, 杜育松

单位：中山大学 数据科学与计算机学院, 广州 510006

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

基金：国家重点研发计划"电子货币新算法与新原理研究"（2017YFB0802500）；广东省自然科学基金"基于格的密码体制的应用研究"（2016A030313298）；重庆市/信息产业部"计算机网络与通信技术重点实验室"开放基金"格密码与区块链技术的新应用研究"（CY-CNCL-2017-04）。

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

来源：2020年第8期

《计算机工程》期刊编辑部

查看计算机工程杂志2020年第8期