BKW算法求解多元含错方程组

摘要

LWE是近年来设计后量子密码和全同态加密算法的热门数学问题。对这些算法的分析,关键在于求解相应的LWE问题。一般的LWE问题求解的困难性甚至高于格上SVP困难问题。本文研究了目前求解LWE问题较为有效的算法——BKW算法。首先详细总结了BKW算法的主要步骤和原理,针对不同参数的LWE问题,分析了BKW约化技术的合理选择,进一步对约减变元数、错误率的变化、方程数量的膨胀、时间复杂度等进行了深入研究。最后通过实验仿真对整个算法进行了实现,对Z/(5)上40个变元、10000个样本,错误率为2%、4%的LWE实例进行了成功求解。