编者荐语

本文深入剖析了格公钥密码的安全性基石——格上数学困难问题，为读者揭示了这一领域的核心奥秘。

孙柏顺 , 王保仓 . 格公钥密码的安全性评估方法[J]. 信息安全与通信保密 ,2024(10):2-15.

摘　要

格公钥密码是目前广受关注的一类后量子密码，其效率高，且归约证明结论与安全性分析相对成熟。格公钥密码的安全性基于格上的数学困难问题，针对这些困难问题的求解算法大多为启发式算法且复杂度评估困难，这一现状是格公钥密码的安全性精确评估以及参数配置的主要技术障碍。首先，介绍目前格上最短向量问题的求解算法及其复杂度评估模型；其次，梳理了目前主流格公钥密码的底层困难问题，讨论其与格上最短向量问题的归约关系；最后，对格公钥密码的安全性评估算法进行总结与展望。

论文结构

0　引　言

1　格理论

2　SVP求解与复杂度评估

2.1　精确求解算法

2.2　近似求解算法

2.3　复杂度评估模型

3　格上困难问题求解

3.1　NTRU问题求解

3.2　SIS问题求解

3.3 LWE问题求解

3.4 唯一最短向量问题复杂度评估

4　结 语

作者简介

  • 孙柏顺（2001—），男，博士研究生，主要研究方向为格密码分析；
  • 王保仓（1979—），通信作者，男，博士，教授，主要研究方向为后量子公钥密码、密码分析。