格公钥密码的安全性评估方法  

Security Estimating Algorithms for Lattice-Based Public Key Cryptosystems

作　　者：孙柏顺 王保仓[1] SUN Baishun;WANG Baocang(State Key Laboratory of Integrated Service Networks,Xidian University,Xi’an Shaanxi 710071,China)

机构地区：[1]西安电子科技大学空天地一体化综合业务网全国重点实验室,陕西西安710071

出　　处：《信息安全与通信保密》2024年第10期1-15,共15页Information Security and Communications Privacy

基　　金：国家重点研发计划(2023YFB4403500);国家自然科学基金(62272362)。

摘　　要：格公钥密码是目前广受关注的一类后量子密码,其效率高,且归约证明结论与安全性分析相对成熟。格公钥密码的安全性基于格上的数学困难问题,针对这些困难问题的求解算法大多为启发式算法且复杂度评估困难,这一现状是格公钥密码的安全性精确评估以及参数配置的主要技术障碍。首先,介绍目前格上最短向量问题的求解算法及其复杂度评估模型;其次,梳理了目前主流格公钥密码的底层困难问题,讨论其与格上最短向量问题的归约关系;最后,对格公钥密码的安全性评估算法进行总结与展望。Lattice-based public key cryptography is a type of post-quantum cryptography that is currently receiving widespread attention for its high efficiency and the relative maturity of its reduction proofs and security analyses.The security of lattice-based public key cryptography relies on mathematical hard problems on the lattice,and most of the algorithms for solving these hard problems are heuristic algorithms with complex complexity estimating models,and this situation is the main technical obstacle to accurately estimate the security of lattice-based public key cryptosystems as well as the parameter configuration.This study first introduces the current algorithms for solving the shortest vector problems on the lattice and their complexity estimating model.Then,it reviews the underlying hard problems in the current mainstream lattice-based public key cryptographies and discusses how to convert them to shortest vector problem.Finally,it summarizes and prospects the security estimating algorithms for latticebased public key cryptosystems.

关 键 词：后量子密码 格公钥密码 格基归约算法 安全性评估 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]