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

摘要

Blomer and Seifert [1] showed that SIVP2 is NP-hard to approximate by giving a reduction from CVP2 to SIVP2 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(0(n))-time algorithm for approximating CVPp up to some constant factor gamma = 1 for any 1 = p = infinity. 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(0(n))-time algorithm for approximating SIVPp up to some constant factor gamma = 1 for any 1 = p = infinity. (C) 2020 Elsevier B.V. All rights reserved.