格困难问题的复杂度分析

• 作者: 王旭阳 胡爱群
• 来源期刊: 密码学报
• 学科: 工学
• 关键词: 格 最短向量问题 最近向量问题 小整数解问题 误差学习
• 年，卷（期）: 2015,（1）
• 页码范围: 1-16
• 页数: 16页
• 分类号: TP309.7
• 字数: 11650字
• 语种: 中文
• DOI: 10.13868/j.cnki.jcr.000056

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	胡爱群	东南大学信息科学与工程学院	204	2184	22.0	39.0
2	王旭阳	东南大学信息科学与工程学院	3	14	1.0	3.0