整数上离散高斯采样算法实现中的安全参数估计

摘要

整数上的离散高斯采样是实现基于格的密码(格密码)体制的基础构建之一。一般可采用Knuth-Yao采样或逆采样方法来设计采样算法。由于这类算法实现的是对近似离散高斯分布的采样，一个关键问题是先要计算近似分布和理想分布之间的Rényi散度，并确定出尾切界和概率精度，从而平衡采样效率和格密码体制的安全性。然而，Rényi散度又依赖尾切界和概率精度，计算时需要进行参数预设，并反复检查散度值是否达到安全性上界。通过对整数上离散高斯分布的Rényi散度进一步的理论分析，提出使用估计公式直接计算得到尾切界和概率精度的方式，并分别给出尾切界和概率精度估计公式。使用估计公式不需要进行预设，也无需使用高精度浮点运算，只需要输入关键参数并计算一次即可确定出合适的尾切界和概率精度，极大简化了尾切界和概率精度的确定过程，有助于离散高斯采样算法的实现。公式估计结果和达到安全性要求的最小结果之间的比较表明，对于取值在2到50之间的参数σ，使用估计公式获得的尾切界与达到安全性要求的最小尾切界之差不超过1.0，使用估计公式获得的概率精度与达到安全性要求的最小精度之差在5比特内，估计效果优良。

关键词

格密码 / 随机数生成 / 离散高斯采样 / 逆采样 / Knuth-Yao采样 / Rényi散度

基金资助

国家自然科学基金(61972431); 广东省基础与应用基础研究重大项目(2019B030302008); 广东省基础与应用基础研究项目(2020A1515010687; 2022A1515011512); 广州市基础与应用基础研究项目(202102080332); 广东工贸职业技术学院校级科研项目(2021-ZK-17)