Improved lower bound for the complexity of unique shortest vector problem  

作　　者：Baolong Jin Rui Xue 

机构地区：[1]State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100085,China [2]School of Cyber Security,University of Chinese Academy of Sciences,Beijing 100049,China

出　　处：《Cybersecurity》2024年第3期102-110,共9页网络空间安全科学与技术（英文）

基　　金：This work is funded by National Natural Science Foundation of China(Grants No.62172405).

摘　　要：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 n 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 smallerthan1.

关 键 词：Computational complexity Unique shortest vector problem Bounded distance decoding Complexity reduction 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]