The crypto system constructed with Learning With Errors (LWE) can resist quantum attacks,and its application efficiency is closely related to the sampling process of LWE problem.In the LWE problem sampling,the error factor sampling which accounted for most of the sampling process.This paper studies the sampling algorithm of the error factor in the LWE problem,and applies the Gaussian distribution (Ziggurat) sampling algorithm to an effective sampling algorithm of the LWE problem.Based on the idea of high sampling efficiency on the sampling domain in the continuous domain,this paper deals with the LWE problem sampling algorithm on the discrete domain.The sampling process is optimized,and a method of rounding the sampling results in the continuous domain is proposed and applied to the LWE problem sampling algorithm.We have compared the two LWE sampling algorithms before and after optimization.The experimental results show that the improved algorithm increases the sampling speed by 38％ ～ 200％ in the condition of not using a lot of memory and ensuring the safety of sampling.%基于带错误学习问题(Learning With Errors,LWE)构造的密码体制能够抵御量子攻击,它的应用效率与LWE问题的采样过程密切相关.而在LWE问题采样中,对其中的错误因子(Error Factor)采样占采样过程绝大部分时间,本文对LWE问题中的错误因子的采样算法进行研究,将在高斯分布上效率较高的金字塔(Ziggurat)采样算法,应用到了一种高效的LWE问题采样算法中.基于在连续域上的采样比离散域上采样效率高的思路,对LWE问题采样算法在离散域上采样的过程进行了优化,提出了一种将连续域上的采样结果进行取整的方法,.对优化前后的两种LWE问题的采样算法进行了对比实验,结果表明:改进后的算法在不占用大量内存并且保证安全性的情况下,将采样速度提高了38％～200％.
展开▼
