LWE问题的分析策略及格基约减算法综述

作者：王镭璋; 张帅领; 王保仓

来源：广州大学学报(自然科学版), 2021, 20(04): 29-45.

• 格密码
• 带错误的学习问题
• 格基归约算法

格公钥密码因其数学困难问题的平均/最坏复杂度等价性、代数结构的线性性和丰富的密码等功能而被普遍认为是最有发展前途的后量子密码。目前有大量格密码算法的安全性基于格上的错误学习(LWE)问题而设计。因此,研究LWE的求解算法对深刻理解格公钥密码算法的安全性至关重要。文章首先针对不同类型LWE问题的不同求解策略进行梳理和比较;其次,归纳整理了目前已有的格基约减算法的基本思想和技术原理;最后,对基于格归约的方法求解LWE问题的研究重点和趋势作了展望。

• 单位
  西安电子科技大学; 中国电子科技集团公司第三十研究所; 综合业务网理论及关键技术国家重点实验室