首页|Improved lower bound for the complexity of unique shortest vector problem
Improved lower bound for the complexity of unique shortest vector problem
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NETL
NSTL
万方数据
Unique shortest vector problem(uSVP)plays an important role in lattice based cryptography.Many cryptographic schemes based their security on it.For the cofidence of those applications,it is essential to clarify the complex-ity of uSVP with different parameters.However,proving the NP-hardness of uSVP appears quite hard.To the state of the art,we are even not able to prove the NP-hardness of uSVP with constant parameters.In this work,we gave a lower bound for the hardness of uSVP with constant parameters,i.e.we proved that uSVP is at least as hard as gap shortest vector problem(GapSVP)with gap of O(√n/log(n)),which is in NP ∩ coAM.Unlike previous works,our reduction works for paramters in a bigger range,especially when the constant hidden by the big-O in GapSVP is smaller than 1.
NETL
NSTL
万方数据
