A Note on the Concrete Hardness of the Shortest Independent Vectors Problem in Lattices

Divesh Aggarwal, Eldon Chung

Blömer and Seifert showed that ${\mathsf{SIVP}}_2$ is NP-hard to approximate by giving a reduction from ${\mathsf{CVP}}_2$ to ${\mathsf{SIVP}}_2$ for constant approximation factors as lo…