As pointed out by archgoon (and also pbsd) only for specific parameters is the problem broken, somewhat akin to saying a problem is NP-hard doesnt mean all instances of a problem are hard. But in this case for those parameters it isnt even NP hard.
I was under the impression that the Shortest Vector Problem was NP hard (at least, in some cases). If this works even in those scenarios, that's an even bolder claim by far.
SVP is NP-hard for approximation factors much smaller than this algorithm reaches. This algorithm solves approximation factors of at best O(n^4.5), but NP-hardness is only shown for approximation factors well below n^(1/2). See Figure 1 in page 2 of [1] for a breakdown of the hardness of various approximation factors.
(my favorite maxim from 2012 era atheism debates on youtube)
But yeah I totally agree. Putting the cart before the horse here with the outlined consequences probably isn't smart, but to be fair, I haven't (and probably couldn't) read the paper.
