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

摘要：

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

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

所属期刊栏目：46

分类号：TP309(计算技术、计算机技术)

资助基金：国家重点研发计划“电子货币新算法与新原理研究”;广东省自然科学基金“基于格的密码体制的应用研究”;重庆市/信息产业部“计算机网络与通信技术重点实验室”开放基金“格密码与区块链技术的新应用研究”

在线出版日期：2020-09-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：119-123