A note on the concrete hardness of the shortest independent vector in lattices

Abstract Blomer and Seifert [1] showed that SIVP 2 is NP-hard to approximate by giving a reduction from CVP 2 to SIVP 2 for constant approximation factors as long as the CVP instance has a certain property. In order to formally define this requirement on the CVP instance, we introduce a new computational problem called the Gap Closest Vector Problem with Bounded Minima. We adapt the proof of [1] to show a reduction from the Gap Closest Vector Problem with Bounded Minima to SIVP for any l p norm for some constant approximation factor greater than 1. In a recent result, Bennett, Golovnev and Stephens-Davidowitz [2] showed that under Gap-ETH, there is no 2 o ( n ) -time algorithm for approximating CVP p up to some constant factor γ ≥ 1 for any 1 ≤ p ≤ ∞ . We observe that the reduction in [2] can be viewed as a reduction from Gap - 3 - SAT to the Gap Closest Vector Problem with Bounded Minima. This, together with the above mentioned reduction, implies that, under Gap-ETH, there is no randomised 2 o ( n ) -time algorithm for approximating SIVP p up to some constant factor γ ≥ 1 for any 1 ≤ p ≤ ∞ .