格困难问题的复杂度分析

摘要：

作为新型的密码系统,格密码因为其巨大的潜在应用价值备受关注.作为格密码的基石,格困难问题一直是格密码研究的重点.本文通过分析一些常见的格问题,主要包括最短向量问题(SVP),最近向量问题(CVP),小整数解问题(SIS)和误差学习(LWE)等,对相关格问题的复杂度成果进行了总结.结果主要包括两个方面,一方面是SVP,CVP等格困难问题的复杂度分析,本文得到了SVP,CVP和SIVP在不同参数和不同范数下的依据参数大小排序的复杂度表格;另一方面则是不同问题之间的归约,其中包括最坏情况之间,最坏情况和一般情况之间和一般情况之间的归约,本文主要讨论了最坏情况和一般情况归约的结果,并得到了SIS和LWE按归约参数递减顺序排列的表格,并得到了困难问题归约的关系图.此外,文中还给出了格在密码系统上应用的例子.

关键词：格、最短向量问题、最近向量问题、小整数解问题、误差学习

所属期刊栏目：2

分类号：TP309.7(计算技术、计算机技术)

资助基金：国家重点基础研究发展计划973计划2013CB338003

在线出版日期：2016-06-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共16页

页码：1-16