Fine-grained hardness of the unique shortest vector problem in lattices
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.
NETL
NSTL
万方数据
