随着量子计算研究的不断发展,量子计算机的出现将不再是空谈,因此研究出能够抵御量子攻击的新型密码体制成为了研究热点。而格上的很多问题被证明是困难的,是通过量子计算在多项式时间内也无法求解的,因而很多密码体制的设计都是基于格上的困难问题。带错误学习问题(Learning with error,LWE)是格上的困难问题之一,通过LWE问题构造的密码体制在安全性上可以得到保证。而对LWE问题的采样效率关系到对应的密码体制的应用效率,基于这一问题,本文对LWE问题的采样算法进行了研究。在LWE问题中,对错误因子的采样占用了绝大部分的时间,并且使用的采样算法灵活多变,是研究LWE问题采样的主要内容。对LWE问题中错误因子的采样是从离散高斯分布上采样获得的,因此对离散高斯分布上的采样算法研究成为了本文的研究重点。本文以设计出高效的新型LWE问题采样算法为目标,首先对现有的LWE问题采样算法进行了研究,通过对算法的实现发现了现有算法中综合性能最好的离散金字塔(Ziggurat)高斯采样算法,因此对该算法进行了深入研究。基于将格上的采样转化为整数域上的采样这一思路,本文提出了一种新的LWE问题采样算法,在该采样算法中,对整数域上的离散高斯分布采样过程进行了优化,并与现有最优算法离散金字塔采样算法进行了效率比对,发现本文提出的优化改进算法比离散金字塔采样算法的采样速度快了 2倍。A-LWE(Augmented Learning with Errors)问题作为 LWE 问题的扩展问题,增加了信息嵌入的功能,因此基于A-LWE问题的安全加密方案相较已有基于LWE问题的安全加密方案更有研究价值。本文将新的LWE问题采样算法应用在了基于A-LWE问题的安全加密方案中,通过实验表明,在安全加密方案中,使用新的LWE问题采样算法比使用已有的采样算法,在实现速度上提升了 10%-20%。
暂无评论