抵御计时攻击的基于Knuth-Yao的二元离散高斯采样算法

摘要：

格密码被认为是能够抵抗量子计算机攻击的新型密码.整数上的离散高斯采样算法在格密码中有着重要作用,但是容易遭受计时攻击.Knuth-Yao方法是一种基于二元概率矩阵的采样方法,对其进行简单改进可以实现常数运行时间,以抵御计时攻击,但极大地牺牲了采样速度.利用二元离散高斯分布的概率矩阵的移位性质,简化了Knuth-Yao方法的实现过程,减少了概率矩阵的存储空间.基于对Knuth-Yao方法中的概率矩阵的划分思想,有效地实现了抵御计时攻击的基于Knuth-Yao的二元离散高斯采样算法,并在较大程度上保证了采样速度.实验结果表明,与常规的基于Knuth-Yao的采样算法相比,改进的抵御计时攻击的采样算法采样速度仅降低了27.6％,较好地实现了采样速度与安全性的平衡.

关键词：离散高斯采样、二元高斯分布、Knuth-Yao方法、计时攻击

所属期刊栏目：49

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

资助基金：广东省基础与应用基础研究重大项目;国家自然科学基金;广东省基础与应用基础研究项目;广州市基础与应用基础研究项目;中央高校基本科研业务费项目;中山大学大学生创新创业训练计划项目

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

页数：共5页

页码：485-489