一种基于LWE采样算法的实现与优化

发布时间：2018-04-21 07:01

本文选题：格 + 带错误学习问题　；参考：《北京交通大学学报》2017年05期

【摘要】：基于带错误学习问题(Learning With Errors,LWE)构造的密码体制能够抵御量子攻击,它的应用效率与LWE问题的采样过程密切相关.而在LWE问题采样中,对其中的错误因子(Error Factor)采样占采样过程绝大部分时间,本文对LWE问题中的错误因子的采样算法进行研究,将在高斯分布上效率较高的金字塔(Ziggurat)采样算法,应用到了一种高效的LWE问题采样算法中.基于在连续域上的采样比离散域上采样效率高的思路,对LWE问题采样算法在离散域上采样的过程进行了优化,提出了一种将连续域上的采样结果进行取整的方法,.对优化前后的两种LWE问题的采样算法进行了对比实验,结果表明:改进后的算法在不占用大量内存并且保证安全性的情况下,将采样速度提高了38%~200%.
[Abstract]:The cryptosystem based on Learning With errors LW with error learning problem can resist quantum attack. Its application efficiency is closely related to the sampling process of LWE problem. In the sampling of LWE problem, the sampling of error factor (error factor) takes up most of the time in the sampling process. In this paper, the sampling algorithm of error factor in the LWE problem is studied, and the sampling algorithm of pyramid Ziggurat, which is more efficient in Gao Si distribution, is studied in this paper. It is applied to an efficient sampling algorithm for LWE problem. Based on the idea that sampling in continuous domain is more efficient than that in discrete domain, the sampling process of sampling algorithm for LWE problem in discrete domain is optimized, and a method of rounding the sampling results in continuous domain is proposed. Two sampling algorithms for LWE problems before and after optimization are compared. The results show that the improved algorithm increases the sampling speed by 38 / 200 without occupying a lot of memory and ensuring security.
【作者单位】：北京交通大学计算机与信息技术学院;
【基金】：国家自然科学基金青年基金项目(61402035) 中央高校基础科研业务费专项资金(2014JBM033)~~
【分类号】：TN918.4

【相似文献】