格上唯一最短向量问题的细粒度复杂性
Fine-grained hardness of the unique shortest vector problem in lattices
金保隆 1薛锐1
作者信息
- 1. 中国科学院信息工程研究所网络空间安全防御重点实验室,北京 100085;中国科学院大学网络空间安全学院,北京 100049
- 折叠
摘要
唯一最短向量问题(unique shortest vector problem,uSVP)的困难性是一些流行的格密码方案的安全基础,对其在不同参数下的复杂性的研究也是格密码体系的重要组成部分,然而这方面的研究进展十分缓慢,同时对uSVP的细粒度复杂性的研究也十分欠缺.本文改进了一个从最短向量问题(shortest vector problem,SVP)到uSVP的归约算法,提高了其成功概率,调整了参数限制,从而允许建立不同参数条件下从SVP到uSVP的细粒度归约.利用这个归约,得以证明以下结果:(1)在超多项式时间下,得到了一个参数更大的从SVP到uSVP的归约;(2)在强指数时间假设(gap strong exponential time hypothesis,GapSETH)下,构建了从常数参数的SVP到常数参数的uSVP的亚指数时间归约,从而证明了 uSVP在GapSETH下的困难性;(3)以上结果都可以转化成有界距离译码(bounded distance decoding,BDD)的相应结论:在对应条件下求解参数小于1的BDD也是困难的;(4)结合稳定格中的格点个数上界,得到了参数远超常数的从SVP到uSVP的归约.
Abstract
The intractability of uSVP(unique shortest vector problem)is the foundation of the security of some popular lattice-based cryptographic schemes.The study of its computational complexity plays an important part in the lattice-based cryptography.However,the research progress on the difficulties of uSVP under different parameters is very slow.There is also a lack of research on the fine-grained hardness of uSVP.In this work,we presented an improved reduction that allows for a fine-grained reduction of SVP(shortest vector problem)instances to uSVP instances.Our reduction has a potentially greater success probability and allows more flexible parameters.Using this reduction,we demonstrated the following results:(1)we presented a reduction from SVP to uSVP with greater parameters,in a super polynomial setting;(2)assuming the GapSETH(gap strong exponential time hypothesis),we presented a reduction from SVP to uSVP with subexponential running time and constant parameters,which proved the intractability of uSVP under GapSETH;(3)all results above can be transferred into the hardness results of BDD(bounded distance decoding),hence BDD with a parameter strictly smaller than 1 is also intractable assuming GapSETH;(4)by combining our reduction with an upper bound for the number of lattice points in stable lattices,we presented several reductions from SVP to uSVP with parameters beyond constant.
关键词
最短向量问题/唯一最短向量问题/计算复杂性/细粒度复杂性/复杂性归约Key words
shortest vector problem/unique shortest vector problem/computational complexity/fine-grained complexity/complexity reduction引用本文复制引用
出版年
2024
NETL
NSTL
万方数据