学术报告（王明强 6.7）

格上的最短向量问题(SVP)和最近向量问题(CVP)被证明是NP-Hard问题，且抗量子攻击。能用来设计密码算法的格上困难问题有LWE,SIS,NTRU。格密码体制的安全强度、参数的长短及实现效率依赖于其基于的格困难问题(LWE,SIS,NTRU等)的计算复杂度。当前LWE,SIS,NTRU等格上的困难问题靠归约到格上的基本困难问题(SVP,SIVP,CVP等)来保证困难性。目前还不存在高效的量子算法求解SVP等格上的基本困难问题，对于LWE,SIS,NTRU等适用于构建格密码体制的数学困难问题还没有发现优于经典算法的量子计算方法。格上困难问题的计算及其上的密码体制的分析、设计成为后量子密码算法中最核心课题。本报告从格归约和计算两个方面介绍格上困难问题LWE,SIS,NTRU及其变形问题的困难性。