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.