格困难问题的复杂度分析  

Complexity Analysis of Lattice Hard Problems

作　　者：王旭阳[1] 胡爱群[1] 

机构地区：[1]东南大学信息科学与工程学院,南京210096

出　　处：《密码学报》2015年第1期1-16,共16页Journal of Cryptologic Research

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

摘　　要：作为新型的密码系统,格密码因为其巨大的潜在应用价值备受关注.作为格密码的基石,格困难问题一直是格密码研究的重点.本文通过分析一些常见的格问题,主要包括最短向量问题(SVP),最近向量问题(CVP),小整数解问题(SIS)和误差学习(LWE)等,对相关格问题的复杂度成果进行了总结.结果主要包括两个方面,一方面是SVP,CVP等格困难问题的复杂度分析,本文得到了SVP,CVP和SIVP在不同参数和不同范数下的依据参数大小排序的复杂度表格;另一方面则是不同问题之间的归约,其中包括最坏情况之间,最坏情况和一般情况之间和一般情况之间的归约,本文主要讨论了最坏情况和一般情况归约的结果,并得到了SIS和LWE按归约参数递减顺序排列的表格,并得到了困难问题归约的关系图.此外,文中还给出了格在密码系统上应用的例子.As a new cryptographic system, lattice-based cryptography attacked much attention for its high potential of applications. As the cornerstone of lattice-based cryptography, lattice problems are always the key point of lattice-based cryptography. Through the analysis of some common lattice problems, such as the shortest vector problem(SVP), the closest vector problem(CVP), the small integer solution problem(SIS) and the learning with errors problem(LWE), this paper summarizes some achievements about the hardness of these problems. This paper focuses mainly on two aspects. One is the complexity of these hard problems, according to the parameters order, and some complexity tables about SVP, CVP and SIVP which are obtained with different parameters and norms. The other one is the reductions between different lattice hard problems, including the reductions between the worse-case, the reductions between the average-case and the reductions from the worst-case to the average-case. By discussing the reductions from the worse-case to the average-case, this paper obtains some tables about SIS and LWE according to the reduction of parameters order, and a relationship diagram is obtained. In addition, this paper also presents some examples about the applications of these problems to cryptosystems.

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

分 类 号：TN918.1[电子电信—通信与信息系统]