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

作     者：王艺航 梁天元 

作者机构：69224部队吉林 延边 32124部队西藏 阿里 

出 版 物：《应用数学进展》 (Advances in Applied Mathematics)

年 卷 期：2020年第9卷第12期

页      码：2244-2255页

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

主 题 词：LWE问题 含错方程组 BKW算法 算法实现 

学科分类：08[工学] 0812[工学-测绘类] 

D　O　I：10.12677/AAM.2020.912262

馆 藏 号：203100817...